Java Collections: Different Types of HashMap and comparison

• Comparison 

Features	HashMap	Hashtable
Synchronized	No	Yes
Performance	Faster than Hashtable	Slower than HashMap
NULL	Allowed	Not Allowed (NPE)
Legacy	No	Yes

Features	HashMap	LinkedHashMap	TreeMap
Complexity get, put, containsKey, remove	O(1)	O(1)	O(1)
Iteration Order	Random	As per insertion	As per Comparator or Comparable
NULL keys	Yes	Yes	No
Interface	Map	Map	Map, SortedMap, NavigableMap
Application	Fast Retrieval	LRU Cache	Sorting is required

	Get	ContainsKey	Next	Data Structure
HashMap	O(1)	O(1)	O(h / n)	Hash Table
LinkedHashMap	O(1)	O(1)	O(1)	Hash Table + Linked List
IdentityHashMap	O(1)	O(1)	O(h / n)	Array
WeakHashMap	O(1)	O(1)	O(h / n)	Hash Table
EnumMap	O(1)	O(1)	O(1)	Array
TreeMap	O(log n)	O(log n)	O(log n)	Red-black tree
ConcurrentHashMap	O(1)	O(1)	O(h / n)	Hash Tables
ConcurrentSkipListMap	O(log n)	O(log n)	O(1)	Skip List

• Details

HashMap

1. Insertion order is NOT preserved and stores records based on hashcode of keys

2. Heterogeneous objects are allowed for both - keys & values

3. Only one NULL key is allowed, but as many as NULL values are allowed

4. Is a best choice if frequent operation is search

5. Constructors (Common for all Hash implemented collections)

1. Default (with initialCapacity as 16 and fillRatio: 0.75 i.e. new HashMap will be created when existing one is filled 75%)

2. int initialCapacity = Creates with predefined size = initialCapacity and fillRatio = 0.75

3. int initialCapacity, float fillRatio = Creates with predefined initialCapacity & fillRatio

4. Collections C = convert any collection to HashMap

6. To get synchronized version of HashMap, use 

Map m = new HashMap();

Map m1 = Collections.synchronizedMap(m);

7. For HashMap. JVM uses ‘.equals()’ method to identify duplicate keys, hence in below program, ONLY ONE object will be stored in HashMap as key is duplicate

HashMap m = new HashMap();

Integer i1 = new Integer(10);

Integer i2 = new Integer(10);

m.put(i1, “ganesh”);

m.put(i2, “ashtakar”);

8. For HashMap, if GC finds a key object as null, still GC will not destroy it as it is associated with HashMap. For example, in following case, temp object will NOT be collected by GC

HashMap m = new HashMap();

Team temp = new Temp();

m.put(temp, “ganesh”);

temp = null;

SOP(m); // will print {temp=”ganesh”}

9. put(key, value): On put operation, hashmap calculates the hash value of the key using hashCode() method which returns a number and then calculates the bucket number using “hashcode % (n-1)”, hashCode method if overridden, MUST always return same hashcode for an object

10. In case there is collision i.e. two different objects has same hashcode, equals() method is used to compare KEY objects and decide whether to add new Entry or overwrite existing one

11. In case there is collision where two different objects results in either same or different hashcode value but same bucket number, a LinkedList is formed to store new entry with first entry having address of next entry, following info is available for each of the HashMap Entry

Key

Hashcode 

Value

Next Node

12. Java 8 onwards, if LinkedList size grows beyond threshold i.e. 8, JVM will convert LinkedList to TreeMap (smaller keys & hashcode on left node and greater ones on right nodes), this is faster as it results in binary search which is faster

13. get(key): for get operation, key is again converted to hashcode and then bucket number as mentioned in #9 above, once the bucket is identified, hashcode is compared with the Entry, if it does not match (in case of LinkedList or TreeMap), the next Node Entry will be checked & so on. Once an Entry is found for hashcode, key will be compared using equals method and then Value will be returned

LinkedHasMap

1. Same as HashMap but insertion order is preserved

2. Slower than HashMap as insertion order is preserved

Hashtable

1. Insertion order not maintained, but based on hashcode of key

2. Duplicate keys not allowed, values allowed

3. Heterogeneous objects for keys as well as values are allowed

4. NULL key & values not allowed

5. It is synchronized, hence thread safe

6. Best choice for frequent search operations

7. Constructors (Common for all Hash implemented collections)

1. Default (with initialCapacity as 11 (not 16) and fillRatio: 0.75 i.e. new HashSet will be created when existing one is filled 75%)

2. int initialCapacity = Creates with predefined size = initialCapacity and fillRatio = 0.75

3. int initialCapacity, float fillRatio = Creates with predefined initialCapacity & fillRatio

4. Map M = convert Map to Hashtable

TreeMap

1. Underlying data structure is RED-BLACK tree

2. Insertion order is NOT preserved and it is based on some sorting order of keys

3. Duplicate keys are not allowed but values can be duplicated

4. For default natural sorting order, then keys should be comparable & homogeneous otherwise ClassCastException will be thrown

5. For custom comparator, then keys need NOT be homogeneous & comparable

6. Methods from SorteMap

1. firstKey(): first element in the Map

2. lastKey(): last element in the Map

3. headMap(key): elements less than or equal to ‘key’

4. tailMap(ele): greater than or equal to ‘key’, 

5. subMap(key1, key2): >= key1 and <= key2

6. comparator(): returns null, if natural order is used

7. Constructors

1. Default (default natural sorting order of keys)

2. Comparator C: Customized sorting order defined by comparator object

3. Collections C = convert any collection to TreeMap

4. SortedMap S = convert SortedSet collection to TreeMap

IdentityHashMap

1. Same as HashMap (refer #7 in HashMap) but

2. For IdentityHashMap. JVM uses ‘==’ method to identify duplicate keys, hence in below program, TWO objects will be stored in IdentityHashMap as key is NOT duplicate now

HashMap m = new HashMap();

Integer i1 = new Integer(10);

Integer i2 = new Integer(10);

m.put(i1, “ganesh”);

m.put(i2, “ashtakar”);

WeakHashMap

1. Same as HashMap (refer #8 in HashMap) but 

2. GC dominates WeakHashMap i.e. For WeakHashMap, if GC finds a key object as null, GC will destroy it though it is associated with WeakHashMap. For example, in following case, temp object will be collected by GC

HashMap m = new HashMap();

Team temp = new Temp();

m.put(temp, “ganesh”);

temp = null;

SOP(m); // will print {}

ConcurrentHashMap

1. Implements ConcurrentMap=> Map interface

2. ConcurrentMap methods: putIfAbsent(key, value), remove(key, value), replace(key, oldValue, newValue)

3. Read operation does NOT require lock, any number of threads can perform read operations

4. For Write & Update operations, In normal thread entire collection is LOCKED by one thread, whereas in ConcurrentHashMap locking is at hash BUCKET LEVEL

5. Hence normally if there are 16 buckets, 16 threads can do read/update operations

6. initialCapacity & concurrencyLevel are most of the time same but need not be same e.g. initailCapacity = 16 & concurrencyLevel=8 then there will be 1 lock for 2 buckets, or initailCapacity = 16 & concurrencyLevel=32, lock for each half of the bucket

7. Constructors (Common for all Hash implemented collections)

1. Default (with initialCapacity as 16 and fillRatio: 0.75 i.e. new HashMap will be created when existing one is filled 75%)

2. int initialCapacity = Creates with predefined size = initialCapacity and fillRatio = 0.75

3. int initialCapacity, float fillRatio = Creates with predefined initialCapacity & fillRatio

4. int initialCapacity, float fillRatio, int concurrencyLevel = Creates with predefined initialCapacity & fillRatio & concurrencyLevel

5. Collections C = convert any collection to HashMap