java: maps zoo, what to choose

  • Never bother with Hashtable, it's a relic from Java 1.0;
  • HashMap is the universal default due to O(1) lookup and reliance only on equals and hashCode, guaranteed to be implemented for all Java objects;
  • TreeMap gives you sorted iteration over the map entries (plus a lot more—see NavigableMap), but requires a comparison strategy and has slower insertion and lookup – O(logN) – than HashMap;
  • LinkedHashMap preserves insertion/access order when iterating over the entries.

SortedMap implementations offer some great features, like headMap and tailMap. NavigableMap implementations offer even more features with terrific performance for operations that assume sorted keys.

Further out there are java.util.concurrent map implementations, like ConcurrentHashMap, which offer great concurrent performance and atomic get/put operations.


  • HashMap use it almost all the time. Note that your object need have proper implementation of equals and hashCode methods. Does not save insertion order.
  • HashTable don't use it never.
  • LinkedHashMap the same as HashMap but saves insertion order. Large overhead.
  • TreeMap support natural ordering. But insertion works in O(logn).

  • Hashtable is the thread safe version of HashMap, you shouldn't use it anymore. instead you should use ConcurrentHashMap which is a new implementation of a thread safe map
  • TreeMap is mostly use when you want to sort your keys, it implements the SortedMap interface. The put/get performance is O(logn).
  • ConcurrentSkipListMap is used if you need a thread safe SortedMap
  • LinkedHashMap is used when you want to iterate on keys in the insertion order

I mostly use HashMap or ConcurrentHashMap if I need it to be thread safe