Open addressing and linear probing

How it works and why

In separate chaining, colliding keys share a bucket containing multiple entries. In open addressing, every key resides in a slot of the main array. If the hashed slot is occupied, linear probing checks (index + 1) % capacity, then (index + 2) % capacity, and so on until it finds the key or an available slot.

Lookup must follow the same probe sequence as insertion. Deletion is subtle: clearing a middle slot to empty can cause lookups past that slot to stop early. Real implementations use tombstones or suitable back-shifting. A table must have spare capacity; at 100% full, insertion cannot succeed.

C# and C++ examples

C#

C# | Example.cs

int[] slots = new int[11];
bool[] used = new bool[11];
int key = 19;
int start = key % slots.Length;
for (int step = 0; step < slots.Length; step++)
{
    int i = (start + step) % slots.Length;
    if (!used[i]) { slots[i] = key; used[i] = true; break; }
}
// This insertion-only example omits lookup/deletion and resizing.

C++

C++ | Example.cpp

#include <vector>
std::vector<int> slots(11);
std::vector<bool> used(11, false);
int key = 19;
int start = key % static_cast<int>(slots.size());
for (int step = 0; step < static_cast<int>(slots.size()); ++step) {
    int i = (start + step) % static_cast<int>(slots.size());
    if (!used[i]) { slots[i] = key; used[i] = true; break; }
}
// Insertion only: deletion needs tombstones or back-shifting.

When and why to use it

Compare: Chaining can store more than one value per bucket; linear probing typically has good locality but suffers from clustering. Pitfall: Deleting by setting used[i] = false is not a correct general deletion implementation once collisions occur. Try: With capacity 11 insert 1,12,23 and draw their probe sequence.

Interactive hash table · HashSet and Dictionary