Why Does Java’s HashMap Use a 0.75 Load Factor? The Math Behind It

Why Does HashMap Need a Load Factor?

HashMap is built on a hash table that stores key‑value pairs; it is an insertion‑slow, lookup‑fast structure. A load factor measures how full the table may become before it is automatically resized.

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

public int hashCode() {
    int h = 0;
    Iterator<Entry<K,V>> i = entrySet().iterator();
    while (i.hasNext())
        h += i.next().hashCode();
    return h;
}

How to Resolve Hash Collisions

1. Open Addressing

Linear probing : probe sequence Hi = (H(key) + i) mod m, i = 1,2,…

Quadratic probing : probe step di = ±i².

Pseudo‑random probing : probe step follows a pseudo‑random sequence.

Drawbacks: clustering, costly deletions, need for overflow area when table is full.

2. Rehashing

When a collision occurs, a secondary hash function RHi(key) is applied to find a new slot, increasing computation time.

3. Separate Overflow Area

All colliding entries are placed in an auxiliary overflow table, which requires linear scans during lookup.

4. Chaining (Linked‑list)

Each bucket holds a linked list of entries; insertion is simple, deletions are easy, and no clustering occurs, but extra memory is needed for the lists.

Why Is the Default Load Factor 0.75?

The resize threshold is calculated as DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR. With the default capacity of 16, the table resizes when 12 entries are stored.

Java’s source comments explain that, under random hash codes, the expected distribution of bucket sizes follows a Poisson distribution with λ≈0.5 when the load factor is 0.75. The probability of a bucket containing eight or more entries is less than one in ten million, making long chains extremely unlikely.

Choosing 0.75 balances time and space: a higher factor (e.g., 0.8) would increase collision probability and cache misses, while a lower factor (e.g., 0.6) would waste memory and cause more frequent rehashes.

Conclusion

Understanding the mathematical basis of the load factor helps developers tune HashMap performance and appreciate the role of probability theory in data‑structure design.