java: maps zoo, what to choose

Question

I'm pretty new to the Java World (since I'm writing primary in C/C++). I'm using maps in my apps. Since java.util.Map is abstract I need to instantiate it's implementation. Usually I use HashMap like:

Map<String, MyClass> x = new HashMap<>();

But in java docs I found many other implementations, like TreeMap, LinkedHashMap, HashTable, etc. I want to know if I can continue blindly using of the HashMap or there are any important differences between those Map implementations.

The brief list of points-to-know will be ok. Thanks.

Answer 1

• 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.

Answer 2

• 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).