library
advancedHashMap Internals: Hashing, Buckets & Treeification
Understand how HashMap works internally — hashing, collision handling, and the Java 8 treeification optimization.
HashMap<K,V> is Java's most-used Map. Understanding its internals helps avoid performance pitfalls.
HashMap = a post office with numbered P.O. boxes (buckets). The hashCode is your zip code — it determines which box your mail goes into. If two letters have the same zip (collision), they stack up in the same box. Treeification = upgrading a large stack to an organized filing system.
Key Concepts
1
Structure: an array of buckets (Node<K,V>[]). Default initial capacity: 16. Load factor: 0.75 (resize at 75% full).
2
Put operation:
1. Compute hash: key.hashCode() → spread bits (hash ^ hash >>> 16)
2. Compute bucket index: hash & (capacity - 1)
3. If bucket is empty: insert new Node
4. If bucket has entries: traverse linked list, check key equality
- If key found: replace value
- If key not found: append to list
3
Java 8 treeification: when a bucket's linked list exceeds 8 entries (TREEIFY_THRESHOLD), it converts to a balanced red-black tree. Lookup goes from O(n) to O(log n) for that bucket. Converts back to list when entries drop below 6 (UNTREEIFY_THRESHOLD).
4
Resize: when size > capacity × loadFactor, the array doubles. All entries are rehashed — O(n) operation. Choose initial capacity wisely to avoid unnecessary resizes.
5
Capacity is always a power of 2: allows bitwise AND (hash & (capacity - 1)) instead of modulo (hash % capacity) — faster.
6
hashCode() contract: equal objects MUST have equal hash codes. Unequal objects SHOULD have different hash codes (for performance).