Stage 4: HashMap internals, lesson 12 of 13

HashMap internals 12: Java 7 vs Java 8+

Advanced3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

HashMap was largely rewritten in Java 8. The differences show up in interviews and explain old production incidents:

  • Buckets: Java 7 used linked lists only; Java 8 uses lists that become red-black trees when crowded.
  • Insertion: Java 7 added new nodes at the head of a list; Java 8 adds them at the tail.
  • Resizing: Java 7 recalculated every index and reversed each list while moving it; Java 8 splits each bucket into lo and hi lists and keeps the order.
  • Hash spreading: Java 7 mixed bits with several shifts and XORs; Java 8 does a single h ^ (h >>> 16), because trees now handle the bad cases.
  • The infinite loop: in Java 7, two threads resizing at once could link a bucket into a cycle, and a later get() would spin at 100% CPU forever. Java 8's order-preserving resize avoids that cycle, but HashMap is still not thread-safe: concurrent writes lose updates and can corrupt the map. Use ConcurrentHashMap.
HashMap lab

Example

Java
// Still true in Java 8+: HashMap is NOT thread-safe
Map<Integer, Integer> map = new HashMap<>();
Thread t1 = new Thread(() -> { for (int i = 0; i < 50_000; i++) map.put(i, i); });
Thread t2 = new Thread(() -> { for (int i = 50_000; i < 100_000; i++) map.put(i, i); });
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(map.size());   // often less than 100000: updates were lost

Map<Integer, Integer> safe = new ConcurrentHashMap<>();   // the fix

Old way vs new way

Java 7
// Java 7: new entries go to the HEAD of the bucket
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K, V> first = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, first);
}
Java 8+
// Java 8+: new nodes go to the TAIL (inside putVal)
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);
        break;
    }
    p = e;
}

Common mistake

Believing Java 8 made HashMap thread-safe because the infinite-loop bug is gone. Concurrent writes still lose data.

Under the hood

Java 8 also added the Map default methods that make HashMap pleasant to use: getOrDefault, putIfAbsent, computeIfAbsent, computeIfPresent, compute, merge, forEach and replaceAll. Some Java 7 updates also briefly had an optional "alternative hashing" for String keys, which was removed in Java 8 once tree buckets made it unnecessary.

Check yourself

Where does Java 7's HashMap insert a new node in a bucket?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.