What is Hashing with Open Addressing?
Learn how open addressing resolves hash collisions with probing, why deletion needs tombstones, and how to explain it in interviews.
Expected Interview Answer
Open addressing resolves hash collisions by keeping all entries directly inside the table's own array of slots, probing to a different slot (via linear, quadratic, or double hashing) whenever the computed slot is already occupied, instead of chaining a list off each bucket.
When a key hashes to an occupied slot, the probing sequence checks the next candidate slot according to a fixed rule: linear probing moves one slot at a time, quadratic probing jumps by increasing squared steps, and double hashing uses a second hash function to compute the step size. Search follows the same probe sequence, stopping at a match or an empty slot that was never filled. Because every entry lives in the array itself with no extra pointers, open addressing has excellent cache locality and lower memory overhead than chaining, but deletion is trickier — removing an entry outright can break probe sequences for later keys, so implementations use tombstone markers instead. Open addressing also degrades faster as the load factor approaches 1, since probe chains grow long when the table is nearly full.
- No extra pointer/list overhead per entry
- Better cache locality than chaining
- Table stays a single contiguous array
- Multiple probing strategies to reduce clustering
AI Mentor Explanation
Open addressing is like a stadium's numbered parking lot where every ticket hashes to one designated spot, and if that spot is taken, the attendant does not start a side queue there but instead walks to the next spot in a fixed pattern until an empty one is found. Finding a parked car later means hashing the ticket to its expected spot and walking that same fixed pattern until the car or an untouched empty spot appears. As the lot fills up, this walking search gets noticeably longer since fewer empty spots remain to stop the probe. Removing a car carelessly would break the search for cars parked after it, so attendants mark the spot 'recently vacated' instead of just leaving it blank.
Step-by-Step Explanation
Step 1
Hash to a preferred slot
Compute the initial candidate index using the primary hash function.
Step 2
Probe on collision
If the slot is occupied by a different key, apply the probing rule (linear, quadratic, or double hashing) to get the next candidate.
Step 3
Repeat until placed or found
Continue probing until an empty slot is reached (insert) or the key matches / an untouched empty slot is hit (search).
Step 4
Delete with tombstones
Mark removed slots as deleted rather than empty so later searches do not stop prematurely.
What Interviewer Expects
- Name at least one probing strategy: linear, quadratic, or double hashing
- Explain why deletion needs tombstones instead of clearing the slot
- Compare cache locality and memory overhead against chaining
- State performance degrades sharply as load factor approaches 1
Common Mistakes
- Clearing a deleted slot outright instead of using a tombstone marker
- Confusing open addressing with chaining
- Not knowing linear probing suffers from primary clustering
- Letting the load factor reach 1.0, causing infinite or very long probes
Best Answer (HR Friendly)
“Open addressing handles hash collisions by keeping everything inside the array itself: if a key's preferred slot is taken, it just checks the next slot in a fixed pattern until it finds a free one. I like it for cache performance since there is no pointer chasing, though I am careful with deletions because you have to leave a marker behind instead of truly clearing the slot.”
Code Example
class OpenAddressingTable:
EMPTY, DELETED = object(), object()
def __init__(self, size=8):
self.size = size
self.slots = [self.EMPTY] * size
self.count = 0
def _probe(self, key):
idx = hash(key) % self.size
for step in range(self.size):
i = (idx + step) % self.size
yield i
def put(self, key, value):
first_deleted = None
for i in self._probe(key):
slot = self.slots[i]
if slot is self.EMPTY:
target = first_deleted if first_deleted is not None else i
self.slots[target] = (key, value)
self.count += 1
return
if slot is self.DELETED:
if first_deleted is None:
first_deleted = i
continue
if slot[0] == key:
self.slots[i] = (key, value)
return
raise RuntimeError("table full")
def get(self, key):
for i in self._probe(key):
slot = self.slots[i]
if slot is self.EMPTY:
raise KeyError(key)
if slot is not self.DELETED and slot[0] == key:
return slot[1]
raise KeyError(key)
def delete(self, key):
for i in self._probe(key):
slot = self.slots[i]
if slot is self.EMPTY:
raise KeyError(key)
if slot is not self.DELETED and slot[0] == key:
self.slots[i] = self.DELETED
self.count -= 1
return
raise KeyError(key)Follow-up Questions
- How does linear probing lead to primary clustering, and how does quadratic probing help?
- Why does open addressing require tombstones for deletion?
- How would you decide the resize threshold to avoid long probe sequences?
- How does double hashing reduce clustering compared to linear probing?
MCQ Practice
1. In open addressing, where are all key-value entries stored?
Open addressing keeps every entry inside the array itself, probing to another slot on collision rather than chaining externally.
2. Why is a tombstone marker used instead of clearing a slot on deletion?
If a slot were simply cleared, a search for a later-inserted colliding key could stop early at the empty slot and wrongly report "not found".
3. What problem does linear probing commonly suffer from?
Linear probing tends to form long runs of occupied slots (primary clustering), which lengthens future probe sequences.
Flash Cards
Name the three common probing strategies in open addressing. — Linear probing, quadratic probing, and double hashing.
Why can't you just clear a slot when deleting in open addressing? — It would break probe sequences for keys placed after it during earlier collisions, so a tombstone marker is used instead.
What advantage does open addressing have over chaining in terms of memory? — No extra pointers or list nodes per entry — better cache locality and lower overhead.
What happens to open addressing performance as load factor approaches 1? — Probe sequences grow long and performance degrades sharply since few empty slots remain.