How Does Java’s HashMap Work? Deep Dive into Structure, Hashing, and Resizing

HashMap Data Structure

HashMap stores entries in an internal array where each slot, called a bucket, holds a linked list of key‑value pairs. When a bucket’s list exceeds a threshold (default 8), it is transformed into a red‑black tree to improve lookup performance. In JDK 1.7 and earlier the structure was array + linked list; starting with JDK 1.8 it became array + linked list + red‑black tree.

HashMap Hash Function

The core of HashMap is its hash function, which mixes the original hashCode() of a key with a shifted version to improve randomness (the “perturbation” method). The algorithm is:

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

This produces a new hash value by XOR‑ing the original hash code with its unsigned right‑shifted 16‑bit counterpart, reducing collisions caused by poor hashCode implementations.

HashMap Hash Collisions

Because the hash function maps many possible keys to a fixed number of buckets, different keys can end up in the same bucket, causing a hash collision. HashMap resolves collisions using separate chaining: each bucket stores colliding entries in a linked list (or tree when the list becomes long).

HashMap Dynamic Resizing

When the number of stored entries reaches loadFactor × capacity (default load factor 0.75, initial capacity 16), HashMap automatically expands. The first resize occurs when 12 entries are present, doubling the array size. During resizing, a new array is allocated and all existing entries are rehashed into it.

These mechanisms—array‑based storage, hash mixing, collision chaining, and load‑factor‑driven resizing—constitute the core implementation details of Java’s HashMap.