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 onequals
andhashCode
, guaranteed to be implemented for all Java objects;TreeMap
gives you sorted iteration over the map entries (plus a lot more—seeNavigableMap
), but requires a comparison strategy and has slower insertion and lookup – O(logN) – thanHashMap
;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 ofequals
andhashCode
methods. Does not save insertion order.HashTable
don't use it never.LinkedHashMap
the same asHashMap
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