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

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.