Where it runs
1. The problem
In the last step each bucket had its own small list, the chain. When two keys landed in one bucket, you walked that list. Open addressing works differently. All entries live in one flat array (one long row of cells). On a collision, the key moves forward to the next free cell of the array. A cell in such an array is called a slot.
A flat array has advantages. There are no separate lists and no extra references, and the entries sit next to each other in memory, which the processor reads faster. The price is that you need exact rules for two things. First: where does a key go if its slot is taken? Second: how do you delete a key without quietly breaking the search for other keys? Beginners miss the delete rule most often, and this lesson is about it.
2. In plain words
Take three keys from the tests: "a", "i" and "q". In a table of 8 slots all three start at slot 1. "a" takes slot 1. "i" finds slot 1 taken and moves on to slot 2. "q" finds slots 1 and 2 taken and lands in slot 3.
To find "q", you start at slot 1 and walk forward the same way: slot 1 holds "a", slot 2 holds "i", slot 3 holds "q". You stop when you find the key or when you reach a slot that was never used. A never-used slot means the key is not in the table, because the key would have taken that slot.
Now the hard part. Delete "i" and simply empty slot 2. Search for "q" again: slot 1 holds "a", slot 2 is empty, so the search stops and says "not here". But "q" is sitting in slot 3. The fix is to leave a mark in slot 2 that says "something was here, now it is empty". That mark is called a tombstone. A search walks past it and goes on. A new key may still be put in its place.
3. The idea
All entries live in one array of fixed size. Its size is called the capacity; here it is 8. Each slot holds one of three things: empty, a real [key, value] pair, or a tombstone. A tombstone is a mark that says "a key used to live here".
To place a key, first find its starting slot. The hash is computed as before: the sum of the character codes of the key, then the remainder after dividing by the capacity. The code of "a" is 97, and 97 % 8 is 1, so "a" starts at slot 1. That first slot is called the key's home slot.
If the home slot is taken by a different key, that is a collision. Linear probing solves it: move forward one slot at a time, to 2, then 3, and so on. After the last slot (7) you go on to slot 0. Keep going until you find an empty slot or the same key. Put the pair into the empty slot. If you found the same key, replace its value in place, and the count of entries stays the same.
get and has walk the same path: they start at the home slot and step forward. As soon as they find the key, they return the value. As soon as they reach an empty slot, they stop and answer "this key is not here". Here is why an empty slot proves it: on insert, the key would have taken the first free slot on its path. So if the key is present, it stands before the empty slot.
The tombstone matters in delete. You cannot make the deleted slot empty: an empty slot stops every later search. Then any key that walked past this slot on insert would suddenly look missing. So delete writes a tombstone into the slot. Searches walk past tombstones and go on. And set may put a new key in place of a tombstone.
Trace it with capacity 8. set("a", 10): home slot 1 is empty, put it there. set("i", 20): the code of "i" is 105, and 105 % 8 is 1. Slot 1 holds "a", so step to slot 2, which is empty, and put it there. set("q", 30): the code of "q" is 113, and 113 % 8 is 1 too. Walk past "a" in slot 1 and "i" in slot 2 and put "q" in slot 3. Now delete("i"): slot 2 gets a tombstone. get("q"): start at slot 1, which holds "a", not it. Step to slot 2: a tombstone, walk past it. Step to slot 3: "q", found. The key is still reachable thanks to the tombstone. An empty slot 2 would have stopped the search, and get("q") would have returned nothing.
One more thing: this table has a fixed capacity, so it can fill up. If every slot holds a real pair and you call set with a brand-new key, there is nowhere to put it. This version changes nothing in that case, and get on that key returns undefined. Growing the table so that it never fills up is the next step.
4. What it costs
While the table still has free room, each operation costs about O(1): compute the hash and walk past a couple of slots at most. Memory is O(capacity): one flat array and nothing beside it.
As the table fills up, the runs of taken slots grow longer, and probing walks further. In the worst case the cost approaches O(n). So real tables never let themselves fill up: they grow in advance (step 17). Compare with the chaining of the last step. Open addressing uses less memory and works better with the CPU cache, because the slots sit next to each other. It suffers more from a full table, though, and it needs the tombstone rule to delete safely.
6. Where this shows up
Many hash tables in production systems use open addressing. dict in CPython (the main Python implementation) runs on it, and it is in almost every Python program. When it deletes, dict leaves tombstones (called "dummy" entries there) for exactly the reason you just worked through. Fast C++ tables, such as flat_hash_map from Google's Abseil library and the older dense_hash_map, keep their entries in one flat array to work well with the CPU cache. Open addressing is a common choice when a table in memory has to be fast and it matters how the data sits in the cache. Examples: routing tables, symbol tables in compilers, interning pools (stores where each string exists only once). And every author of such a table had to solve deletion with tombstones.
On LeetCode
Design problems about a hash table in one flat array, where a collision sends the key to the next free slot and the index wraps around after the last slot.
Write it with linear probing and tombstones, so remove never breaks the search for keys stored past it.
The same probing over one flat array, storing only the keys.
Moving on with (i + 1) % capacity is the same wraparound your probing uses after the last slot.
Your task (Tier 1)
Build the HashMap class over one flat list of 8 slots. Methods: set, get, has, delete and the size getter. The constructor and the _hash helper are given.
Each slot holds one of three things: empty, a deletion mark (a tombstone) or a [key, value] pair. On a collision, go to the next slot with (home + step) % 8: after slot 7 it gives slot 0.
- Change the list of slots:
setanddelete. - Return:
getgives a value or nothing;hasgivestrue/false;deletegivestrue/false;sizegives a count.
Steps:
set(key, value): start at the home slot_hash(key)and move forward one slot at a time. If you meet the same key, replace its value in place and finish (the size stays the same). If you meet a tombstone, remember the first such place, but do not stop: this key may stand further on. When you reach an empty slot, put the pair into the remembered tombstone if there was one, otherwise into this empty slot, and add 1 to the size. If you went through all 8 slots without finding an empty one, put the pair into the remembered tombstone if there is one. If there is no tombstone, the list is full and the key is new: do nothing.get(key): walk from the home slot. Skip tombstones. If the key matches, return the value. When you reach an empty slot, stop and return nothing.has(key): the same walk, returntrueorfalse.delete(key): walk from the home slot and skip tombstones. At an empty slot, stop and returnfalse. If the key matches, put a tombstone in the slot, take 1 off the size and returntrue.size: return how many real pairs are stored.
Done when all tests pass:
set("a",1),set("b",2)->get("a")->1,has("a")->true,size->2set("a",10),set("i",20),set("q",30)share one home slot, yet all three come back, e.g.get("q")->30set("a",1)thenset("a",9)->get("a")->9,size->1(replaced in place)- after
delete("i"), a key that stands past it still works:get("q")->30,has("i")->false - fill all 8 slots, then a new
set("i",99)does nothing:get("i")->undefined,size->8 - empty map:
get("x")->undefined,delete("x")->false,size->0
Practice
Hash map by open addressing (linear probing + tombstone delete)
class HashMap { set(key, value); get(key) -> value|undefined; has(key) -> bool; delete(key) -> bool; get size -> int }
const CAPACITY = 8;
const TOMB = Symbol('tombstone');
export class HashMap {
constructor() {
this.slots = new Array(CAPACITY).fill(null);
this._size = 0;
}
_hash(key) {
let sum = 0;
for (let i = 0; i < key.length; i++) sum += key.charCodeAt(i);
return sum % CAPACITY;
}
set(key, value) {
// Your code here. The task is described in the box above the editor.
}
get(key) {
// Your code here. The task is described in the box above the editor.
}
has(key) {
// Your code here. The task is described in the box above the editor.
}
delete(key) {
// Your code here. The task is described in the box above the editor.
}
get size() {
// Your code here. The task is described in the box above the editor.
}
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.