Collision Handling
In this page:
What is a Collision
A collision happens when a hash function maps two different keys to the same position in the hash table, which is unavoidable in general since the number of possible keys is usually far larger than the table's size.
Example: What is a Collision
#include <iostream>
using namespace std;
int hashFn(int key, int size) { return key % size; }
int main() {
cout << "hash(12)=" << hashFn(12, 5) << " hash(7)=" << hashFn(7, 5) << " (same slot = collision)";
return 0;
}public class Main {
static int hashFn(int key, int size) { return key % size; }
public static void main(String[] args) {
System.out.println("hash(12)=" + hashFn(12, 5) + " hash(7)=" + hashFn(7, 5) + " (same slot = collision)");
}
}def hash_fn(key, size):
return key % size
print("hash(12)=", hash_fn(12, 5), "hash(7)=", hash_fn(7, 5), "(same slot = collision)")#include <stdio.h>
int hashFn(int key, int size) { return key % size; }
int main() {
printf("hash(12)=%d hash(7)=%d (same slot = collision)", hashFn(12, 5), hashFn(7, 5));
return 0;
}Login to try C/C++/Java code in the editor
Linear Probing
Linear probing handles a collision by checking the next slot in the table, and the one after that, and so on, until an empty position is found to place the new key.
Example: Linear Probing
#include <iostream>
using namespace std;
int main() {
int table[5] = {-1, -1, -1, -1, -1};
int keys[] = {12, 7, 17};
for (int k : keys) {
int idx = k % 5;
while (table[idx] != -1) idx = (idx + 1) % 5;
table[idx] = k;
}
for (int i = 0; i < 5; i++) cout << table[i] << " ";
return 0;
}public class Main {
public static void main(String[] args) {
int[] table = {-1, -1, -1, -1, -1};
int[] keys = {12, 7, 17};
for (int k : keys) {
int idx = k % 5;
while (table[idx] != -1) idx = (idx + 1) % 5;
table[idx] = k;
}
for (int v : table) System.out.print(v + " ");
}
}table = [-1] * 5
keys = [12, 7, 17]
for k in keys:
idx = k % 5
while table[idx] != -1:
idx = (idx + 1) % 5
table[idx] = k
print(table)#include <stdio.h>
int main() {
int table[5] = {-1, -1, -1, -1, -1};
int keys[] = {12, 7, 17};
for (int i = 0; i < 3; i++) {
int idx = keys[i] % 5;
while (table[idx] != -1) idx = (idx + 1) % 5;
table[idx] = keys[i];
}
for (int i = 0; i < 5; i++) printf("%d ", table[i]);
return 0;
}Login to try C/C++/Java code in the editor
Chaining
Chaining handles a collision differently: instead of finding another slot, each table position holds a small list (a bucket) of all the key-value pairs that hashed there, so colliding keys simply share the same bucket.
Example: Chaining
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> buckets[5];
int keys[] = {12, 7, 17};
for (int k : keys) buckets[k % 5].push_back(k);
cout << "Bucket 2: ";
for (int v : buckets[2]) cout << v << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < 5; i++) buckets.add(new ArrayList<>());
for (int k : new int[]{12, 7, 17}) buckets.get(k % 5).add(k);
System.out.println("Bucket 2: " + buckets.get(2));
}
}buckets = [[] for _ in range(5)]
for k in (12, 7, 17):
buckets[k % 5].append(k)
print("Bucket 2:", buckets[2])#include <stdio.h>
int main() {
int bucket2[5], count = 0;
int keys[] = {12, 7, 17};
for (int i = 0; i < 3; i++) if (keys[i] % 5 == 2) bucket2[count++] = keys[i];
printf("Bucket 2: ");
for (int i = 0; i < count; i++) printf("%d ", bucket2[i]);
return 0;
}Login to try C/C++/Java code in the editor
Collision Effects
When too many keys collide into the same slots or buckets, lookups degrade from the ideal O(1) toward O(n), since the table has to check multiple candidates instead of finding the right one immediately.
Example: Collision Effects
#include <iostream>
using namespace std;
int main() {
int bucketSize = 4;
cout << "Bucket has " << bucketSize << " keys -- lookup now checks all " << bucketSize << ", degrading toward O(n)";
return 0;
}public class Main {
public static void main(String[] args) {
int bucketSize = 4;
System.out.println("Bucket has " + bucketSize + " keys -- lookup now checks all " + bucketSize + ", degrading toward O(n)");
}
}bucket_size = 4
print("Bucket has", bucket_size, "keys -- lookup now checks all", bucket_size, ", degrading toward O(n)")#include <stdio.h>
int main() {
int bucketSize = 4;
printf("Bucket has %d keys -- lookup now checks all %d, degrading toward O(n)", bucketSize, bucketSize);
return 0;
}Login to try C/C++/Java code in the editor
Good Hashing
A good hash function is the real defense against collisions: it should spread keys as evenly as possible across the whole table, which keeps buckets short and linear-probing chains close to their starting slot.
Example: Good Hashing
#include <iostream>
using namespace std;
int poorHash(int key) { return key % 2; }
int goodHash(int key) { return (key * 2654435761u) % 10; }
int main() {
cout << "poor(4)=" << poorHash(4) << " poor(6)=" << poorHash(6) << " (collide)\n";
cout << "good(4)=" << goodHash(4) << " good(6)=" << goodHash(6) << " (spread out)";
return 0;
}public class Main {
static int poorHash(int key) { return key % 2; }
static int goodHash(int key) { return (int)((key * 2654435761L) % 10); }
public static void main(String[] args) {
System.out.println("poor(4)=" + poorHash(4) + " poor(6)=" + poorHash(6) + " (collide)");
System.out.println("good(4)=" + goodHash(4) + " good(6)=" + goodHash(6) + " (spread out)");
}
}def poor_hash(key):
return key % 2
def good_hash(key):
return (key * 2654435761) % 10
print("poor(4)=", poor_hash(4), "poor(6)=", poor_hash(6), "(collide)")
print("good(4)=", good_hash(4), "good(6)=", good_hash(6), "(spread out)")#include <stdio.h>
int poorHash(int key) { return key % 2; }
int goodHash(int key) { return (key * 2654435761u) % 10; }
int main() {
printf("poor(4)=%d poor(6)=%d (collide)\n", poorHash(4), poorHash(6));
printf("good(4)=%d good(6)=%d (spread out)", goodHash(4), goodHash(6));
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: