UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 14.2 Free with a free account
Hash Functions: Spreading Keys Evenly Across Slots
Data Structures and Algorithms · Chapter 14: Maps and HashingSection 14.2 · lesson 57 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: Hash Tables: The Array Behind Near-Instant Lookup →← Maps: Pairing Unique Keys With Their ValuesNext lesson: Hash Tables: The Array Behind Near-Instant Lookup →
In this lesson
Hash codes, compression functions and collisions in Java hash tables.
- Explain the hashCode contract and why equals and hashCode must agree
- Compute polynomial string hash codes with Horner's rule
- Apply division and MAD compression safely, including negative hash codes
- Explain why collisions are unavoidable and how prime table sizes spread keys
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,695 words). Read along, or search it.
Opening Question
The Coat Check Problem
Imagine a coat check with seven numbered hooks. A coat arrives with a name tag, and the attendant must turn that name into a hook number. It has to be the same number every time the same name comes back, and the coats should spread across the hooks. A hash function does exactly this for a program: it turns a key into a slot number. Its quality decides whether lookups are fast, or painfully slow.
Two Steps
Hash Code, Then Compression
Keys can be words, numbers, dates or whole objects, but a slot number is a small integer from zero to N minus one. So the work is split into two steps. Step one, the hash code: the key's own type turns it into any int, which may be huge, or negative. The string cat gives ninety-eight thousand, two hundred sixty-two. Step two, the compression function, squeezes that into the range of slots. With seven slots, cat lands in slot three. The key's type writes step one, because it knows its own insides. The hash table does step two, because only it knows N. Each step can be improved without touching the other.
Built-In Hash Codes
How Java Types Hash Themselves
Every Java object can produce a hash code. For an Integer, it's the value itself. A Long folds its two 32-bit halves together with exclusive or, so two to the thirty-second plus five gives four. A Double folds its bits the same way. Booleans use two fixed numbers, a character uses its code, and a string uses a polynomial over its characters. Now look at the last two lines. The different strings capital A small a, and capital B capital B, share the hash code twenty-one twelve. That's not bad design. There are far more possible strings than 32-bit ints, so some different keys are bound to share one.
The Contract
Three Rules Every Hash Code Obeys
A hash table trusts the hash code completely, so Java states rules it must obey: the contract. One: consistent. An unchanged object gives the same hash code every time within a run, or a key stored in one slot is searched for in another. Two: if a equals b, then their hash codes must be equal, or equal keys are looked for in different slots. Three: different objects may share a hash code. Nothing breaks; it's only slower. So equal codes never prove equal keys: always confirm with equals.
Worked Example
BadPoint Versus GoodPoint
The second rule is the one programmers break. Whenever a type overrides equals to compare fields, it must override hash code using the same fields. BadPoint forgets: it has no hash code method of its own. GoodPoint follows the contract, using the helper Objects dot hash, which combines the fields it's given. Both types say the two points are equal. But BadPoint inherits the default hash code, which depends on the object itself, so equal points get different codes. So a hash set can't find an equal BadPoint. GoodPoint gives both points the code ten fifty-eight, and the same lookup succeeds. The rule is simple: override both, or neither.
Common Mistake
Changing a Stored Key
There's a second way to break rule one. If the fields that hash code reads change after the key is stored, its hash code changes, and so does its slot. This Tag hashes its label. Labeled red, it goes to slot sixty-nine of a hundred and one. Relabeled blue, it would go to slot sixty-four. The old slot still holds the entry, but nobody will look there anymore. So keys should be immutable, or at least never changed while they're stored.
String Hashing
Summing Versus Polynomial Codes
How should a string's hash code be computed? Each character has a numeric code: small a is ninety-seven. The simplest idea adds the codes up. It's quick, but it ignores order, so every rearrangement of the same letters gets the same code. The polynomial version multiplies the running total by a number a before adding each character, so a character's position matters.
Example
Six Anagrams, One Sum
Six words, stop, pots, tops, spot, opts and post, are rearrangements of the same four letters. The sum can't tell them apart: every one gets four fifty-four. The polynomial gives six different codes.
Horner's Rule
Computing the Polynomial Efficiently
The polynomial rule picks a multiplier a. The first character is multiplied by a to the power n minus one, the next by one power less, and so on. The last character is simply added. Computing the powers separately would be wasteful. Horner's rule gets the same result with one multiplication and one addition per character: h becomes h times a, plus the code. For cat with a equal to thirty-one: ninety-nine; then ninety-nine times thirty-one plus ninety-seven, three thousand, one hundred sixty-six; then ninety-eight thousand, two hundred sixty-two. That matches cat's own hash code, so Java's string hash is this polynomial, with thirty-one. When the value outgrows an int, Java silently drops the high bits. That's harmless: it's still the same every time.
Choosing a Multiplier
Counting Distinct Codes per Multiplier
The multiplier matters. This program hashes ten thousand keys, I D dash zero zero zero zero to I D dash nine nine nine nine, and counts the different hash codes for each multiplier. A multiplier of one is the plain sum, and ten thousand keys share only thirty-seven codes. Two gives just one hundred thirty-six. Thirty-one, thirty-three and thirty-seven keep all ten thousand apart. Small odd primes in this range are the usual choice.
Quick Check
Hashing ba With Thirty-One
Quick check. Using the polynomial rule with thirty-one, what's the hash code of the string b a? And does it collide with a b? Remember, b is ninety-eight and a is ninety-seven. Pause and predict. Three thousand, one hundred thirty-five, and no collision. Start at zero: ninety-eight, then ninety-eight times thirty-one plus ninety-seven. The string a b gives three thousand, one hundred five, a different code. One hundred ninety-five is the plain sum, which would make b a and a b collide. That's exactly the flaw the polynomial fixes.
Compression
Division and MAD Methods
Now step two. A hash code can be any int, but there are only N slots. Two compression functions are in common use. The division method takes the remainder after dividing by N. The MAD method, multiply, add and divide, scrambles the code first, using a large prime p.
Common Trap
Negative Remainders in Java
Division has a trap. In Java, the percent operator keeps the sign of the first number, so a hash code of minus seven, mod five, gives minus two: not a valid slot. Wrapping h in Math dot abs looks like a repair, and works for minus seven. But the smallest int has no positive twin: its absolute value is still negative, and the slot comes out minus three. Math dot floor mod is always between zero and N minus one. Never write h percent N, or Math dot abs of h, for a slot.
Table Size
Prime Sizes Break Patterns
The size N matters too. Suppose a hundred keys have hash codes zero, four, eight, and so on, every multiple of four, and there are twenty slots. Four and twenty share the factor four, so the remainders can only be zero, four, eight, twelve or sixteen. Only five slots are used, with twenty keys in each. With nineteen slots, a prime, every slot is used, and the largest holds only six. A prime shares no factor with a pattern in the data, unless the pattern is a multiple of the prime itself. And MAD, on the same twenty slots, reaches all twenty, with six at most in any of them.
MAD Method
Multiply, Add and Divide
When a prime size isn't possible, MAD helps. Slot equals a times h plus b, mod p, then mod N, where p is a prime larger than N. The multiplication by a, and the reduction mod p, break up patterns before the final mod N. One caution: a must be large enough for a times h to wrap around p. A tiny a leaves the pattern intact.
Collisions
Pigeonhole Collisions
A collision happens when two different keys are sent to the same slot. The keys may share a hash code, like capital A small a and capital B capital B, or the compression may map different codes together. Here, eight three-letter words go into seven slots. Bee and hen share slot five, and dog and fox share slot six. With eight keys and seven slots, two must share. That's the pigeonhole principle.
Birthday Problem
Collisions Arrive Early
Surprisingly, collisions arrive much earlier than that. This program drops random keys into three hundred sixty-five slots, twenty thousand times for each count. Five keys collide about three percent of the time, and ten keys, about twelve. With only twenty-three keys, a collision is already as likely as not: fifty point one percent. So hash tables can't hope to avoid collisions. They must handle them, and the hash function's job is to keep them few, and evenly shared.
Measured Spread
Counting Keys per Slot
The best test of a hash function is to count the keys in each slot. Two thousand keys go into fifty slots, so a perfect spread puts forty in each. The sum of characters is a disaster: twenty-one slots stay empty, and the busiest holds one hundred fifty, almost four times the ideal. The polynomial with division fills every slot, and the largest holds forty-two. With MAD, too, no slot is empty, and the largest holds forty-eight.
Quick Check
Multiples of Six and Table Size
Quick check. A batch of keys has hash codes that are all multiples of six: zero, six, twelve, and so on. They're compressed with the division method. Which table size spreads them best? Pause, and decide. Thirteen. It's prime, and shares no factor with six, so the remainders reach all thirteen slots. Twelve shares the factor six, so only slots zero and six are ever used. Eighteen shares six too: only zero, six and twelve.
Summary
Properties of a Good Hash Function
So a good hash function is consistent, and gives equal keys equal codes. It uses the whole key, so similar keys don't land together. It spreads keys evenly, always produces a valid slot, and it's fast, since it runs on every single lookup.
Key Takeaways
Codes, Compression and Collisions
To sum up. A hash function has two steps: a hash code from the key, then compression into a slot number. If equals is overridden, hash code must be too, on the same fields. And keys must not change while they're stored. For strings, use the polynomial rule with Horner's method and a multiplier like thirty-one. Compress with Math dot floor mod, a prime size or MAD. And plan for collisions: they're certain.
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 Hash Functions: Spreading Keys Evenly Across Slots
Why must you override hashCode when you override equals in Java?
How does Java's String hashCode work?
Why use Math.floorMod instead of % when compressing a hash code in Java?
Why should a hash table size be a prime number?
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 →