Unlocking Java HashMap: Deep Dive into Auto‑Resizing, Hashing, and Concurrency

1. Automatic Resizing

Resizing is triggered in putVal when the size exceeds the pre‑computed threshold; the resize method doubles the bucket array and recalculates the new threshold.

Three cases are handled during resizing:

Single element in a bucket (no collision) – the element is copied directly.

Tree node in a bucket – red‑black tree resizing is performed.

Normal node list – a high‑low linked list assists the expansion to avoid dead‑link issues present in earlier JDK versions.

Example code demonstrates how a small initial capacity quickly forces a resize, emphasizing the importance of sizing the map appropriately.

2. Initialization & Lazy Loading

HashMap creates only the load factor initially; the actual bucket array is allocated on the first put via resize(), which sets the default capacity to 16 and the threshold to 12.

HashMap hashMap = new HashMap(2);
hashMap.put("1", 1);
hashMap.put("2", 2);
hashMap.put("3", 3);

3. Hash Computation

Instead of using the raw hashCode(), HashMap applies a perturbation function: h = key.hashCode() ^ (key.hashCode() >>> 16). This mixes high bits into low bits, reducing collisions. The same logic appears in ConcurrentHashMap.

Illustrative binary examples show how the function differentiates keys that would otherwise collide.

4. Bitwise Operations

The method tableSizeFor(int cap) finds the smallest power‑of‑two greater than or equal to cap using a series of bitwise OR and shift operations, ensuring efficient index calculation via hash & (n‑1).

int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

5. Concurrency Evolution

HashTable uses a single synchronized lock (pessimistic locking). Pre‑JDK 8 ConcurrentHashMap introduced segment locks to reduce lock granularity. JDK 8 abandoned segments, adopting optimistic locking with synchronized plus CAS, leveraging Unsafe for low‑level memory access.

Key methods such as tabAt and casTabAt illustrate how volatile semantics and CAS ensure visibility and atomicity without coarse‑grained locks.

6. Concurrent Summation (CounterCell)

CounterCell

(the basis of LongAdder) enables high‑throughput counting by distributing increments across cells indexed by thread‑local probes. The fullAddCount method shows a loop with three branches (A, B, C) handling initialized cells, initialization, and fallback to a base counter, respectively, and includes lock‑free expansion logic.

private final void fullAddCount(long x, boolean wasUncontended) { /* ... */ }

Conclusion

The article covers most of the essential features of Java Map implementations, providing a practical understanding of how automatic resizing, lazy initialization, hash perturbation, bitwise sizing, and evolving concurrency strategies work together in real‑world Java development.