5.3 Collision Resolution | Code Scholars Tutoring

How it works

Chaining hangs a secondary structure off each bucket; open addressing probes for another slot. Linear probing suffers primary clustering, where occupied runs lengthen future probes.

Compare the two by memory behavior and by how gracefully they degrade as the table fills.

Common error

Treating a collision as an error. Collisions are expected and handled, not prevented.

Worked example

Example

Capacity: 5
Keys inserted: 7, 12, 17
Bucket index: key mod 5
All three initially map to bucket 2

Chaining stores multiple entries at a bucket, while open addressing searches other table positions. A probing scheme must define lookup and deletion consistently so a removed entry does not hide later displaced keys.

Keys 7, 12, and 17 hash to bucket 2 in a capacity-5 table and occupy slots 2, 3, and 4. — Probe to later available slots, using the same rule for lookup.

Exercises

5.3.1 · Explain

Under linear probing in an empty capacity-5 table, where do 7, 12, and 17 land?

Show solution

They initially hash to 2. With linear probing, they occupy indices 2, 3, and 4 in that insertion order.

5.3.2 · Write code

Insert 7, 12, and 17 into an empty capacity-5 table using linear probing. Use null to mark an unused slot and print the table.

Show solution

All three hash to 2; wrap around with remainder if a later position is needed.

One valid solution

Integer[] table = new Integer[5];
for (int key : new int[]{7,12,17}) {
    int index = Math.floorMod(key, table.length);
    while (table[index] != null) index = (index + 1) % table.length;
    table[index] = key;
}
System.out.println(Arrays.toString(table));

Expected output

[null, null, 7, 12, 17]

Open Java compiler