Collections Framework

Hashing Internals

HashMap = array of buckets, indexed by a spread of the key's hashCode, with collisions chained in lists that convert to red-black trees when they grow. Knowing this explains capacity, load factor, and why hashCode quality matters.

Bucket index = (n - 1) & spreadedHash — table size n is always a power of two
Load factor 0.75: table doubles (rehash) when size exceeds capacity × 0.75
Java 8+: a bucket with ≥ 8 colliding entries becomes a red-black tree → worst case O(log n)
Equal objects must share a hash code, or lookups miss (Object Contracts)
Presize: HashMap.newHashMap(expected) (Java 19+) or capacity = expected / 0.75 + 1

Picture the table first: a HashMap is, at bottom, an array (table) of "buckets." A key's hashCode() is reduced to an index into that array — that reduction is what "spreading" and (n-1) & hash compute. Put a key in and it lands in the bucket its index names; ask for it back and the map recomputes the same index and looks there. Two keys can reduce to the same index — they "collide" — so each bucket actually holds a small chain (or, once it grows large enough, a tree) of every entry that ever landed there, and a lookup walks that chain comparing hashes then equals. Load factor and resizing exist to keep those chains short: shrink the array-to-entries ratio, and the ④-step "walk the bucket" degrades.

A get(key): ① compute key.hashCode(), ② spread it (h ^ (h >>> 16) — mixes high bits into the low bits that pick the bucket), ③ index the table, ④ walk the bucket comparing first hash values, then equals. With a good hash function buckets hold 0–2 entries and the whole operation is a handful of cache accesses.

The essential shape (simplified from OpenJDK)

transient Node<K,V>[] table;          // length always a power of 2

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;                    // collision chain
}

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

Treeification (Java 8) capped the damage of pathological collisions: before it, an attacker posting thousands of colliding keys degraded a server's HashMap to an O(n) list — an actual DoS class. At 8 collisions a bucket becomes a red-black tree ordered by hash then (if Comparable) by key.

hashCode quality is your contract: Objects.hash(f1, f2, …) is fine for most classes; high-performance code hand-rolls 31 * result + field chains to avoid varargs boxing (EJ Item 11). Caching the hash of an immutable object (as String does) turns repeated lookups nearly free.