Java HashMap Internal Working Explained

To understand the java hashmap internal working, start with what happens when you call map.put("key", value). The HashMap does not store entries in a linear list. It computes a bucket index from the key's hash code and stores the entry in an internal array of nodes. This mechanism determines lookup speed, memory usage, and behavior under collisions.

The Bucket Array and the Hash Function

A HashMap maintains an array of Node<K,V> objects, often called the table or bucket array. The array length is always a power of two, starting at 16 by default. When you call put(key, value), the HashMap first computes key.hashCode(), then applies a secondary hash function that spreads the bits:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

The ^ (h >>> 16) step mixes the high bits into the low bits. This matters because the bucket index is computed as (n - 1) & hash, where n is the table length. If the table length is small, only the low bits of the hash are used. Without the spread, keys that differ only in high bits would collide into the same bucket.

The index calculation uses bitwise AND rather than modulo because the table length is a power of two. This is faster than hash % n and produces the same result when n is a power of two.

Collision Handling: From Linked List to Tree

When two keys map to the same bucket index, a collision occurs. The HashMap stores colliding entries in a linked list within that bucket. Each Node has a next pointer, so the bucket becomes a singly linked list of entries.

In Java 8 and later, insertion appends to the end of the list, and lookup traverses the list comparing keys with equals(). If a bucket's linked list grows beyond 8 nodes, the HashMap converts it to a red-black tree. This conversion exists because linked-list lookup is O(n) in the worst case, while a red-black tree lookup is O(log n). The tree conversion only happens when the table size is at least 64; otherwise, the HashMap resizes first.

// Simplified bucket structure after tree conversion
// Bucket index 5 now holds a TreeNode root
// TreeNode extends LinkedHashMap.Entry, which extends Node

The tree is converted back to a linked list when the bucket shrinks below 6 nodes during removal or resizing.

Resizing and the Load Factor

The HashMap resizes when the number of entries exceeds capacity * loadFactor. The default load factor is 0.75, and the default capacity is 16, so the first resize happens at 12 entries.

When resizing, the HashMap doubles the table length and rehashes all entries into the new table. The new index for each entry is either the same or the old index plus the old capacity. This follows from the power-of-two table length: a new bit in the hash becomes significant.

// Old table length 16, new table length 32
// Entry with hash 0b...101 stays at index 5
// Entry with hash 0b...1101 moves to index 5 + 16 = 21

Choosing the initial capacity matters. If you know you will store many entries, constructing the HashMap with a capacity that avoids resizing reduces rehash overhead. The formula capacity = (expectedSize / loadFactor) + 1 is a common heuristic.

Performance Characteristics and Tradeoffs

The average case for get, put, and remove is O(1), assuming a well-distributed hash function. The worst case is O(log n) for a tree bucket, or O(n) if the bucket remains a linked list.

The real performance risk is a poor hashCode() implementation. If all keys return the same hash code, every entry lands in one bucket. The HashMap degrades to a single linked list or tree, and operations become O(n) or O(log n).

// A pathological key class
public class BadKey {
    @Override
    public int hashCode() {
        return 42; // All keys collide
    }
}

This is not a theoretical concern. Hash-based collections are only as good as their hash function. A well-designed key class should distribute hash codes evenly across the integer range.

The hashCode and equals Contract

HashMap relies on both hashCode() and equals(). The contract is:

• If two objects are equal according to equals(), they must have the same hashCode().
• If two objects have the same hash code, they are not necessarily equal.

When you mutate a key after inserting it into a HashMap, the stored hash no longer matches the key's current hash code. The entry becomes unreachable by lookup, even though it remains in the map. This is why keys in a HashMap should be immutable.

Map<List<String>, String> map = new HashMap<>();
List<String> key = new ArrayList<>();
key.add("a");
map.put(key, "value");
key.add("b"); // Mutation after insertion
System.out.println(map.get(key)); // null

Concurrency and Null Handling

HashMap is not thread-safe. Concurrent modification from multiple threads can corrupt the internal structure, cause infinite loops during resizing (in older Java versions), or lose entries. Use ConcurrentHashMap when multiple threads access the map.

HashMap allows one null key and any number of null values. The null key is stored at bucket index 0 with a special hash value of 0.

Choosing Capacity and Load Factor in Practice

The default load factor of 0.75 balances space usage against lookup speed. A lower load factor reduces collisions but wastes memory. A higher load factor saves memory but increases collision probability.

For most applications, the defaults are appropriate. Adjust them only when you have measured a specific problem, such as excessive resizing during startup.