HashMap Internals

The Big Picture

HashMap is a hash table - array of buckets with chaining.

• Fast O(1) lookups by computing index from key hash
• Handles collisions with linked lists (or trees)
• Grows automatically when load factor exceeded
• Understanding internals helps debug performance

Key to many algorithms: caches, indexes, deduplication.

How It Works

1. Call key.hashCode(), then spread: h ^ (h >>> 16) 2. Index: spread & (capacity - 1) 3. Check bucket, use equals() to find key 4. Collision? Chain entries in linked list 5. Chain > 8 AND table ≥ 64: treeify to red-black (else resize) 6. Rehash when size > capacity * 0.75

In the Java Landscape

Internals evolved over Java versions:

• Java 7: linked list chaining only
• Java 8+: tree bins for long chains (better worst-case)
• Default capacity: 16, load factor: 0.75
• ConcurrentHashMap uses CAS for concurrency (Java 8+)
• Understanding helps choose initial capacity

Pitfalls and Best Practices

• Bad hashCode() causes collisions - degrades to O(n)
• Override hashCode() and equals() together always
• Immutable keys prevent broken lookups
• Pre-size: new HashMap<>((int)(expected / 0.75f) + 1)
• Don't rely on iteration order - use LinkedHashMap