Utilizing the Map Interface from the Collections Framework
by Ming Chou
We want to hear from you! Please send us your feedback.
Hashtable"3.1 java.util.HashTable Implementation
3.2 java.util.HashMap Implementation
3.3 java.util.TreeMap Implementation
The following Technical Article may contain actual software programs in source code form. This source code is made available for developers to use as needed, pursuant to the terms and conditions of this license.
1. Introduction
With the introduction of the Collections Framework in the Java[tm] 2 Platform, Standard Edition, several commonly used data structure interfaces were integrated into the Java[tm] 2 SDK to simplify the programmer's job, and to allow the programmer to focus on business requirements rather than building data objects. This new framework provides several useful tools and functionality to the user that do not require the user to know much about the details of the framework.
Within the Java[tm] Collections Framework, there are two main interfaces, (1) the Collection interface, which includes the list and set interfaces, and (2) the Map interface. The main difference between the Collection and the Map interfaces is that a Collection stores a group of Objects, while Maps hold key/value pairs of data. In a Map Object, each key has at most one associated value. A perfect everyday example of when to use a Map would be to correlate a person's profile with their social security number. The social security number would be the key, while the profile would be the corresponding person's mapped "value".
2. The Map Interface
The following code snippet shows what the Map interface looks like: public interface java.util.Map {
//Altering Methods
public Object put(Object key, Object value); //gets Object with key/value mapping
public Object remove(Object key); //removes Object with key
public void putAll(java.util.Map); //put all Map elements into current Map
public void clear(); //removes all mappings from current Map
//Querying Methods
public Object get(Object key); //gets Object with key
public int size(); //returns number of Map elements
public boolean isEmpty(); //check if Map is empty
public boolean containsKey(Object); //Checks if map contains object as key
public boolean containsValue(Object); //Checks if map contains object as value
public boolean equals(Object); //compares specified Object with current Map
//Viewing Methods
public java.util.Set keySet(); //Gets keys
public java.util.Collection values(); //Gets values
public java.util.Set entrySet(); //Gets mappings
public static interface java.util.Map.Entry { //a map-entry (single key/value pair)
public Object getKey(); //returns current entry key
public Object getValue(); //returns current entry value
public Object setValue(Object value); //replaces current value with specified value
public boolean equals(Object); //compares current object with specified object
public int hashCode(); //returns hashcode with current map-entry
}
}
The Map interface provides us with methods to accomplish three main functionalities:
Map Altering
Map Querying
Map Viewing
Map altering methods allow the user to alter the contents of the current Map. This includes the removal, updating, and insertion of key/value pairs.
Map querying methods allow the user to retrieve key/value pairs from the Map. Not only are there methods to query the contents of Map elements, but there are also methods that can be used to query the entire Map Object.
There are three different views which can be used to analyze Map key/value Objects. Since the keys in a map must be unique, the keyset() method retrieves a Set of the keys in the Map (A Set is a collection of unique data elements). The values() method returns a Collection of the value Objects (A Collection is a group of objects which allows the storage of duplicate objects). The entrySet() method returns a Set of Map.Entry mappings.
The Map.Entry interface is the object used to store a single key/value pair. Within the Map.Entry, there are methods to store and retrieve individual key/value elements. The entrySet() method returns a Set of objects that implements the Map.Entry interface. Each element within the Set represents a single key/value pair in the Map.
3. Map Implementations
The following section will provide a brief overview of three commonly used map implementations:
java.util.Hashtable
java.util.HashMap
java.util.TreeMap
Hashtable"3.1 java.util.Hashtable Implementation
The Hashtable Object maps key objects to value objects. Methods are provided to enable a quick lookup of values based upon a key search. The Hashtable Object was introduced in Java 1.0 platform, while the HashMap Object which is introduced in the next section was introduced in the Java 1.2 platform platform. The additional methods the Hashtable implementation offers (not including those in the Map interface) are: public class java.util.Hashtable extends Dictionary implements Cloneable, Map, Serializable {
//Hashtable constructors
public Hashtable(); //construct a default Hashtable with default capacity and load of 0.75
public Hashtable (int initialCapacity); //construct a Hashtable with passed capacity and default load of 0.75
public Hashtable(int initialCapacity, float load); //construct Hashtable with passed capacity and load
public Hashtable(Map); //construct Hashtable with passed mapping
//Hashtable specific methods
public boolean contains(Object); //checks if Object is in Hashtable
public Enumeration elements(); //returns Enumeration of elements in Hashtable
public Enumeration keys(); //returns Enumeration of keys in hashtable
public Object clone(); //creates shallow copy of Hashtable(structure copied, but not key/values)
public String toString(); //prints out key/value pairs of Hashtable elements
protected void rehash(); //reorganizes all elements in Hashtable, and increases Hashtable capacity
public Object get(Object); //get Value from passed in key
public Object put(Object key, Object value); //insert key/value pair
}
A Hashtable is similar to a regular table where keys are mapped to values, but the Hashtable offers a quick way to retrieve data. When an element is inserted into the Hashtable, the name of the Object is hashed and the resulting integer value from the hash is used as the table index for that Object. The Object is then stored as the value of the cell the hash index is referring to. If another Object with the same name is stored into the Hashtable, the extra Objects are stored in a linked list following the original item.
The initial capacity of the Hashtable dictates how many spaces are allocated for Objects in the Hashtable. As a Hashtable is a dynamic entity, constant resizing is required to efficiently allocate space for the Hashtable. The load factor indicates how full percentage wise the Hashtable is allowed to become before the Hashtable's capacity is automatically increased.
Two things to note are that (1) Hashtable data is synchronized and (2) the null value is not allowed as a key or value in the Hashtable.
3.2 java.util.HashMap Implementation
The HashMap is very similar to the Hashtable, but was introduced recently starting with the Java 1.2 platform. There are two main differences between HashMap and Hashtable. First, the HashMap is not synchronized (making access faster), and second, the HashMap allows null values to be used as values or keys, which are disallowed in the Hashtable implementation. HashMap specific methods (not found in the Map interface) are: public class java.util.HashMap implements Map, Cloneable, java.io.Serializable {
public HashMap(int initialCapacity, float load); //construct a default HashMap with default capacity and load of 0.75
public HashMap(int initialCapacity); //construct a HashMap with passed capacity and default load of 0.75
public HashMap(); //construct HashMap with passed capacity and load
public Hashmap(Map); //construct HashMap with passed mapping
public Object clone(); //constructs shallow copy of HashMap (keys/values not copied)
public Object get(Object); //get Value from passed in key
public Object put(Object key, Object value); //insert key/value pair
}
The HashMap, after being introduced in the Java 1.2 platform platform, has provided much better performance than the Hashtable. Though HashMap is not synchronized, it can be made synchronized. What happens if the HashMap is modified in a multi-threaded environment? The HashMap has a fail-fast iterator. Fail-fast means that the iterator is notified when the underlying collection changes, and essentially causes the fetching of the next element to fail by throwing ConcurrentModificationException.
3.3 java.util.TreeMap Implementation
The TreeMap implementation implements the Map interface but stores elements in a tree. The TreeMap has a little bit more overhead during operation than the HashMap, but because of the tree structure, it returns keys in sorted order. If there is no need to retrieve Map elements sorted by key, then the HashMap would be a more practical structure to use. The TreeMap implemented public members not included in the Map interface are: public class java.TreeMap implements SortedMap, Cloneable, java.io.Serializable {
public TreeMap(); //new TreeMap
public TreeMap(Comparator); //new TreeMap using Comparator
public TreeMap(Map); //new TreeMap using Map
public TreeMap(SortedMap); //new TreeMap using sortedMap
public Comparator comparator();
public Object firstKey(); //returns first Key
public Object lastKey(); //returns last Key
public Object clone(); //returns shallow copy of TreeMap
public SortedMap headMap(Object); //returns SortedMap of all elements upto Object
public SortedMap tailMap(Object); //returns SortedMap of all elements after Object
public SortedMap subMap(Object, Object); //returns SortedMap of all elements between keys
public Object get(Object); //get Value from passed in key
public Object put(Object key, Object value); //insert key/value pair
}
The TreeMap is very useful when you need to store objects in some sort of order. For example, a phone book or storing the words in a dictionary would be ideal candidates for usage with a TreeMap. SortedMap is a subinterface of Map. TreeMap is the only implementation that utilizes the SortedMap interface.
4. Examples
In the following section, two examples will be presented, the first will show an example of a HashMap, while the second will utilize the TreeMap. Notice that the only difference in the code is present in one line only, when the calendar Map is instantiated, yet the outputs are completely different due to the difference in storage behavior of TreeMap and HashMap.
4.1 HashMap Example
import java.util.*;
public class ExampleHashMap {
//calendar Map
Map calendar = new HashMap();
//constructor to add all elements into Map
public ExampleHashMap(String d[], String i[]){
for (int x=0; x<d.length; x++)
calendar.put(d[x], i[x]);
}
//main method
public static void main(String args[]) {
//Data to be inserted into calendar
String [] dates = {"10/31/01", "01/01/01", "03/05/01", "02/04/01"};
String [] items = {"Halloween", "New Years", "Birthday", "Anniversary"};
//create instance of class
ExampleHashMap example = new ExampleHashMap(dates, items);
//print out all key/value pairs in map
System.out.println("map= " + example.calendar);
//retrieve mappings into Set
Set mappings = example.calendar.entrySet();
System.out.println("object \t\t\tkey\t\tvalue");
//iterate through mappings and print content
for (Iterator i = mappings.iterator(); i.hasNext();) {
Map.Entry me = (Map.Entry)i.next();
Object ok = me.getKey();
Object ov = me.getValue();
System.out.print(me + "\t");
System.out.print(ok + "\t");
System.out.println(ov);
}
}
}
-Output of HashMap (each compiler will output results in different order):
/tmp> java ExampleHashMap
map= {01/01/01=New Years, 03/05/01=Birthday, 02/04/01=Anniversary, 10/31/01=Halloween}
object key value
01/01/01=New Years 01/01/01 New Years
03/05/01=Birthday 03/05/01 Birthday
02/04/01=Anniversary 02/04/01 Anniversary
10/31/01=Halloween 10/31/01 Halloween
Notice how the objects stored into the HashMap were not stored in chronological order, nor in alphabetical order. The output order actually depends upon which compiler is being used, and the machine settings. Halloween was actually the first object "put" into the HashMap, but was actually stored in the last mapping in the HashMap.
4.2 TreeMap Exampleimport java.util.*;
public class ExampleTreeMap {
//calendar Map
Map calendar = new TreeMap();
//constructor to add all elements into Map
public ExampleTreeMap(String d[], String i[]){
for (int x=0; x<d.length; x++)
calendar.put(d[x], i[x]);
}
//main method
public static void main(String args[]) {
//Data to be inserted into calendar
String [] dates = {"10/31/01", "01/01/01", "03/05/01", "02/04/01"};
String [] items = {"Halloween", "New Years", "Birthday", "Anniversary"};
//create instance of class
ExampleTreeMap example = new ExampleTreeMap(dates, items);
//print out all key/value pairs in map
System.out.println("map= " + example.calendar);
//retrieve mappings into Set
Set mappings = example.calendar.entrySet();
System.out.println("object \t\t\tkey\t\tvalue");
//iterate through mappings and print content
for (Iterator i = mappings.iterator(); i.hasNext();) {
Map.Entry me = (Map.Entry)i.next();
Object ok = me.getKey();
Object ov = me.getValue();
System.out.print(me + "\t");
System.out.print(ok + "\t");
System.out.println(ov);
}
}
}
-Output of TreeMap:
/tmp> java ExampleTreeMap
map= {01/01/01=New Years, 02/04/01=Anniversary, 03/05/01=Birthday, 10/31/01=Halloween}
object key value
01/01/01=New Years 01/01/01 New Years
02/04/01=Anniversary 02/04/01 Anniversary
03/05/01=Birthday 03/05/01 Birthday
10/31/01=Halloween 10/31/01 Halloween
Output from the TreeMap object is a little more predictable than the HashMap. Notice that Mappings were sorted in alphabetical order by the key value. Unlike the HashMap output, the TreeMap output would be more useful in a real world calendar application. One drawback of using the TreeMap data structure as mentioned earlier is that there is overhead when you "put" or "remove" elements from the TreeMap structure due to sorting, which can affect program performance.
5. Conclusion
The Map interface and the different implementations offered as part of the Collections package provide a convenient way to store key/value objects. The general rule when considering which implementation to utilize is to use TreeMap when element ordering is important, and use HashMap when elements do not need to be stored in any particular order. Using Hashtable is generally discouraged since HashMap provides all similar functionality, and generally runs quicker. HashMaps can also be made synchronized if you are using the HashMap in a multi-threaded environment.
