Map is a data structure interface that connects keys and values. Each key has at most one associated value. Some examples of key/value pairs would be driver's license number and “Object representing a licensed driver”, username and password, ISBN and book title. The first of each of these pairs is a key for uniquely retrieving the second. The most obvious way of storing a Map is as a two-column table, and you can get fancier from there.
The Map interface provides three views onto its collection of keys/values. You can see the map as a collection of keys, or as a collection of values, or as a collection of key/value pairs. Once you have these collections back, you can invoke the standard Collection method to get an iterator and visit all the elements.
The order of a map is defined as the order in which the iterators on a map's collection views return their elements. Some Map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap, do not.
The Map interface looks like this:
public interface java.util.Map <K, V> {
public java.util.Set<K> keySet(); // get keys
public java.util.Collection<V> values(); // get values
public java.util.Set<Map.Entry<K,V>> entrySet();// get mappings
public boolean containsKey(Object);
public boolean containsValue(Object);
public V get(Object key);
public V put(K key, V value);
public void putAll(Map<? extends K,? extends V> t);
public V remove(Object key);
public boolean isEmpty();
public int size();
public void clear();
public boolean equals(Object);
public int hashCode();
public static interface java.util.Map.Entry<K, V> {
public K getKey();
public V getValue();
public V setValue(V v);
public boolean equals(Object o);
public int hashCode();
}
}
The keys, values, and mappings are returned as collections so that you can easily compare entire maps to one another, and answer questions like “does this map have all the keys that are in that map?” or “does this map have any values in common with that map?” You answer these kind of questions by using the set difference, intersection, and union operations that we have already seen for collections.
If you have a class that implements map, you can iterate over all its mappings like this:
Set<Map.Entry<String,String>> s = myMap.entrySet();
for (Map.Entry<String,String> me : s) {
The set returned by entrySet() is a collection of objects that belong to the static nested interface java.util.Map.Entry. You can then get an iterator for that Set, and each object that it returns will belong to type (class that implements Map.Entry). You can invoke any of the methods promised in the nested interface on that returned object. You can get each key in turn, or get/set each value in turn.
To review, the objects ok and ov represent a single entry in the Map. The object ok is the key for value ov. We got the entry set from the Map, we get the key and value from the entry set.
Maps and their concrete subclasses are part of the Collections Framework, but they are not in themselves collections. You can get pieces from them that are collections, but Map is not a subinterface of Collection.
In the next section, we'll look at a couple of concrete classes that implement Map. Before we do that, we'll briefly outline how hash tables work, and what it means for you in practice.
Now the purpose of the method hashCode() in class java.lang.Object should be clear. It ensures that every single object in the system has a hashcode, and thus can be put in a hash table without further work on your part. The hashcode is a 32-bit int, and the hash table algorithm will typically reduce it modulo the size of the table, and take the remainder as an index value.
The hashcode returned by Object.hashCode() looks like the address of the object in virtual memory, which is a good way of ensuring that unique objects have unique hashcodes. That's fine for many classes, but not so fine for others. There are some classes where objects can be unique (i.e., at different memory addresses) but still be equal.
String is an example of a class with that property. I may have a String object that holds the value “mudflap”. For all purposes, the content of the string should be used to determine equality to some other String, not the unique memory address. I want any other string with those characters to compare equal. Therefore, the Object.hashCode() isn't very useful for String, and the String class should override it.
String does override Object.hashCode(), and it replaces the method with one where the hashcode is calculated based on the characters in the string. The algorithm takes each character in the String and multiplies it by 31 to the power i, where i is the character offset within the String. It sums all these values to get the hash for a given string. (Another way of looking at this is that, loosely, it converts the String to a base 31 int.)
String also overrides java.lang.Object.equals() and replaces it with an equality test that looks at content, not address. There is a rather large pitfall here that you must be careful to avoid. You must always make sure that you override equals() and hashCode() in pairs, and you must make sure they are implemented in mutually compatible ways. If two objects compare equal, then their hashCodes must have the same value too.
If you fail to follow these precautions, then any use of Maps on your object will give undefined values. You may know all the places that you use maps in your own code, but it's hard to be aware of when the run-time library is using a Map on some of your classes on your behalf. So the only safe course is to follow the rule, and make certain that if two objects compare equal, their hashCodes must have the same value too.
The class java.util.HashMap implements the Map interface. It uses a hash table to minimize the searching on every lookup and it implements Map, hence, the name HashMap. You should now use this class where formerly you might have used JDK 1.0's Hashtable.
HashMap is a supremely useful class. Hash tables allow you store together any number of key/value pairs. Instead of storing items with index values 0, 1, 2, 3, as you would in an array, you provide the key to be associated with the object. Then in the future, you need provide only that key again, and voila, out pops the right object.
Here are the public members of HashMap, over and above what is promised by the Map interface that it implements:
public class java.util.HashMap <K, V>
implements Map<K, V>, Cloneable, java.io.Serializable {
public HashMap(int size, float load);
public HashMap(int size);
public HashMap();
public HashMap(Map<? extends K,? extends V> m);
public Object clone();
}
It has four constructors and a public clone() method. The size and load arguments to the constructors specify the initial size (number of elements) of the table, and the fraction of the table which can become full before it is reallocated to a bigger size. As a rule of thumb, a load factor of 0.75 seems to work quite well, and this is the default that the library uses. The last constructor does what you'd expect: constructs a new map with the same mappings as the given map.
HashMap has fail fast iterators, and is not synchronized. Here is some example code that uses a hash map to hold a company phone book containing names and corresponding extension numbers:
import java.util.*;
public class example2 {
// the Map!
Map<String, String> phonebook = new HashMap<String, String>();
// constructor
public example2(String n[], String nums[]) {
for(int i=0; i< n.length; i++)
phonebook.put( n[i], nums[i] );
}
public static void main(String[] args) {
// data
String [] names = { "Lefty", "Guarav", "Wong", "Rupamay" };
String [] extns = { "4873", "4810", "3769", "0" };
// get an instance of this class
example2 ex = new example2( names, extns );
// dump out the map
System.out.println("map: " + ex.phonebook);
// get the mappings
Set<Map.Entry<String,String>> s = ex.phonebook.entrySet();
// iterate over the mappings
// for (Iterator i = s.iterator(); i.hasNext(); ) {
for (Map.Entry me : s) {
Object ok = me.getKey();
Object ov = me.getValue();
System.out.print("key=" + ok );
System.out.println(", value=" + ov );
}
}
}
Compiling and running the program results in this:
% javac -source 1.5 example2.java
% java example2
map: {Wong=3769, Guarav=4810, Rupamay=0, Lefty=4873}
key=Wong, value=3769
key=Guarav, value=4810
key=Rupamay, value=0
key=Lefty, value=4873
You can see that the collection of key/value pairs has been stored into a HashMap and can be retrieved on demand.
The final Collections framework class to review here is java.util.TreeMap. TreeMap has the same relationship to HashMap that TreeSet has to HashSet. In other words, TreeMap implements the Map interface, and its underlying data structure is a red/black tree.
TreeMap takes some extra cycles to do its work of inserting and retrieving keys in the tree, but it will produce its keys in sorted order on demand. If you have no need to see the keys in sorted order, use HashMap instead. In the context of our phone directory example, we may well wish to have the keys in order, as this would be useful if we wanted to output the office phone directory in alphabetic order of names.
Here are the public members of TreeMap, over and above what is promised by the Map interface that it implements:
public class java.util.TreeMap <K, V>
implements SortedMap<K,V>, Cloneable, java.io.Serializable {
public TreeMap(); // constructors
public TreeMap(Comparator<? super K> c);
public TreeMap(Map<? extends K,? extends V> m);
public TreeMap(SortedMap<K,? extends V> m);
public Comparator<? super K> comparator();
public K firstKey();
public K lastKey();
public Object clone();
public SortedMap<K,V> headMap(K toKey);
public SortedMap<K,V> tailMap(K fromKey);
public SortedMap<K,V> subMap(K fromKey, K toKey);
}
The TreeMap class has four constructors which work in the obvious way. The first one creates an empty TreeMap. The second constructor creates an empty TreeMap that will use the Comparator passed as an argument. The third creates a TreeMap out of the elements in the given Map. The fourth constructor creates a TreeMap out of the elements in the given SortedMap.
A SortedMap is a subinterface of Map. TreeMap is the only current implementor of SortedMap. It is the interface that promises all the other methods of SortedMap that are over and above those promised by Map. The other methods will get you the comparator that is in use, or null if the TreeMap is using natural order. The firstKey() and lastKey() methods return the lowest and highest keys in the Map, respectively.
The method headMap() returns a view of this Map containing only elements that are strictly less than the argument object. The method tailMap() returns a view of elements that are greater than or equal to the argument object. The method subMap() returns a view into the Map that holds only objects starting at the from object inclusive, and going up to, but not including, the to object.
As an example use of TreeMap is the phone directory program, modified to use a TreeMap by changing one line.
import java.util.*;
public class example3 {
// the Map!
Map<String, String> phonebook = new TreeMap<String, String>();
// constructor
public example3(String n[], String nums[]) {
for(int i=0; i< n.length; i++)
phonebook.put( n[i], nums[i] );
}
public static void main(String[] args) {
// data
String [] names = { "Lefty", "Guarav", "Wong", "Rupamay" };
String [] extns = { "4873", "4810", "3769", "0" };
// get an instance of this class
example3 ex = new example3( names, extns );
// dump out the map
System.out.println("map: " + ex.phonebook);
// get the mappings
Set<Map.Entry<String,String>> s = ex.phonebook.entrySet();
// iterate over the mappings
// for (Iterator i = s.iterator(); i.hasNext(); ) {
for (Map.Entry me : s) {
Object ok = me.getKey();
Object ov = me.getValue();
System.out.print("key=" + ok );
System.out.println(", value=" + ov );
}
}
}
The output of running this program is now in sorted order because we used TreeMap:
map: {Guarav=4810, Lefty=4873, Rupamay=0, Wong=3769}
key=Guarav, value=4810
key=Lefty, value=4873
key=Rupamay, value=0
key=Wong, value=3769
Most of the time you won't be querying a Map for all its mappings. Most of the time you'll have a key and want to look up the corresponding value using this method:
public V get(Object key);
Or you'll be putting pairs into the table using this method:
public V put(K key, V value);
And that thought concludes this chapter.