Inside Java HashMap: Arrays, Linked Lists, Red‑Black Trees & JDK 7 vs 8

HashMap Underlying Data Structure

In JDK 7 the underlying structure of HashMap is an array plus linked list . In JDK 8 it becomes an array + linked list + red‑black tree .

HashMap Resizing Mechanism

The initial array capacity is 16, and capacities grow by powers of two to improve performance and enable bit‑wise indexing instead of modulo.

Resizing is triggered when the number of entries reaches 75% of the array size (the default load factor), though a custom load factor can be supplied; values greater than 1 avoid resizing at the cost of higher memory usage.

To resolve collisions, each bucket stores a singly‑linked list. When a list length reaches a threshold (7 or 8), it is transformed into a red‑black tree; when the length shrinks to another threshold (6), the tree is converted back to a list.

Before converting a long list to a tree, the implementation checks whether the array has reached a size of 64; if not, it prefers to resize the array first, which explains the 7‑8 length threshold.

Why Is the Initial Capacity 16?

Reduces hash collisions (2ⁿ, 16 = 2⁴).

Balances efficiency and memory usage; the size should be neither too small nor too large.

Avoids frequent resizing caused by a too‑small allocation.

Prevents wasteful memory consumption from an overly large allocation.

Why Does HashMap Expand by Powers of Two?

HashMap computes the bucket index with (n - 1) & hash. When the capacity n is a power of two, n‑1 consists of all 1‑bits, allowing the bit‑wise operation to distribute hashes uniformly and avoid extra modulo operations.

Why Is the Load Factor 0.75?

A load factor of 1.0 would delay resizing until the table is full, leading to many collisions and degraded lookup performance. A very low load factor (e.g., 0.5) reduces collisions but wastes memory. The default 0.75 offers a practical trade‑off between space utilization and collision probability, keeping linked‑list or tree heights low.

Does HashMap Recalculate Hash Values After Resizing?

In JDK 7, all keys recompute their hash values and are placed into the new array.

In JDK 8, a new array is created and entries are transferred. Each entry’s new position is determined by e.hash & oldCap:

If the result is 0, the entry stays at the same index.

If the result is non‑zero, the entry moves to oldIndex + oldCap.

Why Convert a Bucket to a Red‑Black Tree When Its Length Reaches 8?

If the hash function distributes keys well, long chains are extremely rare (probability around 0.00000006 for length 8). Therefore, conversion to a tree occurs only when the chain becomes unusually long, providing O(log n) performance for those buckets.

Why Is HashMap Not Thread‑Safe and How to Fix It?

In JDK 7, concurrent resizing can cause infinite loops and data loss because the transfer uses head insertion.

In JDK 8, concurrent put operations may overwrite each other when two threads compute the same hash and insert into a null bucket simultaneously.

Solutions include using Hashtable (lower performance), ConcurrentHashMap (commonly used), or wrapping a map with Collections.synchronizedMap() .

Why Did JDK 7 Use Head Insertion While JDK 8 Switched to Tail Insertion?

JDK 7’s resize() inserted new nodes at the head of each bucket to avoid traversing to the tail, which is more efficient for a simple list.

JDK 8 changed to tail insertion to prevent the dead‑loop issue that head insertion could cause in multithreaded resizing scenarios.

How Does HashMap Resolve Hash Collisions?

HashMap uses the chaining method (linked lists). When a bucket’s chain length reaches 8, it is transformed into a red‑black tree; when the length drops to 6 or less, it reverts to a linked list.

Additional optimizations in JDK 8 include:

Replacing Entry with Node<K,V>.

Eliminating the indexFor function and using (n‑1) & hash directly.

After resizing, each element either stays at its original index or moves to originalIndex + oldCapacity, preserving list order.

Tail insertion ensures the new bucket’s list order matches the old one, avoiding reversal and dead loops in multithreaded contexts.