How HashMap Works Inside

Why this matters

• This is the most asked internals question in Java interviews, and the answer touches hashing, collisions, tree conversion and resizing in one coherent story.
• The failure modes are real: a poor hashCode turns O(1) lookups into O(n) scans, and a mutable key loses data.
• Understanding resize cost is what makes pre-sizing a map feel obvious rather than pedantic.

The structure

Finding the bucket

Three steps turn a key into an array index.

// 1. The key's own hash code
int raw = key.hashCode();

// 2. Spreading: mix the high bits down into the low bits
int hash = raw ^ (raw >>> 16);

// 3. Index: a mask, equivalent to hash % length but far cheaper
int index = hash & (table.length - 1);

Step 3 is the reason the table length is a power of two. For length 16, length - 1 is 0b1111, so the mask keeps the lowest four bits — exactly a modulo, computed as a single bitwise AND.

Step 2 exists because of step 3. Masking only looks at the low bits, so two keys differing only in their high bits would collide every time. XOR-ing the top 16 bits down mixes that information into the part that is actually used.

put, step by step

map.put("apple", 10);

The hash comparison before equals is a deliberate optimisation: comparing two int values is far cheaper than calling equals, and unequal hashes guarantee unequal keys.

get, step by step

map.get("apple");

Compute the index the same way, then walk the chain comparing hash and key. Found means return the value; exhausting the chain means return null. For a treeified bucket the walk becomes a binary search.

With a good hash the chain holds one node, which is where O(1) comes from. With every key colliding the chain holds all n, which is the O(n) worst case.

Treeification

Java 8 added a defence against long chains.

Resizing

When size exceeds capacity × 0.75, the table doubles and every entry is redistributed.

Doubling the length adds exactly one bit to the mask, which gives a neat property: an entry either stays at its current index or moves to index + oldCapacity. Nothing else is possible, so Java 8 splits each chain into a "stay" list and a "move" list in one pass, preserving relative order.

// 16 → 12 entries triggers a resize to 32
// 32 → 24 entries triggers a resize to 64
// Each resize is O(n) over the current contents

Map<String, Integer> sized = new HashMap<>(1334);      // 1000 entries, never resizes
Map<String, Integer> modern = HashMap.newHashMap(1000); // Java 19+, same effect

Why the hashCode contract matters here

class BadKey {
    final String value;
    BadKey(String value) { this.value = value; }

    @Override public boolean equals(Object o) {
        return o instanceof BadKey k && value.equals(k.value);
    }
    @Override public int hashCode() {
        return 1;                  // legal, and catastrophic
    }
}

Every key hashes to 1, so every entry lands in one bucket. The map degenerates into a single chain — O(n) for every operation, with the memory overhead of a hash map and none of the speed. Treeification limits the damage to O(log n), but the structure is still doing far more work than a plain list would.

The other direction is equally broken:

// equals says these are equal, hashCode says they belong in different buckets
// → put stores two entries for the "same" key, get finds neither reliably

null handling and the family

HashMap<String, String> map = new HashMap<>();
map.put(null, "allowed");           // exactly one null key, stored in bucket 0
map.put("key", null);               // any number of null values

A null key cannot be hashed, so it is special-cased to index 0.

Common misreadings

• "HashMap is O(1), full stop." It is O(1) average with a good hash. The worst case is O(log n) since Java 8, and was O(n) before.
• "The table length can be any number." It is always a power of two, which is what makes the masking trick work.
• "Treeification happens at 8 entries in the map." At 8 nodes in a single bucket, and only once the table is at least 64 long.
• "Resizing rehashes every key." The stored hash is reused; only the index is recomputed, and the split is a single pass.
• "Java 8 made HashMap thread-safe." It removed one specific livelock. Concurrent writes are still unsafe.
• "hashCode must be unique." It must be well distributed. Collisions are expected and handled.
• "A null key throws." HashMap permits one; ConcurrentHashMap and TreeMap do not.