Java Map Implementations Compared

1. HashMap 1.7 vs HashMap 1.8

	HashMap 1.7	HashMap 1.8
Data structure	Array + linked list	Array + linked list + red-black tree
Head insertion or tail insertion in the linked list when collisions occur	Head insertion	Tail insertion

• In 1.7, for a key, its hash value is calculated first and then modulo the array size is used to determine which element it should be placed in. Collisions are then resolved using separate chaining. If many keys map to the same element, efficiency degrades to O(N). Therefore, in 1.8, when the linked list exceeds a threshold, it is converted into a red-black tree, with O(log N) efficiency.
• In 1.7, when two threads perform put and resize at the same time, a circular linked list may occur, so a get operation may enter an infinite loop.

2. HashMap vs Hashtable

	HashMap	Hashtable	ConcurrentHashMap 1.7	ConcurrentHashMap 1.8
Thread-safe	No	Yes	Yes	Yes
Can key/value be null	Both key and value can be null	Neither key nor value can be null	Neither key nor value can be null	Neither key nor value can be null
How thread safety is implemented	/	Each method is synchronized	Segmented locks	synchronized + CAS

• Hashtable, ConcurrentHashMap 1.7, and ConcurrentHashMap 1.8 all improve concurrency by reducing lock granularity.
  • Hashtable adds synchronized before each method. You cannot write while reading, and you cannot read while writing.
  • ConcurrentHashMap 1.7 uses an array + array + linked-list structure. It divides the entire map into multiple segments. When multiple threads read and write the same segment, they need to block and wait for the lock. Reading and writing different segments does not require blocking and waiting for the lock.
  • ConcurrentHashMap 1.8 removes segments and changes the granularity to locking the linked-list head of each element. If the head is empty, it uses a CAS operation; otherwise it uses synchronized.

3. TreeMap vs LinkedHashMap vs HashMap

	HashMap	LinkedHashMap	TreeMap
Data structure	Array + linked list + red-black tree	HashMap + doubly linked list	Red-black tree
Ordered during traversal	Unordered	Traversal follows the insertion order of keys	Traversal follows the order defined by the key’s compareTo method