The one core idea: an open-addressing hash table stores keys directly inside one array, and to find a key you walk a fixed trail of slots until you hit it or hit an EMPTY slot that says "stop, not here." Deleting a key by blanking its slot to EMPTY lies to that trail — so we instead plant a tombstone that means "gone, but keep walking."
This page builds every word and symbol the parent note leans on, from absolutely nothing. If you have never seen a hash table, start here and read top to bottom — nothing below is used before it is drawn.
Before any hashing, you need the picture of an array : a straight row of numbered boxes, side by side, each holding one thing.
Definition Array and its indexAn array is a fixed row of boxes. Each box has an address called its index , counted from 0 0 1
Symbol: we write slot j to mean "the box at index j
Picture: think of a row of lockers with numbers painted on the doors.
m m m = 7 0 , 1 , 2 , 3 , 4 , 5 , 6
Why the topic needs it: every probe formula ends in "mod m inside the array. Without m
k key k 5 , 10 , 15
Picture: the label on the item you're putting in a locker.
Why needed: every operation (insert, search, delete) is about a key . Everything else exists to answer "where does key k
We can't search all m jumps straight to a likely box. That rule is the hash function.
h ( k ) hash function h k { 0 , 1 , … , m − 1 } first try to put or find k
Picture: a machine with k
The parent uses h ( k ) = k mod m
Definition The modulo operationmod a mod m a m 0 … m − 1
Example: 15 mod 5 = 0 15 = 3 × 5 + 0 17 mod 5 = 2 17 = 3 × 5 + 2
Why this tool and not plain division? Division could give you 3.4 inside the shelf ; mod m 0 … m − 1 0
Answer these before moving on:
17 mod 5 2
10 mod 5 0
Why does every index formula end in mod m To keep the result a valid box index inside the array (and to wrap past the end back to 0
A collision happens when two different keys hash to the same starting box, i.e. h ( k 1 ) = h ( k 2 ) k 1 = k 2
Picture: two people assigned locker 3, but the locker holds one bag.
In the parent, A, B, C all have hash 3 why we need probing at all.
There are two families of fixes for collisions. The parent lives in open addressing ; knowing the other one sharpens what "open" means.
Definition Two collision strategies
Separate chaining : each box holds a little linked list; colliding keys all hang off the same box. Deletion is easy (just unlink). See Separate Chaining .Open addressing : every key lives directly in the array — no lists. A colliding key must find a different empty box by trying others in order. See Open Addressing .
Because open addressing keeps everything in the one array, deleting a key leaves a gap inside the array itself — and that gap is the whole problem the tombstone solves. Separate chaining never has this issue.
Since a colliding key can't use its first box, it tries others in a fixed, repeatable order. That ordered list of boxes is the probe sequence.
Definition Probe, and probe indexi probe is one attempt to look at a box. We number attempts with ==i 0 0 1
Worked example Reading the trailWith m = 7 h ( k ) = 3 h ( k , 0 ) = 3 , h ( k , 1 ) = 4 , h ( k , 2 ) = 5 , h ( k , 3 ) = 6 , h ( k , 4 ) = 0 , … 6 0 mod 7
Every box is always in exactly one of three states. The parent's whole argument turns on telling them apart.
Definition EMPTY, OCCUPIED, DELETED
EMPTY : never held a key on this trail → search stops here ("not present").OCCUPIED : currently holds a key → check if it's the one we want; if not, keep probing.DELETED (the tombstone , written † was here but was removed → search keeps probing , insert may reuse it.Picture: an empty locker (open door, nothing), a full locker (a bag), and a locker with a "used to be here" sticky note.
The single most important distinction — and the reason tombstones exist:
To talk about cost , we need one number for "fullness."
Definition Live load factorα α === m n occupied n occupied 0 1
Picture: the fraction of lockers with a real bag inside.
The parent extends this to α eff also counts tombstones in the numerator — because search must walk past them too. See Load Factor and Rehashing .
Self-test:
If m = 5 3 α 3/5 = 0.6
If additionally 1 α eff ( 3 + 1 ) /5 = 0.8
Search stops at EMPTY invariant
Load factor and alpha eff
Test yourself — you should be able to answer each without looking up.
What is an array index, and where does counting start? The address of a box in the row; counting starts at 0
What does m The table size — the number of boxes in the array.
What does a hash function h ( k ) A starting box index in { 0 , … , m − 1 } k
Compute 15 mod 5 0
Why does every probe formula end in mod m To keep the index inside the array and wrap the last box back to 0
What is a collision? Two different keys hashing to the same box.
Difference between open addressing and separate chaining? Open addressing stores every key inside the array; separate chaining hangs colliding keys off linked lists.
Write the linear-probing sequence formula. h ( k , i ) = ( h ( k ) + i ) mod m
What are the three slot states? EMPTY, OCCUPIED, DELETED (tombstone).
What opposite messages do EMPTY and DELETED send to a search? EMPTY says "stop, not here"; DELETED says "keep probing."
Define the live load factor α n occupied / m
Define α eff ( n occupied + n tombstones ) / m
Parent: tombstone deletion — where all of this is put to work.Hash Functions — the h ( k ) Open Addressing — the family this topic belongs to.Linear Probing — the specific probe rule used above.Separate Chaining — the alternative where deletion is trivial.Load Factor and Rehashing — where α α eff 
