List
models a numbered sequence of elements where the client
can control the ordering of the elements.
Set
models a group of unique elements (no duplicates) where
the client has no control over the ordering of the elements.
Map
Map
models a group of elements that are accessed by keys:
Map
Exampleskey | value | |
---|---|---|
mathematical function y = f(x) | x | y |
dictionary | word | list of definitions |
days per month | month | number of days |
provincial capitals | province | capital city |
book index | keyword | set of pages |
student marks in a course | student number | list of marks |
student marks in a course | student number | map of names of marked items to marks |
Map
Interface
Map
does not extend Collection
;
instead, it is a separate interface:
public interface Map<K,V> { // Basic operations V put(K key, V value); V get(Object key); V remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk operations void putAll(Map<? extends K, ? extends V> m); void clear(); // Collection Views public Set<K> keySet(); public Collection<V> values(); public Set<Map.Entry<K,V>> entrySet(); // Interface for entrySet elements public interface Entry { K getKey(); V getValue(); V setValue(V value); } }
Map<String, String> capitals = new HashMap<String, String>(); capitals.put("Ontario", "Toronto"); capitals.put("Quebec", "Quebec City"); capitals.put("Nova Scotia", "Halifax"); capitals.put("New Brunswick", "Fredericton"); capitals.put("Manitoba", "Winnipeg"); capitals.put("British Columbia", "Victoria"); capitals.put("Prince Edward Island", "Charlottetown"); capitals.put("Saskatchewan", "Regina"); capitals.put("Alberta", "Edmonton"); capitals.put("Newfoundland and Labrador", "St. John\'s");
Set<String> keys = capitals.keySet(); for (String province : keys) { String city = capitals.get(province); out.printf("Capital of %25s : %s%n", province, city); }
Capital of New Brunswick : Fredericton Capital of Quebec : Quebec City Capital of Nova Scotia : Halifax Capital of British Columbia : Victoria Capital of Newfoundland and Labrador : St. John's Capital of Manitoba : Winnipeg Capital of Alberta : Edmonton Capital of Saskatchewan : Regina Capital of Prince Edward Island : Charlottetown Capital of Ontario : Toronto
A map uses a key to insert, remove, and retrieve values. For example, suppose you wanted to count the number of times each word was used in a text document:
Everything starts somewhere, although many physicists disagree.
But people have always been dimly aware of the problem with the
start of things. They wonder aloud how the snowplough driver gets to
work, or how the makers of dictionaries look up the spelling of the
words. Yet there is the constant desire to find some point in the
twisting, knotting, ravelling nets of space-time on which a metaphorical
finger can be put to indicate that, here, is the point where it all
began...
Opening paragraphs of Hogfather, Terry Pratchett
to 3 they 1 but 1 everything 1 aware 1 somewhere 1 where 1 people 1 space-time 1 been 1 of 5 although 1 began 1 wonder 1 on 1 snowplough 1 be 1 work 1 ravelling 1 how 2 or 1 spelling 1 here 1 disagree 1 finger 1 always 1 many 1 that 1 start 1 makers 1 some 1 dictionaries 1 put 1 can 1 have 1 dimly 1 indicate 1 nets 1 metaphorical 1 words 1 driver 1 all 1 find 1 twisting 1 look 1 aloud 1 with 1 is 2 knotting 1 it 1 constant 1 desire 1 a 1 physicists 1 gets 1 problem 1 the 9 in 1 up 1 point 2 which 1 starts 1 there 1 things 1 yet 1
To count the number of times a word appears in a document, you
want to map a word (the key) to its count (the value). The appropriate
collection is a map with String
keys and Integer
values:
import java.util.Map;
import java.util.HashMap;
public class WordCount
{
public static void main(String[] args)
{
Map<String, Integer> wordCount =
new HashMap<String, Integer>();
}
}
Map
HashMap
get
, put
, containsKey
TreeMap
get
, put
, containsKey
Comparable
Let's assume that you have created a scanner for the text file and created a loop to read in each word.
Suppose you read in a word. If the word is a new word, you want
to insert the word as a key with a value of 1
(the word
has been counted once). If the word is not a new word, you want to
add one to the count for that word.
How can you tell if a word is already a key in the map?
There are two ways to check if a map holds a key.
boolean containsKey(Object key)
Returns true
if this map contains a mapping for
the specified key.
V get(Object key)
Returns the value to which the specified key is mapped,
or null
if this map contains no mapping for the key.
For the word counting problem, you have to call get
if you need to update the word count, so you might as well use
get
:
// is word already in the map?
Integer count = wordCount.get(word);
if (count == null)
{
// word is not in the map
}
else
{
// word is in the map
}
Once you know if a word is a key in the map, you want to update the value associated with the key.
The method put
inserts a key-value pair into the map.
V put(K key, V value)
Associates the specified value with the specified key in this map.
If the map previously contained a mapping for the key,
the old value is replaced.
// is word already in the map? Integer count = wordCount.get(word); if (count == null) { wordCount.put(word, 1); } else { wordCount.put(word, count + 1); }
WordCount
Exampleput
returns a value
Maps only allow a key to map to single value; this means that
the keys in a map must be unique (ie. the keys form a set). If you
use an existing key to insert a value, the old value is replaced by
the new value, and put
returns the old value.
put
returns null
if the key used is
not currently in the map.
The keys in a map are unique so they form a set. A client can ask a map for its set of keys:
// Map<String, Integer> wordCount ...
Set<String> words = wordCount.keySet();
output.println(words);
The code fragment above prints:
[to, they, but, everything, aware, somewhere, where, people, space-time, been, of, although, began, wonder, on, snowplough, be, work, ravelling, how, or, spelling, here, disagree, finger, always, many, that, start, makers, some, dictionaries, put, can, have, dimly, indicate, nets, metaphorical, words, driver, all, find, twisting, look, aloud, with, is, knotting, it, constant, desire, a, physicists, gets, problem, the, in, up, point, which, starts, there, things, yet]
Notice that HashMap
does not order the keys.
If you want sorted keys, use TreeMap
.
for
Loops and CollectionsThe easiest way to traverse a list or a set is to use the
enhanced for loop (also called the for each
loop). This type of loop only works for classes that
implement the Collection
interface (and arrays).
Recall that the keys for our word counting map are all strings. If we want to print each key, one key per line, we would want a loop like:
for each key in the map's keyset print the key followed by a newline
You can use a for-each loop:
for (String key : wordCount.keySet())
{
output.println(key);
}