Stage 4: HashMap internals, lesson 5 of 13

HashMap internals 5: Collisions

Intermediate3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

A collision is when two different keys land in the same bucket. There are two ways it happens:

  1. Same hash code: "Aa" and "BB" both have hash code 2112, so they always share a bucket, whatever the table size.
  2. Different hash codes, same index: billions of possible hash codes are squeezed into a few buckets using only the low bits. "book" (3029737) and "cat" (98262) have very different hash codes, yet both end up in bucket 7 of 16.

Collisions are normal and expected; HashMap is built to handle them (part 6). What matters is keeping buckets short, which depends on:

  • a good hashCode() that spreads keys evenly, and
  • resizing before the table gets too full (parts 7 and 9). After a resize to 32 buckets, "book" stays in bucket 7 and "cat" moves to 23.
HashMap lab

Example

Java
// Different hash codes, same bucket (16 buckets)
System.out.println("book".hashCode());   // 3029737
System.out.println("cat".hashCode());    // 98262
// bucketOf("book", 16) == 7 and bucketOf("cat", 16) == 7   (see part 2)

// A terrible hashCode: every key collides
class BadKey {
    final String id;
    BadKey(String id) { this.id = id; }
    @Override public int hashCode() { return 42; }                  // legal, but ruins performance
    @Override public boolean equals(Object o) { return o instanceof BadKey b && b.id.equals(id); }
}

Common mistake

Treating collisions as a bug to eliminate. They can't be avoided; a good hashCode() and resizing just keep them rare.

Under the hood

With a constant hash code every entry shares one bucket, so HashMap degrades into a list (O(n) per lookup) or, in Java 8+, a tree (O(log n)). Attackers have used deliberately colliding keys (for example crafted HTTP parameter names) to slow servers down; this "hash flooding" is one reason Java 8 added tree buckets.

Check yourself

"book" and "cat" have different hash codes but share bucket 7 of 16. Is that a collision?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.