Core Concept Mastery • DSA Module
We handle collisions in two main ways: Chaining (keep a list at each slot so more than one item can live there) and Linear Probing (if the slot is full, try the next slot, then the next, until you find an empty one). Linear probing can cause clustering (many used slots in a row).
Idea: If spot 5 is full, keep a list at that index. Add the new item to the list. One slot can hold many items (like a linked list).
Idea: Spot 5 full? Try 6. Full? Try 7. Keep going until you find an empty slot.
Problem: Clustering. When many used slots are in a row, you may have to walk far to find an empty one.
Chaining (list at each slot)
If spot 5 is full, we do not move the first item. We add the new item to a list at spot 5. So one slot can hold many items (like bunk beds in a room). We use a linked list at that index. Search: go to the index, then walk the list if needed.
Linear probing (try next door)
If spot 5 is full, we try spot 6. If that is full, we try 7, then 8, and so on until we find an empty slot. The problem is clustering: when many slots in a row get full, you may have to step through many slots to find an empty one. So performance can get worse when the table is full.
Collisions will happen. Chaining is simple and works well when the list at each slot stays short. Linear probing keeps everything in the array but if many slots in a row get full, finding an empty slot can take longer (clustering).