How HashMap Actually Works, and Why It Matters

HashMap is the collection most Java developers use most and understand least. The internals are not complicated, and knowing them explains several behaviours that otherwise look arbitrary.

The structure

A HashMap is an array of buckets. A key's hash decides which bucket it lands in, and the bucket holds the entries whose keys mapped there.

Index selection is (n - 1) & hash, where n is the array length. That is a bitmask rather than a modulo, which is why the array length is always a power of two. It also means only the low bits of the hash affect the bucket, so a hashCode that varies only in its high bits would collide constantly. HashMap compensates:

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

That single xor mixes the high sixteen bits down into the low ones. It is cheap and it rescues mediocre hash functions, which is most hand-written ones.

Collisions

Two keys in the same bucket form a linked list. Lookup walks the list, comparing hashes first and then calling equals. With a good hash function the lists stay at length one and lookup is constant time.

With a bad one, the map degrades to a linked list and lookup becomes linear. Since Java 8 there is a floor: once a bucket holds eight entries and the table has at least 64 buckets, that bucket becomes a red-black tree, and lookups within it become logarithmic. If it shrinks back below six, it reverts to a list.

Treeification was added for a security reason. An attacker who could produce colliding keys could send a few thousand form fields that all hashed to one bucket and turn every request into quadratic work. Trees cap the damage. Treeification requires the keys to be Comparable to order the tree; otherwise it falls back on identity hash comparison, which still works but is not something to rely on.

Resizing

HashMap has a load factor, 0.75 by default. When size exceeds capacity times load factor, the array doubles and every entry is redistributed. Since capacity is a power of two, an entry either stays at index i or moves to i + oldCapacity, decided by a single bit. That makes the rehash cheap, but it still touches every entry.

The practical consequence: if you know roughly how many entries you will store, say so.

Map<String, User> users = new HashMap<>(1000);

That is a capacity hint, not a size limit. Note that the argument is the initial capacity, so a map you intend to fill with 1000 entries will still resize at 750. To avoid it entirely, pass (int) (expected / 0.75f) + 1, or on Java 19 and later use the clearer factory:

Map<String, User> users = HashMap.newHashMap(1000);

Mutable keys

If a key's fields change after insertion, its hash changes, and the entry is now in the wrong bucket. The map does not notice. A lookup with an equal key computes the new hash, goes to the new bucket, and finds nothing. The entry still exists, still shows up in iteration, and is unreachable by get.

This is not a theoretical problem. It is the single most common cause of "the object is in the set but contains returns false", and it is why the equals and hashCode contract asks for stability, and why a JPA entity with a generated id makes such a poor key before it is persisted. Use immutable keys. Records are ideal here precisely because their components are final and their hashCode is derived correctly.

Thread safety

HashMap is not synchronised, which everyone knows. The interesting part is the failure mode. Concurrent put calls during a resize can corrupt the internal structure. In Java 7 this could produce a circular linked list and an infinite loop in get, pinning a CPU core at 100% with no exception and no stack trace pointing at anything useful. Java 8's resize algorithm made that specific infinite loop go away, but lost updates and torn state remain entirely possible.

Use ConcurrentHashMap. It locks per bin rather than globally, so reads are lock-free and writes contend only with writes to the same bucket. Note that computeIfAbsent on a ConcurrentHashMap holds that bin's lock for the duration of the mapping function, so a function that itself touches the same map can deadlock. Keep it short and side-effect free.

Collections.synchronizedMap wraps every method in one lock, which is correct and much slower, and still does not make compound operations like check-then-put atomic.

What to take away

Give keys a decent hashCode, make them immutable, size the map when you know the size, and use ConcurrentHashMap when more than one thread is involved. The rest of the machinery is there to make average cases fast and worst cases survivable.