Hash-based Maps in Java: HashTable, HashMap, LinkedHashMap, ConcurrentHashMap, and TreeMap

In the Java Collections Framework, there are several classes for storing key-value pairs. While many are based on the concept of hashing, they differ in implementation details, performance, and use cases. This article provides a brief overview of the core features of HashTable, HashMap, LinkedHashMap, ConcurrentHashMap, and TreeMap.

HashTable vs. HashMap

HashTable and HashMap are two of the most fundamental hash-based key-value collections.

Core Difference: HashTable is thread-safe but has lower performance, whereas HashMap is not thread-safe but offers higher performance.

| Feature | HashTable | HashMap | | :--- | :--- | :--- | | Thread Safety | Thread-safe, methods are synchronized. | Not thread-safe. | | Null Handling| Does not allow null keys or values. | Allows one null key and multiple null values. | | Initial Capacity | Defaults to 11. | Defaults to 16. | | Hashing Algorithm | Directly applies modulo to the hashCode() result. | XORs the upper 16 bits and lower 16 bits of the hashCode(), then applies modulo to reduce hash collisions. | | Resizing Mechanism | Resizes to 2 * old + 1. | Default load factor is 0.75; resizes by doubling when the threshold is reached. |

---

LinkedHashMap

LinkedHashMap extends HashMap, and its main feature is the ability to maintain the insertion order or access order of keys.

Features

• Ordered: Internally uses a doubly-linked list to connect all entries, thus preserving iteration order.
• Data Structure: Array + Linked List/Red-Black Tree + Doubly-Linked List.

Core Use Case: LRU Cache

By setting it to "access order," LinkedHashMap can easily implement an LRU (Least Recently Used) cache. When a new element is added, the least recently accessed element can be quickly removed.

---

ConcurrentHashMap

ConcurrentHashMap is a class in the java.util.concurrent package designed to provide high-performance concurrent read and write capabilities.

Data Structure Evolution

• JDK 7: ReentrantLock + Segment[] + HashEntry

  • Employs segmented locking, dividing the entire hash table into multiple segments (16 by default).
  • Each segment is an independent sub-hash-table, and update operations only need to lock the corresponding segment, improving concurrency.
  • The data structure within each segment is a linked list.

• JDK 8: synchronized + CAS + Node[] + Red-Black Tree

  • Abandons segmented locking in favor of locking the head node of each hash bucket, resulting in finer-grained locks.
  • When the length of a bucket's linked list exceeds a threshold (8 by default), the list is converted into a red-black tree, optimizing lookup time complexity from O(n) to O(log n).
  • The fields of the Node are modified with volatile to ensure memory visibility.

Locking Mechanism

• Read Operations: No locks are used, resulting in very high read performance.
• Write Operations (JDK 8):
  1. If no node exists: Uses CAS (Compare-And-Swap) to attempt to insert a new node.
  2. If a node exists: Uses synchronized to lock the head node, then proceeds with insertion or update.

---

TreeMap

TreeMap is based on a Red-Black Tree implementation, which ensures that the keys are always in a sorted state.

Core Features

• Sorting: Keys are sorted according to their natural order or by a Comparator provided at construction time.
• Performance: Insertion, deletion, and lookup operations have a stable time complexity of O(log n).
• Thread Safety: Not thread-safe.
• Null Handling: Does not allow null keys (because they cannot be compared), but allows null values.

Use Cases

• When a map sorted by keys is required.
• In scenarios requiring frequent additions and deletions to sorted data, it is more efficient than sorting an ArrayList before each operation.