UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 14.6 Free with a free account
Separate Chaining: Linked Buckets
Data Structures and Algorithms · Chapter 14: Maps and HashingSection 14.6 · lesson 61 of 8713 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: Real Applications Built on Hashing →← Sorted Maps: Keeping Key-Value Pairs in OrderNext lesson: Real Applications Built on Hashing →
In this lesson
Resolving hash collisions with a linked list in every bucket.
- Implement put, get and remove for a separately chained hash table
- Relate load factor to expected chain length and comparison counts
- Compare separate chaining with linear probing on cost and removal
- Explain how Java's HashMap mixes hash bits and turns long chains into trees
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,999 words). Read along, or search it.
Opening Question
Every Bucket Holds a List
A hash table turns a key into an array position. But there are far more possible keys than positions, so two keys will sometimes want the same one. Open addressing handled that by probing for another free slot. Separate chaining takes the opposite view: it never looks for another slot. Instead, each position becomes a bucket holding a linked list, and every key that wants that position simply joins its list. Store twenty-two, thirty-three, forty-four, fifty-five and twelve in eleven buckets. The first four all belong to bucket zero, so they share one chain. Twelve gets bucket one, and a chain of its own.
Data Layout
An Array of Bucket Heads
A chained table is an array of bucket heads. Each bucket is either null, meaning empty, or a reference to the first node of a linked list. Each node stores one entry: a key, a value, and a reference to the next node. The node type is nested inside the map class. The constructor takes the number of buckets, and a limit on the load factor, which decides when it grows. Index maps a key to a bucket with Math dot floor mod, so even a negative key gets a valid bucket. And last comparisons records the cost of the latest lookup.
Insertion
Walk First, Then Link at the Head
Every operation starts the same way: compute the bucket, then walk its chain. Nothing outside that one chain is ever examined. Put walks the chain first, because a key may appear only once. If the key is there, its value is replaced. If not, a new node is linked in at the head of the chain. No walk to the end is needed: once the key is known to be new, that's constant time.
Lookup and Removal
Walking and Unlinking a Chain
Get walks the chain, counting comparisons, and stops when a key matches or the chain ends. Reaching null is enough to prove the key is absent. Remove finds the node and unlinks it. The variable prev trails one node behind, so the node before the target can point to the node after it. If the target is the head, the bucket itself is updated instead.
Worked Example
Six Keys in Five Buckets
Here's a table of only five buckets, which never grows. Keys twelve, three, twenty-two, eight, seven and seventeen go in. Twelve, twenty-two, seven and seventeen share bucket two. Three and eight share bucket three. The newest key sits at the head: seventeen was inserted last, and it's found with one comparison. Twelve went in first, so it's at the end, and takes four. Ninety-nine belongs to the empty bucket four, so it's rejected without a single comparison. Twenty-seven is absent too, but it belongs to bucket two, so the search walks the whole chain first.
Advantage
Removal Without Repair or Markers
Now remove twenty-two from the middle of bucket two's chain. Seven simply points past it, to twelve. Nothing else had to move. Twelve is still found, now one comparison sooner, and twenty-two is gone. That's a real advantage over probing, where an erased slot could hide other entries and needed a repair or a marker. In a chain, a removed node is just gone.
Worked Example
The Opening Keys Revisited
Back to the five keys from the start, in eleven buckets. Bucket zero holds fifty-five, forty-four, thirty-three, twenty-two: newest first. Finding them takes four, three, two and one comparisons. Twelve takes one, and the absent twenty-three, in bucket one, also takes one.
Comparison
Chaining Versus Linear Probing Counts
Linear probing stored the same keys in the same eleven slots. Its probes for twenty-two through fifty-five ran one, two, three, four: the opposite order. The real difference is twelve. Under probing, it had to walk past all four keys, though none of them wanted its slot. In a chained table, the crowd in bucket zero never spills into bucket one. In total, eleven comparisons for chaining, and fourteen probes for linear probing.
Quick Check
Head-First Order in Bucket Three
Quick check. A chained table has seven buckets, and a key's bucket is the key mod seven. Ten, seventeen, twenty-four, three and eleven go in, in that order, each linked at the head. What does bucket three hold, from head to tail? Pause and predict. It prints three, twenty-four, seventeen, ten. All four leave remainder three when divided by seven, and each new node went in at the head, so the newest, three, comes first. Eleven leaves remainder four, so it has bucket four to itself. And ten, seventeen, twenty-four, three is arrival order, which a chain linked at the tail would give.
Load Factor
Chain Length and Lookup Cost
All three operations cost time proportional to the length of one chain. So how long are the chains? The load factor is n over m: entries divided by buckets. Under open addressing it could never pass one. Here an entry is a node, not a slot, so the load factor can be one, two, or ten. The average chain length is exactly the load factor, but the entries aren't spread exactly. At a load factor of one, about thirty-seven percent of buckets stay empty, while a few chains reach three, four or five. So an absent key walks a whole chain: about L comparisons, where L is the load factor. A present key stops about halfway: about one plus L over two.
Measured Results
Formulas Checked Against Runs
This program checks the formulas: tables of one thousand and nine buckets, random keys, two hundred runs per load factor. The measurements sit almost exactly on the formulas. At a load factor of four, a present key still needs only three comparisons on average. But notice the longest chain: about twelve at a load factor of four, three times the average. An unlucky key can cost more than the average suggests.
Quick Check
Twenty Entries in Eight Buckets
Quick check. A chained table holds twenty entries in eight buckets, with a hash function that spreads keys evenly. On average, about how many comparisons does a lookup of a present key need? Pause, and decide. About two and a quarter. The load factor is twenty over eight, two and a half, and a present key costs one plus L over two. Two and a half is the cost for an absent key, which walks the whole chain. And ten and a half would be a single list of twenty, searched halfway.
Resizing
Doubling Buckets and Relinking Nodes
Since the cost follows the load factor, a table that keeps receiving entries must add buckets. The usual policy: when an insert pushes the load factor past a limit, double the buckets, and move every node. That's called resizing, or rehashing. Nodes must move because a key's bucket is the key mod m, and m has changed. No new nodes are created: each is relinked, so the loop saves next before overwriting it.
Measured Results
How Often Resizes Happen
Insert one to a hundred into a table that starts with four buckets, and a limit of point seven five. It doubles at the fourth, seventh, thirteenth, twenty-fifth, forty-ninth and ninety-seventh entries. Each resize relinks every node, so one insert can be expensive. But doubling makes resizes rare: a thousand inserts caused nine resizes and fifteen hundred forty-two relinks, one and a half per insert. And the payoff is dramatic. Five thousand random keys, in a table stuck at eleven buckets, made a longest chain of four hundred eighty-eight, and about two hundred twenty-eight comparisons per lookup. The same keys, with growth at point seven five, ended in eleven thousand, two hundred sixty-four buckets. The longest chain was four, and the average, one point two three.
Worst Case
Every Key in One Bucket
All of this assumes the hash function spreads keys. Put every key into one bucket, and you get one long linked list. A hundred keys average fifty point five comparisons; five thousand average two thousand, five hundred. That's n plus one over two, like any linear search. Chaining is only as good as its hash function.
Comparison
Absent-Key Costs Across Methods
How does chaining compare with open addressing? Here are measured averages for an absent key, on tables of one thousand and nine slots. At a load factor of one half, the plans are close. By point nine, linear probing needed about forty-one comparisons to prove a key absent, quadratic about ten, and chaining point nine. And chaining can go past a load factor of one, where open addressing can't go at all.
Trade-Offs
When to Choose Each Plan
Speed isn't everything. Choose chaining when the number of entries is hard to predict, when entries are removed often, or when the load may run high. Choose open addressing when memory per entry matters, since chaining spends a node object per entry. It also suits sparse tables, with rare removals. Neither plan wins in every situation, and the measurements show why a simple answer would mislead.
Java Library
HashMap as a Chained Table
Java's HashMap is a chained table. Each node stores four things: the hash, the key, the value, and a next reference. It starts with sixteen buckets, and doubles when the load factor would pass point seven five: at the thirteenth entry, then the twenty-fifth, forty-ninth and ninety-seventh. It keeps its bucket count a power of two, so it can pick a bucket by keeping only the low bits of the hash code. That's fast, but risky when hash codes differ only in their upper bits.
Hash Mixing
Folding High Bits Into Low Bits
So HashMap mixes the upper half of the hash code into the lower half first: h exclusive-or h shifted right sixteen, then the low bits. Take eight keys, sixty-five thousand five hundred thirty-six times one through eight. Each has zeros in its low sixteen bits. Low bits alone send all eight to bucket zero. With the mixing step, they spread over buckets one to eight.
Safety Net
Long Chains Become Trees
Even a good table can meet a bad hash code, one that returns the same number for every key. Then a chain grows long, and every lookup is a linear search. HashMap defends itself by turning a long chain into a tree. In OpenJDK twenty-one, a chain may become a tree once it passes eight entries, but only when there are at least sixty-four buckets. So with keys that all collide, the ninth entry doubles the buckets to thirty-two instead, and the tenth to sixty-four. The eleventh finally turns the chain into a tree. It's a red-black tree, a balanced tree that finds a key in about log n steps. Once the bucket gets small again, it turns back into a chain.
Measured Results
Trees Need Comparable Keys
But a tree only helps if it can choose a branch. This program stores five thousand keys that all share hash code forty-two, then looks each one up, counting calls to equals. With Comparable keys, a lookup took about thirteen calls, close to log two of five thousand, which is about twelve point three. Without Comparable, HashMap still builds a tree, but can't tell which branch to follow, so it searches both: two thousand, five hundred calls, no better than a plain chain. Treeification is a safety net, not normal life. With a decent hash code, it almost never happens.
Common Mistakes
Six Ways Chaining Goes Wrong
A few mistakes to avoid. Changing a key after storing it: lookups by the old or the new value both fail. Use keys that can't change. Overriding equals without hash code: equal keys land in different buckets. And a hash function that uses few buckets turns lookups into linear searches. Never growing the table, using percent on a negative hash code, and expecting trees to rescue a bad hash: each one was shown to fail.
Key Takeaways
Chains, Load and Growth
To sum up. Separate chaining gives each bucket a linked list. Insert, find and remove walk one chain, and remove simply unlinks a node. The load factor is entries over buckets, and it can pass one. An absent key costs about L comparisons, a present key about one plus L over two. Doubling the buckets keeps the load factor in check, at about one and a half relinks per insert. HashMap is a chained table that mixes hash codes, grows at point seven five, and turns long chains into trees, which help only with Comparable keys.
Think About It
A Million Entries, a Thousand Buckets
Something to think about. A service stores a million entries in a chained table of a thousand buckets that never grows. Estimate the average chain length, and the cost of present and absent lookups. What change would repair it, what does that change cost while it happens, and why couldn't open addressing work here at all?
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 Separate Chaining: Linked Buckets
What is separate chaining in a hash table?
What is the expected cost of a lookup with separate chaining?
Is separate chaining better than open addressing?
When does Java's HashMap turn a bucket into a tree?
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 →