UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.6 Free with a free account
Finding Another Slot When the Home Slot Is Taken
Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.6 · lesson 72 of 8712 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Sorting and Selection in Practice →← Comparing Sorts: Speed, Memory, and StabilityNext lesson: Sorting and Selection in Practice →
In this lesson
Double hashing, tombstones, and cuckoo hashing for taken home slots.
- Compute double-hashing probe sequences and explain why a prime table size helps
- Explain why deletion in open addressing needs tombstones and how they slow searches
- Describe how cuckoo hashing guarantees at most two probes per lookup
- Estimate the cost of an unsuccessful search from the load factor
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,725 words). Read along, or search it.
Opening Question
Two Keys Share One Home Slot
A hash function sends every key to a home slot. But two keys can share a home slot, and a slot holds only one key. Key eighteen already sits in slot five. Now forty-four arrives, and its home is slot five too. Where should forty-four go? And how will a later search know where to look for it?
Open Addressing
Probe Sequences and the Load Factor
In open addressing, the other place is another slot of the same array, reached by a probe sequence: a fixed series of slots that depends on the key. Every open-addressing table faces two more problems: how to delete a key, and how speed suffers as the table fills. How full it is, is the load factor, alpha: keys divided by slots. An alpha of one half means half the slots are in use. This lesson covers four ways to place a key whose home is taken: double hashing, cuckoo hashing, Robin Hood hashing, and hopscotch hashing.
Double Hashing
A Second Hash Picks the Step
In double hashing, a second hash function chooses how far to jump. The key's i-th probe lands on slot h one of k, plus i times h two of k, all mod m, where m is the number of slots. Probe zero is the home slot. If it's taken, probe one jumps one step, and probe two jumps two steps from the start. The jump size is the step. Because the step depends on the key, two keys that share a home slot usually follow different paths afterward. The step must never be zero, or the probe would stay on one slot forever. So the usual choice is one, plus k mod the quantity m minus one.
Worked Example
Eight Keys in Thirteen Slots
Take thirteen slots, with h one of k equal to k mod thirteen. Insert eight keys in order. Eighteen goes home to slot five. Forty-one goes to slot two, and twenty-two to slot nine. Forty-four's home is five, which is taken. Its step is one plus forty-four mod twelve, which is nine. So it jumps to slot one. Fifty-nine goes home to seven, and thirty-two to six. Thirty-one also starts at five. But its step is eight, so it lands in slot zero, not slot one. Seventy-three goes home to eight. Only two of the eight keys needed a second probe. And the two that shared slot five went separate ways.
Searching
Following the Same Probe Path
A search follows exactly the same path. Compute the home slot and the step. At each slot on the path: if it's empty, the key is absent, because an insertion would have stopped there. If it holds the key, it's found. Otherwise, jump by the step. Insertion walks the same path, and uses the first empty slot.
Table Size
Why a Prime Table Size Helps
The table size matters. A key's path visits slots zero, s, two s, and so on, wrapping around, where s is the step. With twelve slots and a step of four, the path visits zero, four, eight, and then it's back at zero. It's trapped on three slots. So a key could be refused even though the table has room. With twelve slots, steps of two, three, four and six all get trapped. With thirteen slots, every step from one to twelve reaches all thirteen slots. The rule: a path visits every slot exactly when the step and m have no common factor bigger than one. A prime table size guarantees that for every step.
Quick Check
A Step of Four in Ten Slots
Quick check. A table has ten slots, and a key's step is four. Starting from its home slot, how many different slots can its path ever visit? Pause, and decide. Five. From slot zero: four, eight, two, six, and back to zero. Four and ten share the factor two, so the path only ever lands on every other slot. Ten would need a step with no common factor, such as three or seven. Four is the step, not the number of slots visited.
Deletion
Emptying a Slot Breaks Searches
Now, deleting. A search stops at the first empty slot, because if the key had been inserted, it would have been placed there or earlier. Here's a table of seven slots. Nine sits at its home slot, two. Sixteen also has home slot two, jumps by a step of five, and lands in slot zero. Delete nine by simply emptying its slot. Now search for sixteen. Its first probe hits slot two, finds it empty, and reports that sixteen is absent. That's wrong. The fix is a tombstone. Instead of emptying the slot, mark it as deleted.
Tombstone Rules
Search, Insert, and Delete With Tombstones
The rules become these. A search treats a tombstone as occupied by something else, and moves on. Only an empty slot stops it. An insertion may reuse the first tombstone on the path, but only after reaching an empty slot, which proves the key isn't stored yet. And a deletion finds the key, and overwrites its slot with the tombstone.
Hidden Cost
Tombstones Pile Up Until a Rebuild
Tombstones fix correctness, but they cost speed. A tombstone doesn't stop a search, and a table can fill up with them even when few keys are alive. In one measurement, a table of ten thousand and seven slots was half full. Then, again and again, a random key was deleted and a new one inserted, so the live keys never changed. A fresh table needed two probes for an unsuccessful search. After twenty-five thousand cycles, it needed three hundred forty-five. After a hundred thousand cycles, not one slot was empty, and every unsuccessful search visited all ten thousand and seven slots. The remedy: count tombstones together with live keys when judging how full the table is. When that combined load gets too high, rebuild, re-inserting only the live keys.
Cuckoo Hashing
Two Tables and Two Possible Homes
Double hashing may probe many slots before it finds an empty one. Cuckoo hashing guarantees a short lookup instead. It keeps two tables, T one and T two, with two hash functions. Every key has exactly two possible homes: one slot in each table. A lookup checks those two slots and nothing else. So it makes at most two probes, however full the tables are. Insertion keeps that promise by eviction. A new key goes into its T one home. If a key is already there, it's pushed out, the way a cuckoo chick pushes eggs from a nest. The evicted key moves to its home in the other table, and may evict another key in turn, until a key lands in an empty slot.
Worked Example
An Insertion With Three Evictions
Here's one insertion, with eleven slots per table. h one is k mod eleven, and h two is k divided by eleven, mod eleven. A hundred five goes to its T one home, slot six, and evicts fifty. Fifty moves to its T two home, slot four, and evicts fifty-three. Fifty-three moves back to T one, slot nine, and evicts seventy-five. Seventy-five moves to T two, slot six, which is empty. The chain ends after three evictions. Most insertions in the run made no evictions, or one. But the tenth key set off a chain of seven.
Limits
Cycles, Rebuilds, and a Half-Full Ceiling
If a chain goes on too long, it has probably hit a cycle, where keys keep displacing one another forever. Then new hash functions are picked, and everything is rebuilt. How full can the tables get? With a hundred thousand slots in all, every trial worked at a load of forty-five percent. At forty-eight percent, two of twenty trials failed. At half full, fourteen of twenty. At fifty-five percent, every trial failed. That's the price of the two-probe guarantee: about half the slots stay empty. Deletion, though, is simpler: clear the slot, with no tombstone, because no search follows a path.
Other Schemes
Robin Hood and Hopscotch Hashing
Two more ideas are worth knowing by name. Robin Hood hashing probes forward, but when a new key meets a resident, the key farther from its own home keeps the slot. That evens out probe lengths, and a search for a missing key can stop early, once its distance exceeds the resident's. Hopscotch hashing keeps every key inside a small, fixed neighborhood of its home slot, say thirty-two slots. A lookup scans only that window. If it's full, nearby keys are shuffled to make room.
Performance
Probe Counts as the Table Fills
Finally, speed as the load factor rises. For double hashing, theory predicts about one over one minus alpha probes for an unsuccessful search. A simulation with a hundred thousand and three slots follows the formula closely: two probes at half full, five at eighty percent, and ten at ninety percent. Linear probing, from the earlier lesson on open addressing, climbs far faster. Keys pile up in long runs, and at ninety percent it needed nearly forty-nine probes. Searches for a key that's present stay cheap for longer: about three probes even at ninety-five percent. But misses, and so insertions, get expensive quickly.
Quick Check
Tombstones Count Toward the Load
Quick check. A double-hashing table of ten thousand and seven slots holds seven thousand live keys, and two thousand tombstones. About how many probes does a search for a missing key need? Pause, and decide. Ten, roughly. Tombstones don't stop a search, so they count toward the load. Nine thousand of ten thousand slots are in use: alpha is about point nine. One over one minus point nine is ten. Three is what you'd get by counting only the live keys, and fifty is linear probing's figure at that load.
Decision Guide
Double Hashing or Cuckoo Hashing
Choosing between the two main schemes comes down to this. Double hashing: about one over one minus alpha probes for a miss, so keep alpha below about point seven or point eight. It needs tombstones, a rebuild when they pile up, and a prime table size. Two-table cuckoo hashing: at most two probes, always, and deletion just clears the slot. But the load must stay below about one half, with an occasional rebuild.
Key Takeaways
Collision Strategies in Brief
To sum up. Double hashing jumps by a step from a second hash function, so keys that share a home usually part ways. The step is never zero, and a prime table size lets every step reach every slot. Deletion needs tombstones, and tombstones count toward the load until a rebuild. Cuckoo hashing gives each key two possible slots, so a lookup needs at most two probes, below about half full. And for a missing key, expect about one over one minus alpha probes.
Think About It
Fixed Lookups Versus Constant Churn
Here's something to think about. One table holds a fixed list of identifiers. It's built once, and then looked up millions of times. A second table has constant insertions and deletions. Which would you give to cuckoo hashing, and which to double hashing? And why?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Finding Another Slot When the Home Slot Is Taken
How does double hashing work?
Why should a double hashing table size be prime?
Why does open addressing use tombstones for deletion?
What is cuckoo hashing?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →