Java: HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap

Map is one of the most important data structures. In this post, I shall show you the main differences between HashMap, TreeMap, HashTable and LinkedHashMap.

There are four commonly used implementations of Map in Java SE: HashMap, TreeMap, Hashtable and LinkedHashMap. If we use one sentence to describe each implementation, it would be the following:

HashMap is a hash table without ordering on keys, and with amortized constant access costs.
TreeMap is a hash table allows to access entries based on key ordering with logarithmic costs.
LinkedHashMap is a hash table using a linked list to preserve the insertion order of entries.
Hashtable is the thread-safe version of HashMap without nullable values.

We give more specific remarks concerning the use of maps below.

HashMap

If you want to use self-defined objects as keys, make sure the equals and hashCode methods implemented correctly. By default, the hashCode and equals methods implemented in Object class are used. The default hash codes are distinct for distinct objects, and two keys are equal only if they have the same primitive value or they are references to the same object.

TreeMap

Keys for TreeMap must implement Comparable interface, since they have to compare with each other. Note that TreeMap uses compareTo other than equals to decide whether two keys are identical. Another difference between TreeMap and the other map implementations is that it provides guaranteed O(lgn) time cost for the containsKey, get, put and remove operations, while others guarantee amortized O(1) time cost (O(n) in the worst case) for these operations.

Hashtable

The Hashtable class is roughly equivalent to HashMap, except that it is synchronized and it does not permit null keys or null values.

LinkedHashMap

LinkedHashMap is a subclass of HashMap. It inherits the features of HashMap and, in addition, the output of the entrySet method preserves the insertion/access-order of the entries. There is also a special method removeEldestEntry that allows implementer to erase entries according to custom criteria. One direct application of LinkedHashMap in computer science is the LRU (least-recently-used) cache (example code).

Static abstract methods in Java

In Java 6 and earlier, you can't define an abstract static method. For example,

abstract class foo {
    abstract void bar( );        // this is ok
    abstract static void bar2(); // this gives a compile-time error
}

Abstract static methods work fine and are commonly used in many other languages, e.g., @classmethod in Python. Indeed, some methods just don't make sense as instance methods, and it would be much more effective to call directly a static abstract method than creating an instance just for using that abstract method. If Java supported abstract static methods, one could expect that the method (i) must be implemented by subclasses, and (ii) is a class method of the subclass. In Java, however, a static method cannot be inherited or overridden. If a subclass has a static method with the same signature as a static method in the superclass, the former shadows the latter instead of overriding it. (See this document for rules of overriding and shadowing in Java.)
On the other hand, some languages do support static inheritance, just like the way they support instance inheritance. From a syntax perspective, those languages usually require the class name to be included in the statement. For example, in Java, assuming you are writing code in ClassA, where methodA is a static method and there is no instance method with the same signature. Then methodA() and ClassA.methodA() are equivalent statements. In SmallTalk, however, the class name is not optional, so the syntax is (note that SmallTalk does not use the . to separate the "subject" and the "verb", but uses it as the statement terminator): ClassA methodA. Because the class name is always required, the correct "version" of the method can always be determined by traversing the class hierarchy.
Since a Java static method defined in an abstract class would belong to that very class, an abstract static method could not be used anyway. Fortunately, an abstract class can have static fields and static methods starting from Java 7 (see this document). These static members can be invoked with a class reference as you would do with a non-abstract class.