How HashMap Works Internally in Java

HashMap is probably the most used data structure in Java, and "how does it work internally?" is one of the most asked Java interview questions. Let's build the mental model step by step.

The big idea: an array of buckets

Internally, a HashMap is an array. Each slot is called a bucket. To store a key, the map turns the key into an array index — so lookup is a direct jump instead of a search.

Step 1: hashCode()

Every Java object has a hashCode() that returns an int. For "apple", it's computed from the characters.

Step 2: Spreading the hash

HashMap mixes the high bits into the low bits:

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

Why? The index uses only the lowest bits, so without this step keys whose hash codes differ only in high bits would all collide.

Step 3: Hash to index

The array length is always a power of two, so the index is a cheap bitwise AND instead of a modulo:

int index = hash & (table.length - 1);

Collisions

Two different keys can land in the same bucket. The bucket then holds a linked list of entries. On get, the map walks that list and uses equals() to find the exact key.

map.put("Aa", 1);
map.put("BB", 2); // "Aa".hashCode() == "BB".hashCode() == 2112

Both go into the same bucket; equals tells them apart.

Treeification (Java 8+)

A long list turns lookups into O(n). Since Java 8, when a single bucket holds more than 8 entries (and the table has at least 64 buckets), the list is converted into a red-black tree, making the worst case O(log n). If it shrinks to 6 or fewer, it turns back into a list.

Resizing

The map tracks its load factor (default 0.75). When size > capacity × 0.75, the array doubles and every entry is redistributed.

Because capacity doubles, each entry either stays at the same index or moves to index + oldCapacity — Java checks a single bit to decide, so resizing is cheaper than rehashing from scratch.

Why equals() and hashCode() must agree

The contract: if a.equals(b), then a.hashCode() == b.hashCode(). Break it and the map looks in the wrong bucket:

class Point {
    int x, y;
    @Override public boolean equals(Object o) { /* compares x and y */ }
    // forgot hashCode()!
}
 
map.put(new Point(1, 2), "A");
map.get(new Point(1, 2)); // null — different default hash codes

Records generate both correctly — another reason to use them for keys.

Quick reference

Interview-ready summary

• A HashMap is an array of buckets; the key's spread hash picks the bucket.
• Collisions are stored as a list, converted to a red-black tree after 8 entries.
• The table doubles when size exceeds capacity × load factor (0.75).
• equals and hashCode must be consistent, and keys should be immutable.
• HashMap is not thread-safe — use ConcurrentHashMap for concurrent access.