Storing Objects in Java
Part 3 - The Map Interface

by Thomas Paul

In the past two months we discussed the basics of the Collection interface and reviewed the children of this interface, the List and Set interfaces. This month we will look at the Map interface. What exactly is a Map in Java? A Map is simply a class that stores key-value pairs and provides a way to locate a value based on the key. An array is simply a list of objects that allows you to find an object by specifying a number. A Map allows you to specify an Object to find a different Object. Imagine a Map containing Employee objects for eaach employee in your company. A Map would allow you to locate a particular Employee object in the Map by specifying a key such as their Social Security Number. A Map can not contain a duplicate key.

The Map interface is a replacement for the Dictionary class which is now considered obsolete. There are seven non-abstract implementations of the Map interface that we will discuss. The Hashtable and Properties classes have been around since JDK 1.0. TreeMap, HashMap, and WeakHashMap were added in JDK 1.2. Two new classes were added in J2SE 1.4. These are the LinkedHashMap and the IdentityHashMap. Each implementation contains features that make it appropriate for particular applications. Each of the classes has a unique feature that makes its use desirable in certain circumstances. The HashMap is the basic Map implementation. Hashtable is synchronized. TreeMap maintains keys in a sorted order. LinkedhashMap maintains the objects in the order they were added to the Map. The IdentityHashMap is a special Map that maintains key by reference equality (they point to the same object) rather than object equality (they contain the same value). WeakHashMap is a Map with weak keys, that is, objects in a WeakHashMap will be garbage collected if the only reference to them is the WeakHashMap itself. Finally, the Properties class is a special class used to access and maintain properties files that contain name value pairs.

Overall performance is best with the HashMap. The Hashtable is synchronized so performance is slightly worse. The performance of the Properties class is almost identitcal to the HashTable. TreeMap is slower because it maintains keys in a sorted order.

Testing of Map objects.

Type

Test size

Put

Get

Iteration

TreeMap

10

26.5

15.6

56.3

 

100

31.7

18.9

35.16

 

1000

26.9

21.7

7.0

HashMap

10

14.0

11.0

28.1

 

100

12.2

12.6

38.9

 

1000

9.2

12.3

7.0

Hashtable

10

15.6

12.5

51.6

 

100

20.2

14.7

49.8

 

1000

12.1

18.8

9.6

IdentityHashMap

10

18.8

25.0

35.9

 

100

22.2

25.3

32.6

 

1000

18.8

25.2

6.3

LinkedHashMap

10

20.3

10.9

23.5

 

100

18.9

11.6

17.7

 

1000

14.5

12.0

3.3

Figure 1: relationships between the classes and interfaces of the Map interface

The Map interface

The map interface contains one static nested interface, Map.Entry which we will discuss in a moment. The Map contains the basic methods for all Map implementations such as put and get. In addition, the Map provides three separate ways to get objects from it as Collection objects. You can get a Set of keys, a Collection of values, or a Set of key-value pairs stored in a Map.Entry object.

Here are some of the key methods of the Map interface:

The Map.Entry Interface

The Map interface contains a static nested interface called Entry. This interface is used to access key-value pairs as individual objects outside of the Map. The entrySet( ) method can be used to get individual key-value pairs out of the Map. You can then use methods of the Map.Entry interface to get the key or valu out of the Object.

Here are some of the key methods of the Map.Entry interface:


The HashMap class

The HashMap class is the simplest implementation of the Map interface. The HashMap does not add any additional methods (other than clone) beyond those found in the Map interface. The HashMap achieves good performance by using a hash to store the key in the Map. The hash allows fast lookup which means that the containKey( ) method will perform much better than the containsValue( ) method. Any Object used as a key in a HashMap must implement the hashCode( ) and equals( ) methods. See Part 2 of this series for a discussion of this issue.

The HashMap does not guarantee the order of the items in the Map and allows one null key. Duplicates are not permitted. The HashSet offers "constant time" performance for lookups involving the key and linear time for lookups based on value. This means that adding items to the Map will not cause significant performance degradation as long as lookups are done by the key. The performance of basic functions such as put, remove, get, etc is based on two factors which can be specified in the constructor of the HashMap, initial capacity and load factor. See the HashSet discussion in Part 2 of this series for the further discussion of these parameters.

The LinkedHashMap Class

New to J2SE 1.4, the LinkedHashMap class is used in exactly the same way as the HashMap class. It has no additional methods but it does have one additional constructor that we will discuss in a moment. The basic difference between HashMap and LinkedHashMap is that the LinkedHashMap maintains the order of the items added to the Map. It does this by maintaining a doubly linked list containing the hash and the original order of the items. According to Sun, the LinkedHashMap should run nearly as fast as the HashMap.

The LinkedHashMap has one additional constructor that takes an additional boolean parameter. This allows you to construct a LinkedHashMap that maintains items, not in the order that they are added to the Map but rather in the order in which they are accessed.

The Hashtable Class

Part of Java since JDK 1.0, the Hashtable class is a synchronized implementation of the Map interface. It has three methods that are not part of the Map interface (contains, keys, and elements) that should be avoided since the Map interface has methods (containsValue, containsKey, and values) that provide the identical functionality. The main difference between HashMap and hashtable is that the hashtable is synchronized, hoewever, synchronization can be achieved by using the Collections.synchronizedMap method on the HashMap. The Hashtable does not permit null keys or null values. The Hashtable should be treated as a class left in java to support maintenance of older programs.

The WeakHashMap Class

The WeakHashMap is virtually identical to the HashMap. The difference is that entries in this class do not count as a reference against the key contained in this Map. This means that over time, the garbage collector may remove keys from the WeakHashMap and garbage collect the object. This would give the appearance that objects are being removed from the Map. The size( ) method may return different values over time. The isEmpty( ) method may return false and then true. Value objects in the WeakHashMap will be garbage collected only if their key is removed and they have no other reference to them. It should be noted that if the value object has a reference to its own key object, the key objetc will not be garbage collected. This situation should be avoided.

The IdenitityHashMap Class

The IdentityHashMap is also like the HashMap with the exception that a key is considered equal to another key only if they are pointing to the exact same object. Other implementations of Map use the equals( ) method to determine if two keys are equal. The IdentityHashMap uses the == comparator. Two keys (a and b) are considered equal if a == b. The IdentityhashMap should only be used in the cases where this functionality is required. It should not be used otherwise.

The TreeMap class

The TreeMap class guarantees that the keys in the Map will be sorted in ascending order by either the keys natural order or by a Comparator provided to the constructor of the TreeMap. Searching for an item in a TreeMap will be slower than in a HashMap because the hashing algorithm gives better performance than the compareTo() method which is used to locate items in a TreeMap. In part 2 of this series, we discussed how to control the sorting of the TreeSet. The same methods apply to controlling the sorting of the TreeMap.

TreeMap does add several new methods to the Map interface.

The Properties class

The Properties class is very simialr to the Hashtable and has been part of Java since JDK 1.0. The Properties class adds additional functionality that can be extremely useful. The Properties class represents a persistent list of properties. What exactly does this mean? The Properties class is designed to provide methods to store and load files containing key-value pairs as Strings. Properties files are simply key-value pairs where the key and value are separated by an "=" (name=Tom) and eack key-value pair is on a separate line. A Windows ini file is an example of a properties file. In many cases, XML files are replacing properties files but the simplicity of a properties file combined with its ease of use makes the Properties class still a very useful class.

Although the Properties file inherits the methods of the Hashtable, it is recommended that the Hashtable put method not be used as this may allow the insertion of non-String objects. Only Strings should be used as either a key or a value in a Properties object. A Properties object with a non-String in it will throw an exception if you attempt to store it to a file. A Properties object can contain another Properties object (specified in the constructor) which is used as the default keys if no matching key is found in the Properties object.

The Properties class provides several new methods:

Using the Properties class

Here is an example of reading in a properties file, removing the password and printing out the reaminder. As you can see, using the Properties class is very simple.

import java.util.*;
import java.io.*;

public class PropsDemo {

    public static void main(String[] args) throws Exception {

        BufferedInputStream bStream = new BufferedInputStream(new FileInputStream("prefs.ini"));
        Properties props = new Properties();
        props.load(bStream);
        props.remove("password");
        props.list(System.out);
        bStream.close();
    }
} 

Conclusion

We have taken a quick look at the main implementations of the Map interface and also examined how we can make use of properties files. As we have seen, there are quite a few Map objects and which Map object you wish to use will depend greatly upon how you intend on using it in your application. Like the Set interface, performance is less a concern in choosing among Map objects. The main concern is the functionality you require.

Next month we will wrap up this series and take a look at the many additional functions found in the Collections class.