HashMap, TreeMap, LinkedMap Comparison16 Feb 2014
Java has different implementations of Map interface: HashMap, TreeMap, LinkedHashMap, HashTable. Each implementation has its pros and cons which should be considered wisely while deciding data structure for your objects. Here is the summary of major differences:
1. If you add (7,1,3) to both LinkedHashMap and TreeMap, then ForEach on LinkedHashMap will return (7,1,3), but TreeMap will return (1,3,7).
- LinkedHashMap is great for implementing LRU Cache as it provides RemoveEldestEntry() method.
- In an Empty TreeMap, first null key is allowed, but adding more than one will throw error. In a non-Empty TreeMap, null keys are not allowed.
- When you call map.put(Key, Value), HashCode of object Key is retrieved and passed to hashing function to find an appropriate bucket location. It might be possible that two objects have same hashcode and results in a collision. However Hashmap stores both Key and Value in bucket (or LinkedList). In case of collision, we check for same keys – keys.equals() method (not their hashcode) in same bucket.
- Immutable objects like String, int or custom immutable objects are best suitable for keys.
- HashTable: is an obsolete class and should not be used. Use HashMap if thread-safe implementation is not required otherwise use ConcurrentHashMap.
- For TreeMap it is necessary to provide elements which implements comparable interface or you need to provide Comparator interface. Failing to do that will throw ClassCastException.
- Priority Queue: An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects - Java docs