HashMap Performance Improvements in Java 8
A developer-focused look at how Java 8 improved the performance of HashMap under high-collision scenarios, with code examples and practical explanations.
—
Table of Contents
Introduction
Prior to Java 8, java.util.HashMap suffered from performance degradation when many keys hashed to the same bucket (hash collision). In such cases, the bucket was implemented as a linked list, causing lookup time to degrade from O(1) to O(n).
Java 8 introduced a major improvement: buckets with many collisions are now stored as balanced trees (red-black trees) instead of linked lists, improving worst-case performance to O(log n).
The Hash Collision Problem (Pre-Java 8)
- In Java 7 and earlier, each bucket in a
HashMapwas a linked list of entries. - When multiple keys had the same hash code, they were placed in the same bucket.
- As the number of entries in a bucket grew, operations like
get,put, andremovebecame slower (O(n) in the number of entries in the bucket).
Example:
// Many keys with the same hash code
Map<BadKey, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
map.put(new BadKey(i), "value" + i);
}
// Lookup is O(n) for a bucket with many collisions
Java 8 Solution: Tree Bins
- Java 8 introduced a threshold: if a bucket contains more than a certain number of entries, it is converted from a linked list to a balanced tree (red-black tree).
- This reduces the worst-case time complexity for operations in a bucket from O(n) to O(log n).
- When the number of entries in a bucket drops below a lower threshold, it is converted back to a linked list.
- This change applies to
HashMap,LinkedHashMap, andConcurrentHashMap.
Relevant constants:
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
- If a bucket grows beyond 8 entries, it is treeified.
- If it shrinks below 6, it is untreeified.
Thresholds and Behavior
- TREEIFY_THRESHOLD: When a bucket contains more than 8 entries, it is converted to a tree.
- UNTREEIFY_THRESHOLD: When a tree bin shrinks below 6 entries, it is converted back to a linked list.
- Note: Treeification only happens if the overall map capacity is at least 64 (to avoid overhead for small maps).
Code Example:
HashMap<String, String> map = new HashMap<>();
// Add enough colliding keys to trigger treeification
for (int i = 0; i < 20; i++) {
map.put("key" + (i % 4), "value" + i); // Simulate collisions
}
Impact on Iteration Order
- In rare cases, the change to tree bins can affect the iteration order of
HashMapandHashSet. - Important: The iteration order of
HashMapis not specified and should not be relied upon.
Summary
- Java 8 improved
HashMapperformance under high-collision scenarios by using balanced trees for large buckets. - This change improves worst-case performance from O(n) to O(log n) for buckets with many entries.
- The change is transparent to most users, but be aware of possible changes in iteration order.