Backend Study Lab

Java

HashMap Collision Handling Explained

Learn how HashMap collision handling works in Java, including buckets, hashCode, equals, tree bins, load factor, bad keys, and performance.

By CloveCode Studio Jul 1, 2026 Updated Jul 1, 2026 5 min read

Quick answer

A HashMap collision happens when two different keys are assigned to the same bucket. Collisions are normal and allowed. Java resolves them by storing multiple entries in the bucket and using equals to find the exact key.

Good hashCode implementations, a reasonable load factor, and resizing keep collisions low enough that HashMap lookups are usually O(1) on average.

When many keys collide in the same bucket, modern Java can turn that bucket into a tree structure, which improves worst-case lookup behavior for large collision chains.

Why collisions happen

A HashMap stores entries in an internal table of buckets. Each key produces a hash code, and the map uses that hash to choose a bucket.

Different keys can produce the same bucket index for two reasons:

  • The keys have the same hash code.
  • The keys have different hash codes that still map to the same bucket after table indexing.

That is not a bug. The number of possible keys is much larger than the number of buckets, so collisions are inevitable in real programs.

The lookup flow

A simplified HashMap lookup works like this:

key -> hashCode -> bucket index -> scan bucket -> equals confirms key

For example:

Map<String, Integer> counts = new HashMap<>();
counts.put("java", 3);
counts.put("backend", 5);

Integer value = counts.get("java");

The map does not compare "java" with every key in the map. It uses the hash to go to the likely bucket, then compares keys in that bucket.

This is why both hashCode and equals matter. The hash narrows the search. Equality confirms the answer.

Buckets and chains

Historically, a collision bucket could behave like a linked list of entries.

bucket 7 -> entry A -> entry B -> entry C

If the map looks in bucket 7, it checks entries until it finds the matching key or reaches the end.

With a small number of collisions, this is fine. With many collisions in one bucket, lookup becomes slower because more entries must be checked.

Tree bins in modern Java

Modern Java includes a protection for heavily collided buckets. When a bucket becomes large enough and the table is large enough, the bucket can be transformed from a list-like structure into a tree-like structure.

The practical effect is better worst-case behavior when many entries land in one bucket.

This does not mean collisions are free. Tree bins add complexity and still require good key design. Treat them as a safety improvement, not as permission to write poor hashCode methods.

Collision example with a bad key

A terrible key class might return the same hash code for every instance:

public final class BadKey {
    private final String value;

    public BadKey(String value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof BadKey key && value.equals(key.value);
    }
}

This is technically valid because equal objects have the same hash code. But it is terrible for performance because every key goes to the same bucket.

A better implementation uses the meaningful field:

@Override
public int hashCode() {
    return Objects.hash(value);
}

Read Java equals and hashCode Explained for the full equality contract.

Load factor and resizing

Collisions become more likely as the table fills up. HashMap uses load factor to decide when to resize.

The default load factor is usually 0.75. That means a table with capacity 16 resizes after the number of entries crosses 12.

Resizing creates a larger table and redistributes entries, reducing bucket crowding.

Read HashMap Load Factor Explained for the deeper capacity and resizing discussion.

Average vs worst-case complexity

HashMap is commonly described as average O(1) for get and put.

That statement assumes reasonably distributed hashes and a table that is not overloaded. Poor hash distribution can create more bucket work. In extreme cases, many keys can concentrate in one bucket.

Modern collision handling improves worst-case behavior, but complexity tables are still simplified models. Real performance also depends on allocation, CPU cache behavior, key comparison cost, and map size.

Why equals is still required

A collision means two keys may share a bucket. The map still needs to know whether the requested key is exactly the same logical key as an existing entry.

That final check uses equals.

This is why hashCode alone is not enough. Hash codes are not unique identifiers. They are routing hints.

If two different keys have the same hash code, they can coexist in the same map as long as equals says they are different.

Mutable key danger

A key’s hash code must stay stable while the key is inside the map.

UserKey key = new UserKey("u_123");
Map<UserKey, String> map = new HashMap<>();
map.put(key, "active");

key.setValue("u_999");

map.get(key); // may return null

After mutation, the key may point to a different bucket than the one where the entry was stored. This is why map keys should usually be immutable value objects.

Common mistakes

The first mistake is using a constant hash code. It may be legally compatible with equals, but it destroys distribution.

The second mistake is using random or time-based hash codes. Hash codes must be consistent while the object is used in a collection.

The third mistake is assuming collisions mean data loss. Collisions are expected; equals separates entries inside the bucket.

The fourth mistake is tuning load factor before fixing key design. A bad hashCode method can defeat any table setting.

The fifth mistake is benchmarking with unrealistic keys. Production keys may have different distribution than test strings or sequential integers.

Practical backend checklist

When using custom objects as HashMap keys:

  • Make key classes immutable when possible.
  • Override equals and hashCode together.
  • Use stable identity fields.
  • Avoid mutable collections inside hash code calculations.
  • Test HashSet.contains or HashMap.get with equal but different instances.
  • Set initial capacity for large known maps.
  • Measure hot paths with realistic data.

HashMap collision handling is robust, but it works best when keys are designed cleanly.

Read Java equals and hashCode Explained for the equality contract behind hash keys. Read HashMap Load Factor Explained for resizing behavior, and Time Complexity of Java Collections for average and worst-case lookup tradeoffs. For broader map choices, read HashMap vs Hashtable in Java, ConcurrentHashMap Explained, and the Java Collections Learning Path. You can also browse Topics for related Java and algorithm guides.

Keep reading