mediumConceptEntryMidSenior

How does HashMap work internally, and what happens when it resizes?

HashMap stores entries in an array of buckets indexed by a hash of the key; collisions chain into a linked list that converts to a red-black tree past a threshold, and exceeding the load factor triggers a resize that reallocates and redistributes every entry. It also connects collections to the point an interviewer is testing.

3 min readUpdated 2026-08-15

Short answer

HashMap works by hashing the key to choose a bucket, then comparing keys with equals() inside that bucket. Collisions are stored as a linked list and can treeify in Java 8+, while resizing doubles capacity and redistributes entries, so bad hashCode/equals or missing initial capacity shows up as lookup and resize cost.

Practice answering out loud

What the interviewer is scoring

Whether you know the bucket-array-plus-collision-chain structure, not just the public API
Whether you can state the equals and hashCode contract and why violating it breaks lookups
Whether you understand that resize is O(n) and therefore why initial capacity matters
Whether you volunteer thread-safety limitations without being asked

You have 2 more free pages. Create a free account for unlimited access.

Was this answer helpful?

Likely follow-ups

Why is the default capacity 16 and the load factor 0.75?
What breaks if a key object is mutated after being inserted?
How does ConcurrentHashMap achieve thread safety without locking the whole map?
Why did Java 8 introduce treeification, and what problem did it solve?

Related Topics

#collections #hashing #data-structures

The structure

A HashMap holds an array of buckets, referred to internally as the table. Inserting a key computes hashCode(), applies a supplemental spreading function that XORs the high bits into the low bits, and takes the low bits of the result to pick a bucket index. That spreading step exists because the index is derived with a bitmask rather than a modulo, so without it two keys differing only in their high bits would collide constantly.

When two keys land in the same bucket, the entries are chained. Up to eight entries in one bucket the chain is a singly linked list, and lookup within it degrades to a linear scan. Past that threshold, and provided the table is at least 64 slots, the chain converts into a red-black tree so worst-case lookup for that bucket becomes O(log n) rather than O(n). This treeification was added in Java 8 specifically to blunt hash-collision denial-of-service attacks, where an attacker submits keys engineered to collide.

The equals and hashCode contract

Lookup is a two-step process: find the bucket by hash, then walk the chain comparing with equals(). Both steps must agree for the map to work. If two objects are equals() but return different hash codes, they will usually be placed in different buckets and the map will contain what looks like a duplicate key. If the hash codes agree but equals() does not, you will insert a value and never retrieve it.

This is also why mutating a key after insertion is a genuine bug rather than a stylistic concern. The entry stays in the bucket determined by the old hash, but lookups now compute the new hash and search the wrong bucket, so the entry becomes unreachable while still consuming memory.

Resizing

The map tracks a threshold equal to capacity times the load factor, 0.75 by default. Exceeding it doubles the table and redistributes every existing entry, which is an O(n) operation. Java 8 improved the mechanics: because capacity is always a power of two and the index is a bitmask, an entry either stays at its current index or moves to index + oldCapacity, so a chain can be split into two without rehashing each key.

The practical consequence is that a map you know will hold ten thousand entries should be constructed with an explicit initial capacity. Left at the default it will resize roughly ten times on the way there, and each resize touches every entry inserted so far.

// Repeatedly resizes: 16 -> 32 -> 64 -> ... while filling. Map<String, User> lazy = new HashMap<>(); // Sized once. The /0.75f accounts for the load factor so the // threshold is not hit at exactly the expected element count. Map<String, User> sized = new HashMap<>((int) (10_000 / 0.75f) + 1);

Thread safety

HashMap is not synchronised, and the failure mode is worse than lost updates. Concurrent writes during a resize could, before Java 8, produce a circular chain that made a subsequent get() spin forever. Java 8 removed that specific cycle, but concurrent modification is still unsafe and can lose entries or throw ConcurrentModificationException during iteration.

Mentioning this unprompted is worth real credit, because it signals you think about the class in a production context rather than as a textbook data structure. The correct answer for concurrent use is ConcurrentHashMap, which locks per-bin rather than wrapping the whole map in a single lock the way Collections.synchronizedMap does.

How does HashMap work internally, and what happens when it resizes?

Short answer

What the interviewer is scoring

Was this answer helpful?

Likely follow-ups

Related questions

Further reading

Related Topics

What the interviewer is scoring

The structure

The equals and hashCode contract

Resizing

Thread safety

How does HashMap work internally, and what happens when it resizes?

Answer

Short answer

What the interviewer is scoring

Was this answer helpful?

Likely follow-ups

Related questions

Further reading

Related Topics

What the interviewer is scoring

The structure

The equals and hashCode contract

Resizing

Thread safety