HashMap Deep Dive: How Hash Collisions Are Resolved and When Lists Turn into Red‑Black Trees

What HashMap Really Is

HashMap is an array‑based scheduling system that combines a bucket array with a conflict‑resolution mechanism. The core field is transient Node<K,V>[] table;, representing the bucket array.

put() – A Three‑Stage Process

Calling map.put(key, value) triggers three internal actions:

Hash perturbation

int hash = key.hashCode();
hash = hash ^ (hash >>> 16);

This folds high‑order bits into low‑order bits to reduce collision probability.

Bucket index calculation using bitwise AND instead of modulo (capacity must be a power of two): int index = (n - 1) & hash; Insertion logic with three cases:

Empty bucket → place node.

Key already exists → overwrite value.

Collision → attach to a linked list or convert to a red‑black tree.

Hash Collisions – The Performance Divider

A collision occurs when different keys map to the same bucket. In JDK 7 and earlier the bucket remained a linked list, degrading lookup to O(n). Since JDK 8 a bucket whose list length exceeds 8 and whose table capacity is at least 64 is transformed into a red‑black tree, reducing worst‑case lookup to O(log n).

Tree‑ification Conditions

The conversion occurs only when both conditions hold:

if (bucket.size > 8)
if (capacity >= 64)

If the capacity is smaller, the map prefers to resize instead of tree‑ifying.

Resize (Rehash) – The Hidden Cost

Resize is triggered when size > capacity * loadFactor. Default values are capacity = 16 and loadFactor = 0.75, so the map expands after 12 entries. During resize the capacity doubles and every entry is rehashed, a full‑migration step that can cause latency spikes under high concurrency.

get() – Path Dependent on Bucket Structure

The lookup follows three steps: compute hash, locate bucket, then search within the bucket. Complexity varies:

Single node → O(1) Linked list → O(n) Red‑black tree →

O(log n)

Common Pitfalls

Bad hashCode implementation (e.g., always returning 1) forces all keys into one bucket, degrading the map to a linked list with O(n) performance. public int hashCode() { return 1; } Mutable objects as keys change their hash after insertion, making the entry unreachable.

map.put(user, value);
user.setId(100);

Inconsistent equals and hashCode violates the contract that equal objects must have equal hashes, leading to incorrect lookup behavior.

// equals true → hashCode must be equal

Node Structures: List vs. Tree

List node definition:

static class Node<K,V> { final int hash; final K key; V value; Node<K,V> next; }

Tree node definition (extends LinkedHashMap.Entry):

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> left, right, parent; boolean red; }

Impact in Real Systems

In high‑throughput scenarios (e.g., 200 k RPM), poor hash distribution inflates CPU usage, frequent resizing causes latency jitter, and severe collisions drop throughput. Thus HashMap becomes a performance‑critical component.

Practical Example

package com.icoderoad.collection.map;

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>(16, 0.75f);
        map.put("user:1", "Alice");
        map.put("user:2", "Bob");
        System.out.println(map.get("user:1"));
    }
}

File location:

/home/project/src/main/java/com/icoderoad/collection/map/HashMapDemo.java

Conclusion

HashMap is a finely tuned performance‑balancing system composed of an array, linked lists, and red‑black trees. Its efficiency hinges on hash quality, the JDK 8 tree optimization, resize behavior, and conditional tree conversion.