Brewlearn Get the app
🧠 Data Structures & Algorithms · Advanced

Hash tables in Java

Hashing, collisions, load factor — the theory behind HashMap.

🧩 The mysteryYou put a key into a HashMap, change the key a little, and the entry is gone. Not deleted, just lost. Here's what's really inside a HashMap.

From key to bucket

A hash table turns a key into an array index. HashMap calls hashCode(), mixes the high bits into the low ones, and maps the result onto its bucket array. Like a coat check: your ticket number says which hook to look at. If keys spread well, get and put are O(1) on average.

int h = key.hashCode();
h = h ^ (h >>> 16);   // mix high bits
int bucket = (table.length - 1) & h;

Collisions and tree bins

Different keys can land in the same bucket: a collision. HashMap keeps them in a chain and checks each with equals. When a chain reaches 8 entries and the table has at least 64 buckets, it converts that bin into a red-black tree. In a smaller table it resizes instead: long chains there usually just mean too few buckets.

Load factor and resizing

A default HashMap has 16 buckets and a load factor of 0.75. The threshold is 16 x 0.75 = 12, so adding the 13th entry triggers a resize: the table doubles to 32 and entries are redistributed, keeping chains short.

🔮 Predict it

Equal keys, one entry

Records generate equals and hashCode for you. What does this print?

record Pt(int x, int y) {}
void main() {
    var m = new HashMap<Pt, String>();
    m.put(new Pt(1, 2), "A");
    m.put(new Pt(1, 2), "B");
    IO.println(m.size());
    IO.println(m.get(new Pt(1, 2)));
}
  1. 1 B
  2. 2 A
  3. 2 B
Show the answer

The two Pt(1, 2) objects are equal and have the same hash, so the second put lands in the same bucket and replaces the value. The contract: if a.equals(b), then a.hashCode() == b.hashCode(). Break it and the map searches the wrong bucket.

⚠️ The trap

Never mutate a key

The entry was filed in the bucket for the hash of [1]. After add(2), key hashes differently, so get(key) looks in another bucket: null. List.of(1) finds the right bucket, but equals fails against the stored [1, 2]: null again. The entry is stranded.

var key = new ArrayList<>(List.of(1));
var m = new HashMap<List<Integer>, String>();
m.put(key, "found");
key.add(2);
m.get(key);         // null
m.get(List.of(1));  // null
🤔 Think first

Every hash is 42

A buggy key class returns 42 from hashCode() for every object. What happens to HashMap lookups?

Think about it, then reveal the answer

All keys collide into one bucket, so lookups degrade toward O(n). Once that bin is treeified, lookups improve to O(log n), but only if the keys are Comparable. HashMap doesn't switch hash functions or throw; hashing only helps when keys spread out.

💼 In the real world

On the job

Mutable keys and broken hashCode overrides cause "the entry is in the map but get returns null" bugs. Use immutable keys like records and strings, always override equals and hashCode together, and presize maps you know will be large to avoid repeated resizing.

Key takeaways

  1. Average O(1) get/put if hashCode spreads keys well
  2. Long bins treeify at 8 entries when capacity is at least 64
  3. Default 16 buckets × 0.75 → resize on the 13th entry
  4. Equal objects must have equal hash codes

💡 A coat check: your ticket number says which hook to look at, and sometimes two coats share a hook.

🤯 Did you know?

Tree bins were added to HashMap in Java 8 (JEP 180) to keep lookups fast even when many keys collide, including deliberately crafted collision attacks.

Practice questions

What does this print?

var key = new ArrayList<>(List.of(1));
var m = new HashMap<List<Integer>, String>();
m.put(key, "found");
key.add(2);
System.out.println(m.get(key));
System.out.println(m.get(List.of(1)));
  1. null null
  2. found null
  3. found found
  4. null found
Check your answer

null null. The entry was filed under the hash of [1]. After mutation, key hashes differently and lands in another bucket; List.of(1) finds the right bucket, but equals fails against [1, 2]. Never mutate a key that's inside a map.

A HashMap created with default settings has 16 buckets. When does it first resize?

  1. When the 13th entry is added (size > 16 × 0.75)
  2. When the 16th entry is added
  3. When any bucket holds 8 entries
  4. Never; chains just grow longer
Check your answer

When the 13th entry is added (size > 16 × 0.75). The threshold is capacity × load factor = 12. Going past it doubles the table to 32 buckets and redistributes entries, keeping chains short.

Next: a tree that keeps keys sorted and never grows lopsided, the red-black tree inside TreeMap.