How Java HashMap Handles Collisions and Time Complexity: Separate Chaining Explained

Java's HashMap resolves collisions using separate chaining with linked lists, automatically converting chains longer than 8 entries into red-black trees to improve worst-case lookup time from O(N) to O(log N) while maintaining O(1) average-case performance.

The HashMap implementation is a cornerstone of Java's Collections Framework, and understanding its collision handling mechanics is essential for writing high-performance applications. According to the Snailclimb/JavaGuide repository's detailed source code analysis, the class employs a dynamic structure that adapts between linked lists and balanced trees based on collision density. This article examines the internal mechanisms described in the documentation to explain exactly how the JDK optimizes for both speed and memory efficiency.

Collision Resolution Strategy: Separate Chaining

Java's HashMap stores entries in an array of buckets, where each bucket acts as a container for key-value pairs that share the same hash index. When multiple keys map to the same bucket index—a scenario known as a collision—the implementation must maintain these entries without overwriting data.

Hash Distribution and Bucket Indexing

The bucket index is calculated using a hash-spreading (扰动) function combined with a bitmask operation. As documented in [docs/java/collection/hashmap-source-code.md](https://github.com/Snailclimb/JavaGuide/blob/main/docs/java/collection/hashmap-source-code.md) at line 23, the index is determined by (n-1) & hash, where n is the table length and hash is the processed hash code of the key. This bit manipulation ensures uniform distribution across the array while avoiding expensive modulo operations.

Linked List Chaining

When collisions occur, HashMap uses the separate-chaining (拉链法) technique. Each bucket holds a reference to the head of a linked list containing Node objects that share the same index. New entries are appended to this list, creating a chain of colliding keys. The repository notes at line 23 that this structure allows the map to handle unlimited collisions, though traversal time increases linearly with chain length.

Treeification: From Linked List to Red-Black Tree

Since JDK 1.8, the implementation includes a critical optimization to prevent performance degradation from excessive collisions. When a chain's length reaches the tree-ification threshold of 8, and the table capacity is at least 64, the linked list is converted into a red-black tree. This transformation, detailed at lines 23-24 of the source analysis, changes the search complexity from O(N) to O(log N) for that specific bucket. If the table is smaller than 64 entries, the map prefers to resize rather than treeify, prioritizing memory efficiency over tree structure overhead. The default expectation of approximately 8 collisions at standard load factor is explicitly mentioned in the documentation at line 57.

Time Complexity Analysis

The performance characteristics of HashMap operations depend heavily on hash distribution quality and the internal structure of individual buckets.

Operation	Average Case	Worst Case
get() / put() / remove()	O(1) – Constant time hash lookup with minimal list traversal	O(N) for linked-list buckets; O(log N) after treeification
Resize / Rehash	O(N) – Linear time to redistribute all entries	O(N)

With a well-distributed hash function, operations execute in constant time because the number of entries per bucket remains small. The red-black tree fallback ensures that even pathological cases—where all keys collide due to poor hash codes—maintain logarithmic rather than linear search times.

Practical Implementation Examples

The following examples demonstrate average-case usage and the treeification behavior under forced collisions:

// Standard usage with O(1) average-case operations
Map<Integer, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put(i, "value" + i);   // Constant-time insert
}
System.out.println(map.get(500)); // Constant-time lookup

// Forcing collisions to trigger treeification
Map<Integer, String> map = new HashMap<>(2, 0.75f); // Small initial capacity
for (int i = 0; i < 20; i++) {
    // Keys designed to collide in the same bucket
    map.put(i, "v" + i);
}
// After 8+ collisions, the bucket converts to a red-black tree
System.out.println(map.get(15)); // Logarithmic-time lookup

Summary

• Separate chaining resolves collisions by storing colliding entries in linked lists within each bucket of the underlying array.
• Treeification converts linked lists to red-black trees when chains exceed 8 entries and table capacity is ≥ 64, improving worst-case lookup from O(N) to O(log N).
• Average-case time complexity remains O(1) for get, put, and remove operations under normal hash distribution.
• Resize operations occur in O(N) time when the load factor threshold is exceeded, redistributing entries into a larger array.

Frequently Asked Questions

What is the default threshold for converting linked lists to trees in HashMap?

The default tree-ification threshold is 8. When a bucket's chain reaches this length and the table capacity is at least 64, the linked list transforms into a red-black tree. If the capacity is below 64, HashMap resizes the table instead to avoid the memory overhead of tree structures for small datasets.

Why does HashMap use red-black trees instead of AVL trees for collision handling?

Red-black trees are preferred because they offer faster insertion and deletion operations compared to AVL trees, with less restructuring required during modifications. While both guarantee O(log N) lookup time, red-black trees provide better performance for the write-heavy workloads typical in HashMap operations, balancing the tree less strictly than AVL trees.

What is the worst-case time complexity for HashMap get() and put() operations?

Without treeification, the worst-case complexity is O(N) when all keys collide and form a single long linked list. After treeification triggers, the worst-case improves to O(log N) due to the red-black tree structure. The average case remains O(1) assuming a good hash function.

How does HashMap determine which bucket a key belongs to?

HashMap calculates the bucket index using the formula (n - 1) & hash, where n is the table length (always a power of two) and hash is the key's hash code after applying a hash-spreading function. This bitwise AND operation replaces modulo arithmetic for performance efficiency, as documented in the Snailclimb/JavaGuide analysis.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}