What is a Hash Collision?

When discussing hash collisions, we need to understand the fundamental issue: different objects processed through the same hash algorithm produce identical hash values.

Consider HashMap's internal structure—a combination of an array with linked lists. When a key-value pair is inserted, the hash code determines which array index the entry belongs to. If two different keys produce the same hash code, they must coexist at the same index.

This scenario—where multiple keys map to the same bucket—is precisely what we call a hash collision.

HashMap resolves this using separate chaining. When a collision occurs, the new entry gets appended to a linked list at that bucket position.

A Common Interview Question

Here's a practical question: the hash collision diagram above was drawn based on which JDK version?

The critical detail involves insertion order. JDK 7 uses head insertion, while JDK 8 switched to tail insertion.

Constructing Strings with Identical HashCodes

Understanding collisions naturally leads to a question: how do we generate two different Strings with the same hash code?

First, consider single-character strings. Different characters always produce different hash codes based on ASCII values, so length-1 strings cannot collide.

Let's examine length-2 strings by analyzing String's hashCode implementation from JDK 8:

public int hashCode() {
    int h = 0;
    for (int i = 0; i < value.length; i++) {
        h = 31 * h + value[i];
    }
    return h;
}

For a string "xy" where x and y represent character ASCII values:

• First iteration: h = 31 × 0 + x = x
• Second iteration: h = 31 × x + y

Thus, "xy" produces a hash code of 31x + y.

Similarly, "ab" produecs 31a + b.

Setting these equal for collision:

31x + y = 31a + b

This rearranges to:

31(x - a) = b - y

A special solution emerges when x - a = 1 and b - y = 31. This means the first characters' ASCII values differ by 1, and the second characters' ASCII values differ by -31.

Looking at ASCII values: 'A' = 65, 'B' = 66, 'a' = 97, 'b' = 98.

"Aa" and "BB" have identical hash codes.

Verification:

public class HashCollisionDemo {
    public static void main(String[] args) {
        System.out.println("Aa".hashCode());  // Output: 2112
        System.out.println("BB".hashCode());  // Output: 2112
    }
}

Generating Multiple Strings with the Same HashCode

Since "Aa" and "BB" share a hash code, their permutations also collide:

• "AaAa", "AaBB", "BBAa", "BBBB" all produce the same hash

Each of these can combine with "Aa" or "BB" to create additional colliding strings, and this pattern continues indefinitely.

A utility generates colliding strings:

public class CollisionStringGenerator {
    private static final String[] BASE_STRINGS = {"Aa", "BB"};
    
    public static List<String> generateCollidingStrings(int power) {
        List<String> result = new ArrayList<>(Arrays.asList(BASE_STRINGS));
        for (int i = 1; i < power; i++) {
            result = expandWithBase(result);
        }
        return result;
    }
    
    private static List<String> expandWithBase(List<String> existing) {
        List<String> expanded = new ArrayList<>();
        for (String base : BASE_STRINGS) {
            for (String s : existing) {
                expanded.add(base + s);
            }
        }
        return expanded;
    }
}

With power = 3, this generates 8 strings with identical hash codes: "Aa", "BB", "AaAa", "AaBB", "BBAa", "BBBB", "AaAaAa", "AaAaBB", "AaBBAa", "AaBBBB", "BBAaAa", "BBAaBB", "BBBBAa", "BBBBBB".

Impact on HashMap Performance

Inserting these 14 strings in to a HashMap triggers interesting behavior. After two resize operations, the internal array reaches length 64. Only three bucket positions are occupied (indices 0, 31, and 32), with the bucket at index 32 holding 8 nodes in a linked list.

In JDK 8, buckets convert to red-black trees when containing more than 8 nodes. However, a critical condition is often overlooked: the array must have at least 64 elements for treeification to occur.

if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

The treeifyBin method checks array capacity:

private final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index;
    Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else
        // proceed with treeification
}

With default capacity (16), adding the 9th colliding element causes resize to 32 rather than treeification. The 9th element remains a regular Node, not a TreeNode.

Using Custom Objects as HashMap Keys

Using String as keys covers most scenarios, but custom objects sometimes serve as keys. When doing so, failing to properly implement hashCode() and equals() causes severe issues.

Consider storing student information:

public class Student {
    private String name;
    private Integer age;
    // getters, setters, toString omitted
}

public class ResidenceInfo {
    private String address;
    private String vehicleType;
    // getters, setters, toString omitted
}

Test scenario:

public class StudentMapDemo {
    private static Map<Student, ResidenceInfo> studentRecords = new HashMap<>();
    
    static {
        Student student = new Student("John", 8);
        ResidenceInfo info = new ResidenceInfo("North Street", "Bicycle");
        studentRecords.put(student, info);
    }
    
    public static void main(String[] args) {
        updateResidence("John", 8, "Riverside Road", "Motorcycle");
        studentRecords.forEach((s, r) -> 
            System.out.println(s + "-" + r));
    }
    
    private static void updateResidence(String name, Integer age, 
            String address, String vehicle) {
        Student key = new Student(name, age);
        ResidenceInfo existing = studentRecords.get(key);
        if (existing == null) {
            studentRecords.put(key, new ResidenceInfo(address, vehicle));
        }
    }
}

The update operation fails. Despite "John" aged 8 already existing in the map, the system treats the lookup as a new entry. The result: two distinct student entries appear instead of updating the original.

The root cause: HashMap.get() uses the new object's hashCode to locate the bucket. Without a custom hashCode() implementation, each Student instance produces a different hash code. The lookup searches an empty bucket and finds nothing.

But there's a second problem. Even if hashCode were implemented, HashMap.put() compares keys using equals(). Without equals(), two objects with the same hashCode still wouldn't match as duplicate keys.

The conclusion: custom objects used as HashMap keys must override both hashCode() and equals().

Without these overrides, memory exhaustion becomes likely. Each lookup creates a new object with a unique hash code, triggering continuous resizing until an OutOfMemoryError occurs.

Historical Note on Hash Computation

The hashCode formula has evolved. Early JDK versions and the first edition of "Effective Java" used 37 as the multiplier:

result = 37 * result + c

The formula changed to 31 in later releases. The reason: 31 allows optimized computation through bit shifting—31 × i equals (i << 5) - i, which modern JVMs handle efficiently. This simple change provides measurable performance improvement.

Modern Java implementations consistently use 31, reflecting this optimization decision that balances collision distribution with computational efficiency.