UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 14.3 Free with a free account
Hash Tables: The Array Behind Near-Instant Lookup
Data Structures and Algorithms · Chapter 14: Maps and HashingSection 14.3 · lesson 58 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: Open Addressing: Linear and Quadratic Probing →← Hash Functions: Spreading Keys Evenly Across SlotsNext lesson: Open Addressing: Linear and Quadratic Probing →
In this lesson
How Java's HashMap uses buckets, load factor and resizing.
- Trace how put, get and remove find a bucket from a hash code
- Explain load factor, resizing and why entries move during a rehash
- Presize a HashMap and predict when it will double its buckets
- Identify hash codes and key changes that destroy expected constant time
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,488 words). Read along, or search it.
Opening Question
Lockers Opened by Number
Picture a wall of numbered lockers. If you're told your bag is in locker thirteen, you walk straight to it. You don't open lockers one by one. A hash table works the same way. It keeps its data in an array of numbered buckets, and it uses the key itself to work out the bucket number. So here's the puzzle: why does finding one entry among a million take about as long as finding one among ten? And when does that promise break?
Ingredients
Buckets, Hash Codes and Index Rules
A hash table has three ingredients: an array whose positions are called buckets, a hash code computed from each key, and a rule that turns the hash code into a bucket index. Take the key Ava in a table of sixteen buckets. Its hash code is sixty-six thousand, two hundred twenty. A good mental model is: hash code mod the number of buckets, which gives twelve. But Java mixes the bits of the hash code first, and the real bucket is thirteen. Java keeps the bucket count a power of two, so it can keep just the last few bits, which is a fast way to take the remainder.
Worked Example
Eight Names in a Real HashMap
Here are eight names placed by a real HashMap, read from inside the running table. Hal went to bucket two, Eli three, Gus four, Dee five, and Cy six. Ben went to ten, Ava thirteen, and Fay fifteen. Eight entries, eight different buckets, and nothing was searched to put them there.
Operations
Put, Get and Remove Share a Path
Put, get and remove all begin the same way: compute the hash code, turn it into a bucket index, go to that bucket. Only what happens there differs. Put replaces the value of a key that's present and returns the old value, or adds the entry and returns null. Get returns the value, or null. Remove deletes the entry and returns the old value, or does nothing and returns null. Inside the bucket, keys are compared with equals, not with double equals. Two different String objects holding the same text find the same entry.
Load Factor
Growing Past Three Quarters
Sixteen buckets can't comfortably hold a million entries. The buckets would be crowded, and lookups would slow down. So a hash table must grow. Its measure is the load factor: the number of entries divided by the number of buckets. Java's default limit is zero point seven five. When one more entry would push the count past three quarters of the buckets, the map resizes. Resizing means allocating a new array twice as large. Rehashing means placing every existing entry into it again.
Worked Example
Watching a HashMap Double
Watching a default HashMap grow shows the rule at work. A new map has no array at all until the first put, which creates sixteen buckets. The thirteenth entry passes twelve, three quarters of sixteen, so the array doubles to thirty-two. Then the twenty-fifth entry doubles it to sixty-four, the forty-ninth to one hundred twenty-eight, and so on.
Rehashing
Why Entries Move on Resize
Why must every entry be placed again? Because the bucket index depends on the number of buckets. When the map grew from sixteen to thirty-two buckets, Cy moved from bucket six to twenty-two, Fay from fifteen to thirty-one, and Hal from two to eighteen. The other five kept their index. One bit of the mixed hash code decides whether a key moves. A lookup that used the old index after a resize would fail.
Presizing
Requesting Buckets Up Front
A resize touches every entry, so the put that triggers it is expensive. But because the array doubles, resizes get rarer as the map grows. Storing a million integers caused eighteen changes of the array: the creation, plus seventeen doublings, ending at about two million buckets. If you know how many entries are coming, ask for enough buckets up front. There's a catch: the number you request is rounded up to a power of two, and the limit is still three quarters of that. Ask for thirteen, and you get sixteen buckets with a limit of twelve, so the thirteenth entry still resizes. To hold n entries without resizing, request about n divided by zero point seven five.
Quick Check
A HashMap Created for One Hundred
Quick check. A program will store exactly one hundred entries, so it creates new HashMap of one hundred. Does the map resize while those hundred entries go in, and if so, when? Pause, and decide. It's b. A hundred is rounded up to the next power of two: one hundred twenty-eight buckets. Three quarters of that is ninety-six. So the ninety-seventh entry pushes past the limit, and the whole table is rehashed into two hundred fifty-six buckets. Requesting about one hundred thirty-four would have avoided it.
Trade-Off
Why Zero Point Seven Five
Why zero point seven five? It's a compromise between memory and speed. To see it, store a hundred thousand random integers, with the map forbidden to resize. With default growth, two hundred sixty-two thousand buckets: more than two in three are empty, and the longest bucket holds six. Squeeze them into a thousand twenty-four buckets, and the longest holds a hundred thirty-one. Into sixty-four buckets, and it holds over sixteen hundred. Crowded buckets mean slower lookups.
Expected Time
What Expected Order One Means
The promise of hashing is expected order one time for put, get and remove. Read each word carefully. Expected means on average, over typical keys, not a guarantee for every single operation. Order one means the cost doesn't grow with the number of entries. And the condition: the keys must spread evenly over the buckets. Measured on one machine, a thousand times more data made a HashMap lookup about six times slower, a TreeMap about eleven times, and a list search far worse.
Failure Mode
One Hash Code for Every Key
Three things break the promise. First, a poor hash code. If every key reports the same hash code, every key lands in one bucket, and the map behaves like one long list. Measured on one machine, thirty-two thousand such keys took over thirteen seconds to put and get, against two milliseconds with a good hash code. Each doubling multiplied the time by four to eight. Java has a safety net for comparable keys: it reorganizes a crowded bucket so it can still be searched quickly. That helps, but it doesn't make a poor hash code acceptable.
Failure Modes
Changed Keys and Mismatched Equals
Second: a key that changes after it's stored. The bucket was chosen from the key's hash code at the moment of put. Store a person whose hash code uses the name amy, then change the name to amelia. Get now returns null, contains key says false, and yet size still says one. The entry is stranded. Third: overriding equals without hash code. Two equal keys get different hash codes, so get with an equal key returns null. The cure for all three: a hash code that uses the key's fields, keys that never change, and equals and hash code overridden together.
Java Tour
Merge, Contains Value and Bucket Order
Now a tour of Java's HashMap. Contains value has no index for values, so it examines every entry: order n. Merge stores a value, or combines it with the old one. Counting words becomes one line: merge the word with one, using integer sum. Store one if the word is new, otherwise add one. Print the counts, and the order is neither the sentence's nor alphabetical. A HashMap iterates by bucket number. Keys forty, seven, twenty-five, three and eighteen printed as eighteen, three, seven, forty, twenty-five: buckets two, three, seven, eight and nine.
Alternatives
LinkedHashMap, TreeMap and HashSet
The order can even change when the map resizes, so never depend on it. When order matters, choose another map. A LinkedHashMap remembers insertion order, at the same expected cost. A TreeMap keeps keys sorted, at order log n, and offers first key, floor key and ranges. A HashMap also accepts one null key, which a TreeMap with natural ordering rejects. And a HashSet is a HashMap in disguise: its elements are the map's keys.
Quick Check
Printing Integer Keys by Bucket
Quick check. A new HashMap of Integer keys, with sixteen buckets, receives the keys twenty, five and thirty-five, in that order. Then the program prints the key set. What does it print? Pause, and predict. It's c. A small Integer's hash code is the number itself, so with sixteen buckets, thirty-five goes to bucket three, twenty to bucket four, and five to bucket five. Iteration follows the buckets. Option a is insertion order, which a LinkedHashMap would give, and option b is sorted order, which a TreeMap would give.
Key Takeaways
Buckets, Load and Expected Time
To recap. A hash table is an array of buckets, and a key is turned into a bucket index, so a lookup jumps straight to one place. The load factor is entries over buckets. Java doubles the array past zero point seven five, and rehashes every entry, because the index depends on the bucket count. Expected order one is an average that needs well spread hash codes, keys that never change, and equals with hash code. And a HashMap has no useful order.
Think About It
Choosing a Load Factor Limit
Here's something to think about. Why does Java choose a limit of zero point seven five rather than one, or zero point five? What would each of those choices cost, in memory and in lookup time?
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 Tables: The Array Behind Near-Instant Lookup
What is the load factor of a Java HashMap?
Why do entries move to new buckets when a HashMap resizes?
How do you presize a HashMap to avoid resizing?
What makes HashMap lookups slow?
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 →