← Back to the section

From the outside HashMap looks simple: you put, you get, and everything is instant. But how does it find a value by key in a single step, even when there are a million keys? And why does it sometimes suddenly start to slow down? Let's dig into what lies under the hood in Java 21 — it explains both the speed and the requirements on equals/hashCode.

The bucket array

At the core of HashMap is an ordinary array. In the code it is called table, and its cells are buckets. Each bucket stores elements — nodes of type Node, holding the key, the value, and a reference to the next node.

// simplified, as it is declared inside HashMap
Node<K,V>[] table;   // the bucket array

static class Node<K,V> {
    final int hash;    // the stored hash of the key
    final K key;
    V value;
    Node<K,V> next;    // reference to the next node in the same bucket
}

The idea is simple: instead of scanning every element looking for the right key, HashMap immediately computes which bucket the key must be in and looks only there. That is why access, on average, does not depend on the size — that is exactly the "instantaneity".

Short formula: HashMap is an array of buckets, and given a key it can compute the number of the right bucket.

How the bucket number is computed

To turn a key into a cell number, HashMap takes three steps.

  1. It takes the key's hashCode() — an integer "fingerprint".
  2. It mixes the bits of that number: the high 16 bits are shifted and combined (XOR) with the low bits. This is needed because the bucket number depends mostly on the low bits, while many objects' hashCode differs precisely in the high bits — without mixing they would all land in the same bucket.
  3. It takes the remainder modulo the array size via the fast bitwise operation hash & (n - 1), where n is the length of table. The array size is always a power of two, so & (n - 1) works as "take the last bits" and yields a number from 0 to n−1.
// this is how HashMap mixes the bits of hashCode (the hash method)
static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// bucket number: hash & (n - 1)

A null key is allowed too — it always goes into bucket number 0.

Collisions and the linked list

There are many distinct keys but only a limited number of buckets. Inevitably two different keys end up in the same bucket — this is a collision.

HashMap resolves it simply: a bucket stores not a single element but a chain — a linked list of nodes (remember the next field?). On put the new node is appended to this list; on get HashMap walks the list and compares keys to find the right one.

Map<String, Integer> map = new HashMap<>();
map.put("Anna", 30);   // say it landed in bucket 5
map.put("Ivan", 25);   // say it also landed in bucket 5 — a collision
// bucket 5: ["Anna"->30] -> ["Ivan"->25]

This is exactly where equals matters: inside a bucket the hashes are compared first, and on a match equals is called to tell "Anna" from "Ivan". Without a correct equals, HashMap cannot tell whether it is the right key.

While a bucket holds one or two elements, walking the list is unnoticeable. The trouble starts when many nodes pile up in a single bucket — more on that next.

Turning the list into a tree

A long linked list is slow: to find a key you have to walk the whole thing, and that is O(n) (the time grows linearly with the number of elements in the bucket). So that this bad case does not kill performance, Java has an optimization.

When 8 or more nodes accumulate in a single bucket (and the array is large enough), HashMap turns the linked list into a red-black tree — this is called treeify. The tree keeps elements sorted by hash, and lookups run in O(log n) — noticeably faster than a linear scan.

before treeify (list):  A -> B -> C -> D -> E -> F -> G -> H
after treeify (tree):
            D
          /   \
         B      F
        / \    / \
       A   C  E   G ...

If elements are later removed from the bucket and there are 6 or fewer, the tree collapses back into a list — untreeify. The two different thresholds (8 to convert, 6 to revert) are deliberately spread apart so that the structure does not flip back and forth when it hovers around the boundary.

In practice it rarely reaches the tree: with a good hashCode elements are distributed evenly, and a bucket seldom holds more than one or two. The tree is insurance against the worst case, not the normal mode of operation.

Load factor and resize

The more elements in a fixed-size array, the longer the chains and the more frequent the collisions. To avoid this, HashMap tracks fullness via the load factor, 0.75 by default.

This means: as soon as the number of elements exceeds 75% of the array size, a resize happens — the array doubles in size, and all elements are moved (rehashed) into the new, roomier array under new bucket numbers. The starting size is 16, so the first resize happens at roughly the 12th element (16 × 0.75).

// if you know in advance there will be ~1000 elements,
// it is better to set the initial capacity — fewer resizes
Map<String, Integer> map = new HashMap<>(1400);

A resize is not cheap: all elements have to be moved. If you know the approximate size in advance, pass it to the constructor — it saves several doublings as the map grows. 0.75 is a compromise: a smaller value spends more memory but yields fewer collisions; a larger value does the opposite.

Why hashCode matters so much

All of HashMap's speed rests on one condition: elements must be spread evenly across the buckets. hashCode is responsible for that.

Imagine a class whose hashCode always returns the same number:

class BadKey {
    int id;
    @Override public int hashCode() { return 42; }  // do not do this
}

All objects will land in one bucket. HashMap degenerates into a single long list (or tree), and get/put will run in O(n) instead of near-instant access — that is, the whole point of HashMap is lost.

Hence two rules. First: equals and hashCode must be consistent — if two objects are equal by equals, their hashCode must match. Second: hashCode must spread values well, not return a constant. The most reliable way to get both properties for free is to make the type a record: it generates correct equals and hashCode over all fields.

record UserId(long value) {}   // equals and hashCode are generated correctly

Fail-fast and thread safety

HashMap keeps an internal modification counter — modCount. Every put/remove increments it. When you iterate the collection with an iterator (including via for-each), the iterator remembers the value of modCount and checks it on every step. If someone modifies the collection during the traversal, the counter diverges and the iterator throws ConcurrentModificationException. This behavior is called fail-fast — "fail right away", so you notice the problem on the spot rather than silently getting corrupted data.

Map<String, Integer> map = new HashMap<>(Map.of("a", 1, "b", 2));
for (String key : map.keySet()) {
    if (key.equals("a")) {
        map.remove(key);   // ConcurrentModificationException
    }
}

A separate point: HashMap is not thread-safe. If two threads write to it at the same time, you can corrupt the internal structure (up to an infinite loop during a resize) — and you get no exception at all. modCount catches modifications only during a traversal by a single thread; it is not protection against concurrent access.

When a map is accessed by several threads, use ConcurrentHashMap from the java.util.concurrent package — it is designed for concurrent access and still stays fast.

import java.util.concurrent.ConcurrentHashMap;

Map<String, Integer> safe = new ConcurrentHashMap<>();  // safe from many threads

In short

  • Inside, HashMap is an array of buckets (Node[] table); the bucket number is computed as hash & (n - 1), where hash is the mixed hashCode of the key.
  • Bit mixing is needed so that differences in the high bits of hashCode also affect the bucket number.
  • Collisions (different keys in one bucket) are resolved with a linked list of nodes; equals helps tell the keys apart.
  • At 8+ nodes in a bucket the list turns into a red-black tree (O(n) → O(log n)), and at 6 or fewer it collapses back.
  • Load factor 0.75: at 75% fullness the array doubles and all elements are rehashed; if you know the size, set the capacity in the constructor.
  • A bad hashCode (a constant, for example) forces everything into one bucket and kills the speed; the easiest fix is to use a record.
  • The fail-fast iterator catches modifications via modCount; for multiple threads HashMap is not suitable — use ConcurrentHashMap.
  • Java collections — an overview of List, Set, Map and when to choose which.
  • Generics — what <K, V> means in the HashMap declaration.
  • Garbage collection — what happens to objects and the old array after a resize.