UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 14.4 Free with a free account
Open Addressing: Linear and Quadratic Probing
Data Structures and Algorithms · Chapter 14: Maps and HashingSection 14.4 · lesson 59 of 8710 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: Sorted Maps: Keeping Key-Value Pairs in Order →← Hash Tables: The Array Behind Near-Instant LookupNext lesson: Sorted Maps: Keeping Key-Value Pairs in Order →
In this lesson
Resolving hash collisions inside the array with linear and quadratic probes.
- Trace insertion and search with linear and quadratic probing
- Explain how primary and secondary clustering raise probe counts
- Determine which slots quadratic probing can reach for a given table size
- Repair a probe run correctly after removing a key
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,356 words). Read along, or search it.
Opening Question
Four Keys Want Slot Zero
A table has eleven slots, numbered zero to ten, and a key's home slot is the key mod eleven. Twenty-two, thirty-three and forty-four all have home slot zero, so they can't all live there. Now fifty-five arrives, and it wants slot zero too. Where should it go? And once it's somewhere else, how will a lookup ever find it? That's the problem of collisions.
Definition
Probe Sequences for Open Addressing
Open addressing keeps every entry inside the array itself. When the slot a key wants is taken, the table probes: it examines other slots in a fixed order, until it finds a free one. The slots it examines form the probe sequence: home plus f of i, mod m, for i equal to zero, one, two, and so on. Linear probing uses f of i equals i: home, then the next slot, then the next. Quadratic probing uses i squared: offsets zero, one, four, nine, sixteen. From home slot five in our eleven slots, linear probing visits five, six, seven, eight. Quadratic probing visits five, six, nine, then three, because fourteen wraps around.
Worked Example
Inserting With Linear Probing
Insert walks the probe sequence and stores the entry in the first empty slot. If it meets the same key on the way, it replaces that key's value, because a key may appear only once. Insert twenty-two, thirty-three, forty-four, fifty-five and twelve, with linear probing. Twenty-two takes slot zero. Thirty-three finds zero taken, and moves to one. Forty-four probes zero, one, and lands in two. Fifty-five lands in three, on its fourth probe. Twelve has home slot one. It's taken, and so are two and three, so twelve ends up in slot four, after four probes.
Search Rule
An Empty Slot Proves Absence
Find follows exactly the sequence insert would have followed. It stops when it finds the key, when it reaches an empty slot, or after m probes. An empty slot proves the key is absent: if the key had been inserted, insert would have used that slot, or an earlier one. So look for sixty-six, which is absent. Its home is zero. Slots zero through four are all occupied, and slot five is empty. Six probes, to learn that a key isn't there.
Weakness
Primary Clustering Builds Runs
Look again at twelve. Its home slot is one, and no key shares that home with it. Yet it took four probes, because slots one, two and three were filled by keys that wanted slot zero. This is primary clustering, the weakness of linear probing. Collisions build a run of occupied slots. Any key whose sequence enters the run is added at its end, so the run grows. A longer run is a bigger target for the next key, and runs can merge. Long runs make both inserts and unsuccessful finds slow.
Quick Check
Where Fifteen Lands
Quick check. A table has seven slots, the home slot is the key mod seven, and it uses linear probing. Insert fourteen, twenty-one, eight and fifteen, in that order. Which slot does fifteen end up in? Pause, and decide. It's b, slot three. Fourteen takes zero. Twenty-one wants zero, and moves to one. Eight's home is one, taken, so it moves to two. Fifteen's home is also one. One and two are full, so it lands in three, on its third probe. Neither eight nor fifteen has home slot zero, but the run caught them anyway.
Quadratic Probing
Jumps That Grow Each Probe
Quadratic probing makes the jump grow with every probe. A colliding key moves a little at first, then farther away. Insert the same five keys. Twenty-two takes zero, and thirty-three takes one. Forty-four probes zero, one, then four. Fifty-five probes zero, one, four, then nine. And twelve, home slot one, tries one, then two, and stops: second probe, instead of being pulled into a run. Looking for the absent sixty-six now takes five probes instead of six.
Weakness
Secondary Clustering Along One Path
Quadratic probing isn't perfect. Keys with the same home slot follow the same probe sequence. Twenty-two, thirty-three, forty-four and fifty-five still need one, two, three and four probes, exactly as under linear probing, because every one of them follows zero, one, four, nine. That's secondary clustering. It's milder, since runs of neighboring slots no longer build up, but keys with one home still compete along one path. Giving each key its own step size, called double hashing, comes later in the course.
Limit
Slots Quadratic Probing Never Visits
There's a sharper limit. Linear probing eventually visits every slot. Quadratic probing doesn't. From home slot zero, in a table of eleven slots, only six slots are ever visited. In a table of ten slots, also only six: zero, one, four, five, six and nine. Fill those six slots of a ten-slot table, and inserting ten, home slot zero, fails, even though four slots are still free. The remedy: when the number of slots is prime, the first m plus one, over two, probes all hit different slots. Keep it less than half full too, and an insert always succeeds.
Removal Problem
Erasing Breaks the Empty-Slot Rule
Removing is harder than inserting, because find relies on one rule: an empty slot means the key is absent. Erasing an entry breaks that rule for every key placed beyond it. Take the linear table twenty-two, thirty-three, forty-four, and simply erase thirty-three. Forty-four is still stored, in slot two. But find forty-four starts at zero, sees twenty-two, then reaches the erased slot, which now looks empty, and concludes that forty-four is absent. Null, after two probes.
Repair
Reinserting the Rest of the Run
With linear probing there's a correct repair. Every entry that might depend on the erased slot lies in the same run, right after it. So after erasing, take out each following entry, up to the next empty slot, and insert it again. Forty-four moves from slot two up to slot one, and find forty-four succeeds in two probes. Quadratic probing has no such simple repair, because the dependent entries are scattered along sequences that jump by one, four, nine and more. Its standard remedy is a deletion marker, which comes later in the course.
Measured Results
Probes Rise With Load Factor
How full is too full? Tables of one thousand nine prime slots were filled with random keys, and the probes per lookup were averaged over many runs. Below a load factor of one half, both rules are fast: a present key needs about one and a half probes. Absent keys suffer first. At zero point nine, linear probing needed about forty probes to prove a key absent, and quadratic probing about eleven. Inserts cost the same as absent finds. And notice: linear probing at one half needed only two and a half probes, far fewer than quadratic at zero point nine. A table that grows before it fills beats a cleverer probe rule.
Quick Check
Reachable Slots in Twelve
Quick check. A quadratic probing table has twelve slots. Starting from home slot zero, how many different slots can a key ever probe? Pause, and decide. It's a: only four. The offsets mod twelve go zero, one, four, nine, then sixteen gives four again, and twenty-five gives one. Slots zero, one, four and nine, and nothing else. Twelve isn't prime, so the sequence repeats early. A key could fail with eight slots free. Choose a prime size, and keep it under half full.
Common Mistakes
Removal, Limits and Negative Hashes
A few mistakes to avoid. Emptying a slot on remove makes entries beyond it unreachable. Probing without a limit loops forever on a full table, so stop after m probes. Using the percent operator on a negative hash: minus five percent eleven is minus five, not a valid slot. Math floor mod gives six. And letting the slots fill up makes absent keys very slow.
Key Takeaways
Probing Rules and Their Costs
To recap. Open addressing keeps every entry in the array and probes a fixed sequence of slots. Find follows the same sequence, and an empty slot means absent. Linear probing suffers primary clustering. Quadratic probing suffers milder secondary clustering, and needs a prime size and a table under half full. Never just empty a slot on remove: repair the run, or use a marker. And keep the load factor well below one.
Think About It
A Ninety Percent Full Table
Here's something to think about. A linear probing table is ninety percent full, and lookups for absent keys are slow. A teammate proposes switching to quadratic probing. How much would that help, and what would it not fix? What change would help more? And which operation gets harder after the switch?
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 Open Addressing: Linear and Quadratic Probing
How does linear probing work in a hash table?
What is primary clustering in linear probing?
Why does quadratic probing need a prime table size?
Why can't you simply empty a slot when removing from an open addressing table?
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 →