Analysis of JDK 1.8 HashMap Implementation Compared to JDK 1.7

JDK 1.8's HashMap implementation differs significantly from JDK 1.7. The article examines the core logic of the put and get methods, focusing on how the map is initialized during the first put operation.

The putVal method follows these steps:

If the internal array is not yet initialized (length 0), it is created.

The key's hash is computed using the hash method to determine the target bucket.

If the bucket is empty, the new entry is placed directly.

If the bucket contains a red‑black tree, the entry is inserted into the tree.

If the bucket contains a linked list, the list is traversed; a matching key replaces the existing value, otherwise the new node is appended.

If the linked list length reaches 8, it is transformed into a red‑black tree.

Retrieval follows a similar process: compute the hash to locate the bucket, check the first node, and if necessary, traverse the linked list or search the tree.

Resizing moves all entries from the old array to a new, larger array.

Summary

1. HashMap is built on an array combined with doubly‑linked lists and red‑black trees.

2. Insertion first computes the key's hash to find the bucket.

3. An empty bucket receives a new Node directly.

4. If the bucket is occupied, entries are compared by hash and key equality; matching keys replace the old value.

5. When the bucket holds a red‑black tree, the tree is searched and updated accordingly.

Key Points

JDK 1.8 introduces several changes compared to JDK 1.7:

Red‑black trees are used for buckets with many collisions, which did not exist in JDK 1.7.

New entries are appended to the tail of the linked list, whereas JDK 1.7 inserted at the head.

Resizing in JDK 1.8 avoids the dead‑loop issue that could occur in JDK 1.7, and the linked list order is preserved.