Learning Java: How to Use Maps HashMap vs. TreeMap(SortedMap) vs. LinkedHashMap vs. Hashtable

• Introduction
• Inheritance Review
• Understanding Classes
  • HashMap
  • LinkedHashMap
  • TreeMap
  • Hashtable
• Comparison
• Summary
• References

Introduction

The structure of key-value pair map is important in programming. Java provides a basic interface Map and several classes such as HashMap, TreeMap and LinkedHashMap that implement the interface. I will mainly compare these classes, HashMap, LinkedHashMap and TreeMap.

Inheritance Review

The Map interface has many implementing classes. And some of these classes also have sub-classes.

Interface Map<K, V>
All Known Subinterfaces:
    Bindings, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, LogicalMessageContext, MessageContext, NavigableMap<K,V>, SOAPMessageContext, SortedMap<K,V>
All Known Implementing Classes:
    AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

Class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

class AbstractMap<K,V>
extends Object
implements Map<K,V>

interface SortedMap<K,V>
extends Map<K,V>

class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, Serializable

class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>

Understanding Classes

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. The Map interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings.

Basically, these classes that implement Map are like:

• HashMap is implemented based on a hash table.
• LinkedHashMap is like a HashMap, but in insertion order or in least-recently-used (LRU) order.
• TreeMap is implemented based on a red-black tree.
• WeakHashMap is a map of weak keys that allow objects referred to by the map to be released.
• ConcurrentHashMap is a thread-safe map which does not involve synchronization locking.
• IdentityHashMap is a hash map that uses == instead of equals() to compare keys.

HashMap

Hash table based implementation of the Map interface. The HashMap class is roughly equivalent to Hashtable.

HashMap offers O(1) lookup and insertion. If you iterate through the keys, though, the ordering of the keys is essentially arbitrary. It is implemented by an array of linked lists.

• A HashMap contains values based on the key.
• It contains only unique elements.
• It may have one null key and multiple null values.
• It makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
• It provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
• It is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

LinkedHashMap

LinkedHashMap is a subclass of HashMap.

LinkedHashMap offers O(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.

• A LinkedHashMap contains values based on the key.
• It contains only unique elements.
• It may have one null key and multiple null values.
• It maintains insertion order or LRU order. If you want to use LRU order, you need to change one parameter.
• Different from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.
• Same with HashMap, it is not synchronized, either.

TreeMap

TreeMap is implemented NavigableMap whose super interface are SortedMap and Map.

TreeMap offers O(log N) lookup and insertion. Keys are ordered, so if you need to iterate through the keys in sorted order, you can. This means that keys must implement the Comparable interface.

• A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
• It contains only unique elements.
• It cannot have null key but can have multiple null values.
• It is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
• It is not synchronized.

Hashtable

The basic Hashtable is very similar to the HashMap.

• A Hashtable is an array of list. Each list is known as a bucket. The position of bucket is identified by calling the hashcode() method. A Hashtable contains values based on the key.
• It contains only unique elements.
• Any non-null object can be used as a key or as a value.

According to Java API, Hashtable is synchronized, unlike the new collection implementations. If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use ConcurrentHashMap in place of Hashtable.

Comparison

A simple testing example for insertion:

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.TreeMap;

public class SimpleTest {

    private int[] integers = { 1, -2, 0, 3, -4 };

    public void testHashMap() {
        HashMap<Integer, String> map = new HashMap<Integer, String>();
        for (int i : integers) {
            map.put(i, Integer.toString(i));
        }
        System.out.print("HashMap oder: ");
        System.out.println(map);
    }

    public void testLinkedHashMap() {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>(0, 0.75f, true);
        for (int i : integers) {
            map.put(i, Integer.toString(i));
        }
        System.out.print("LinkedHashMap oder: ");
        System.out.println(map);
        map.get(integers[2]);
        System.out.print("LinkedHashMap oder after accessing: ");
        System.out.println(map);
    }

    public void testTreeMap() {
        TreeMap<Integer, String> map = new TreeMap<Integer, String>();
        for (int i : integers) {
            map.put(i, Integer.toString(i));
        }
        System.out.print("TreeMap oder: ");
        System.out.println(map);
    }

    public static void main(String... strings) {
        SimpleTest st = new SimpleTest();
        st.testHashMap();
        st.testHashMap();
        st.testLinkedHashMap();
        st.testTreeMap();
    }

}

/*
Output:
HashMap oder: {0=0, 1=1, -2=-2, 3=3, -4=-4}
HashMap oder: {0=0, 1=1, -2=-2, 3=3, -4=-4}
LinkedHashMap oder: {1=1, -2=-2, 0=0, 3=3, -4=-4}
LinkedHashMap oder after accessing: {1=1, -2=-2, 3=3, -4=-4, 0=0}
TreeMap oder: {-4=-4, -2=-2, 0=0, 1=1, 3=3}
*/

Summary

In a conclusion, you could use HashMap if there are no special requirements, because it is faster and requires less overhead. If insertion order is important, use LinkedHashMap. If the order of key is important, use TreeMap.

References

1. Thinking in Java (4th Edition) by Bruce Eckel - Understanding Maps
2. Java 8 API Specification - Map
3. Differences between TreeMap, HashMap and LinkedHashMap in Java
4. HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap