Safe keys
Use it when the thing you look up has several parts, is a collection, or is a number written in more than one way. Use it also when the order of the output must not depend on the table. Signal words: a key made of several fields, in any order, the same number written in different ways, the same on every server.
the whole pattern cardfold it
Start decide what "the same" means for two items. Then write the key as one fixed value that is equal exactly for items that are the same.
Step build the key from a copy of the item, never from a value that can change later. Look it up. Then add it, or count it.
Stop when the items run out. Take the output order from the input, not from the table.
It does not answer questions about order or range, such as the next key above a value. A hash table has no order.
Cost: O(n) set steps on average, plus the cost of building and hashing one key for each item. For a key of k parts, that is O(n × k). The comparison of every pair costs O(n^2).
In this lesson you learn what a hash table needs from its keys. You build keys that stay correct for pairs, for collections and for numbers, and you see how each language behaves when a key is wrong.
1. Scenario: the cache entries of a sale#
An online store caches the result page of every search, so that it does not build the same page twice. A page is found by two numbers: the category and the page number.
Your team lead says: Before the sale starts, tell me how many different cache entries the day's requests need, so that we can size the cache.
The log of one day holds 100,000 requests, and the cache is sized again every morning.
Here is a short test. The requests, as (category, page), are (1, 23), (12, 3), (1, 23), (2, 5), (12, 3) and (30, 1). The answer is 4, because (1, 23) and (12, 3) each come twice.
So the task is this: count the different pairs, without comparing every request with every other request. The hard part is to decide what makes two requests the same.
Think about a left-luggage room at a station. You hand in a bag and get a ticket with a number. Later, the attendant reads the number on your ticket and goes straight to the right locker.
This works only if three things are true. No two bags have the same ticket number. A ticket never changes its number after it is given out. And the attendant always reads a number the same way.
The locker is the entry of a hash table, and the ticket is its key. Every pitfall in this lesson breaks one of the three rules.
Like a left-luggage room: the ticket is the key, so it must be unique, must never change, and must always be read the same way.
2. Struggle: solve it by hand first#
Before you write code, solve the test by hand.
Solve it by hand: The day's requests, counted by pair. The hand-solve sheet loads in your browser.
You write the requests in a row. You keep a list of the different pairs found so far. For each request, you compare it with the pairs in the list, one by one, and you add it when no pair matches.
Requests: (1, 23), (12, 3), (1, 23), (2, 5), (12, 3), (30, 1).
| Request | List of different pairs before | Comparisons | Result |
|---|---|---|---|
| (1, 23) | empty | 0 | new |
| (12, 3) | (1, 23) | 1 | new |
| (1, 23) | (1, 23), (12, 3) | 1: found at once | already there |
| (2, 5) | (1, 23), (12, 3) | 2 | new |
| (12, 3) | (1, 23), (12, 3), (2, 5) | 2: found second | already there |
| (30, 1) | (1, 23), (12, 3), (2, 5) | 3 | new |
The search made 0 + 1 + 1 + 2 + 2 + 3 = 9 comparisons, and the list holds 4 pairs. If every request had been new, it would have made 15.
Look at what grows. Six requests need up to 6 × 5 / 2 = 15 comparisons. A day of n requests needs up to n × (n − 1) / 2.
The first attempt#
You turn the hand method into code.
Start with a correct version. Keep a list of the different pairs, and search it for every request.
def distinct_pairs(firsts, seconds):
pairs = []
for i in range(len(firsts)):
found = False
for pair in pairs: # every pair found so far
if pair == (firsts[i], seconds[i]):
found = True
break
if not found:
pairs.append((firsts[i], seconds[i]))
return len(pairs)This is correct. When many requests are different, each one is compared with many pairs, which is O(n^2) comparisons.
The scale check#
Now check the real day.
The log holds 100,000 requests, and many of them are different pairs.
Here is the count for a day in which almost every request is a different pair:
- Comparisons: 100,000 × 99,999 / 2, which is about 5 × 10^9.
- Time: at about 10^8 simple steps a second, that is about 50 seconds.
So the morning count takes about a minute, and the team wants it to be instant.
Predict the cost
Q A day holds 60,000 requests, and every request is a different pair. About how many comparisons does the first attempt make?
Answer & explanation
Answer: C
The number of comparisons is n × (n − 1) / 2, which is 1,799,970,000 for 60,000 requests. The answer 3.6 × 10^9 forgets the halving: each pair of requests is compared once, not twice. At 10^8 steps a second that is about 18 seconds.
The first attempt is correct, but it compares pairs of requests, and there are far too many of them. Now the team looks for a better way.
3. See: a key is what you compare#
Can we do better?#
A set answers "have I seen this?" in one step on average. So put a key for each request in a set, and the size of the set is the answer.
The whole question is the key. A hash table finds an entry by two steps: it hashes the key to choose a bucket, and then it compares the keys in that bucket. So the key must be equal for two requests exactly when they ask for the same category and the same page.
The category and the page are two numbers, and the key must keep both. The simplest key is the pair itself, as one value: a tuple in Python. The pair (12, 3) is then different from (1, 23), because a tuple compares each part.
For each request:
- Build the key: the pair as one value.
- Look it up in the set, and add it.
| Position | Request | Key | Key in the set? | Set after |
|---|---|---|---|---|
| 0 | (1, 23) | (1, 23) | no: new | (1, 23) |
| 1 | (12, 3) | (12, 3) | no: new | (1, 23), (12, 3) |
| 2 | (1, 23) | (1, 23) | yes | unchanged |
| 3 | (2, 5) | (2, 5) | no: new | 3 keys |
| 4 | (12, 3) | (12, 3) | yes | unchanged |
| 5 | (30, 1) | (30, 1) | no: new | 4 keys |
Six requests cost 6 keys and 6 lookups. The list search made 9 comparisons here, and up to 15 in the worst case.
Race: Compare with every earlier pair, against one key and one set step. The operation counter loads in your browser.
The race counts the worst case, where every request is a different pair. At 10,000 requests the list search makes 49,995,000 comparisons. The set makes 20,000 operations, one key and one lookup for each request. That is about 2,500 times less, and the gap grows with n.
The key is the pair, kept as one value, so a set finds a repeated request in one step and the size of the set is the answer.
The requests are (1, 23), (12, 3), (1, 23), (5, 15) and (51, 5). Written one after the other, the first three read 123, 123 and 123, and the last two read 515 and 515. The player stops at five steps and asks you to predict.
Dry run: Predict each step: pairs that read the same when glued. The step-by-step player loads in your browser.
Reading without the player? Cover the last column and predict it row by row.
| Position | Request | Key | Key in the set? | Different pairs after |
|---|---|---|---|---|
| 0 | (1, 23) | (1, 23) | no | 1 |
| 1 | (12, 3) | (12, 3) | no | 2 |
| 2 | (1, 23) | (1, 23) | yes | 2 |
| 3 | (5, 15) | (5, 15) | no | 3 |
| 4 | (51, 5) | (51, 5) | no | 4 |
Look at position 1. The text 123 would be the same for (1, 23) and for (12, 3), but the pairs are different. A key that keeps the pair as a pair never confuses them. A key made by gluing the numbers would stop at 2 different pairs here, and the right answer is 4.
4. Shape: the pattern#
Here is the rule that keeps both templates correct. Every line exists to protect it.
After i requests, the set holds one key for each different pair, and two requests share a key exactly when both numbers are equal.
At the start no request is read and the set is empty, so the rule holds. Say it holds after i requests. Look at the next request and build its key from both numbers. A key made of several parts is called a composite key.
If an earlier request has the same pair, it built the same key, and the set already holds it. If no earlier request has the same pair, the key is different from every key in the set, so adding it makes the set one key larger.
So the set always holds exactly one key for each different pair. The whole proof rests on the last words of the invariant: the key must be equal for equal pairs and different for different pairs.
Use it when the thing you look up has several parts, is a collection, or is a number written in more than one way. Use it also when the order of the output must not depend on the table. Signal words: a key made of several fields, in any order, the same number written in different ways, the same on every server.
Start: decide what "the same" means for two items. Then write the key as one fixed value that is equal exactly for items that are the same.
Step: build the key from a copy of the item, never from a value that can change later. Look it up. Then add it, or count it.
Stop: when the items run out. Take the output order from the input, not from the table.
It does not answer questions about order or range, such as the next key above a value. A hash table has no order.
Cost: O(n) set steps on average, plus the cost of building and hashing one key for each item. For a key of k parts, that is O(n × k). The comparison of every pair costs O(n^2).
Template 1: a pair as a key#
def distinct_pairs(firsts, seconds):
# [1] A set of keys, one for each different pair.
seen = set()
for i in range(len(firsts)):
# [2] The key keeps the pair as a pair, with both numbers in it.
# A tuple compares both parts and never glues them.
key = (firsts[i], seconds[i])
# [3] The same pair always gives the same key, and different pairs give different keys.
seen.add(key)
# [4] The number of different pairs.
return len(seen)public int distinctPairs(int[] firsts, int[] seconds) {
// [1] A set of keys, one for each different pair.
java.util.HashSet<Long> seen = new java.util.HashSet<>();
for (int i = 0; i < firsts.length; i++) {
// [2] The key keeps the pair as a pair, with both numbers in it.
// Pack both ints into one long, and mask the second so that its sign does not spill into the first.
long key = ((long) firsts[i] << 32) | (seconds[i] & 0xFFFFFFFFL);
// [3] The same pair always gives the same key, and different pairs give different keys.
seen.add(key);
}
// [4] The number of different pairs.
return seen.size();
}int distinctPairs(vector<int>& firsts, vector<int>& seconds) {
// [1] A set of keys, one for each different pair.
unordered_set<long long> seen;
for (size_t i = 0; i < firsts.size(); i++) {
// [2] The key keeps the pair as a pair, with both numbers in it.
// Pack both ints into one 64-bit number, and mask the second so that its sign does not spill into the first.
long long key = ((long long)firsts[i] << 32) | (unsigned int)seconds[i];
// [3] The same pair always gives the same key, and different pairs give different keys.
seen.insert(key);
}
// [4] The number of different pairs.
return (int)seen.size();
}function distinctPairs(firsts, seconds) {
// [1] A set of keys, one for each different pair.
const seen = new Set();
for (let i = 0; i < firsts.length; i++) {
// [2] The key keeps the pair as a pair, with both numbers in it.
// Join the two numbers with a separator that cannot appear in a number.
const key = firsts[i] + "," + seconds[i];
// [3] The same pair always gives the same key, and different pairs give different keys.
seen.add(key);
}
// [4] The number of different pairs.
return seen.size;
}Template 2: a snapshot of a collection as a key#
def distinct_filter_sets(filters):
# [1] A set of keys, one for each different set of filters.
seen = set()
for row in filters:
# [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
# A list cannot be a key in Python, and a frozenset can.
key = frozenset(row)
# [3] The copy never changes, even if the row is edited later.
seen.add(key)
# [4] The number of different sets.
return len(seen)public int distinctFilterSets(int[][] filters) {
// [1] A set of keys, one for each different set of filters.
java.util.HashSet<java.util.Set<Integer>> seen = new java.util.HashSet<>();
for (int[] row : filters) {
// [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
// A new set compares by its contents, and the copy is separate from the row.
java.util.Set<Integer> key = new java.util.HashSet<>();
for (int tag : row) {
key.add(tag);
}
// [3] The copy never changes, even if the row is edited later.
seen.add(key);
}
// [4] The number of different sets.
return seen.size();
}int distinctFilterSets(vector<vector<int>>& filters) {
// [1] A set of keys, one for each different set of filters.
set<set<int>> seen;
for (const vector<int>& row : filters) {
// [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
// unordered_set has no hash for a set, so an ordered set of sets does the comparing.
set<int> key(row.begin(), row.end());
// [3] The copy never changes, even if the row is edited later.
seen.insert(key);
}
// [4] The number of different sets.
return (int)seen.size();
}function distinctFilterSets(filters) {
// [1] A set of keys, one for each different set of filters.
const seen = new Set();
for (const row of filters) {
// [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
// A string of the sorted, distinct tags works, because an array would be compared by identity.
const key = [...new Set(row)].sort((a, b) => a - b).join(",");
// [3] The copy never changes, even if the row is edited later.
seen.add(key);
}
// [4] The number of different sets.
return seen.size;
}Rebuild the template: put its lines back in order. Loads in your browser.
The key keeps the pair as a pair: a tuple in Python, a packed long in Java and C plus plus, and a joined string in JavaScript.
A warehouse robot logs its cell as (row, column) after every move. The log is (0, 0), (0, 1), (1, 1), (0, 1), (1, 0), (1, 1). How many different cells did it visit?
This is Template 1 with a new meaning for the two numbers. Nothing else changes.
| Position | Cell | Key | Key in the set? | Different cells after |
|---|---|---|---|---|
| 0 | (0, 0) | (0, 0) | no | 1 |
| 1 | (0, 1) | (0, 1) | no | 2 |
| 2 | (1, 1) | (1, 1) | no | 3 |
| 3 | (0, 1) | (0, 1) | yes | 3 |
| 4 | (1, 0) | (1, 0) | no | 4 |
| 5 | (1, 1) | (1, 1) | yes | 4 |
The robot visited 4 different cells. The key was a pair of coordinates.
Complexity in plain words#
- Time. The pass reads each request once, builds one key, and makes one lookup and at most one insert. A key is not free: a key of k parts costs about k steps to build and about k more to hash, so the pass is O(n × k). For a pair, k is 2.
- At scale. For 100,000 requests, the set makes about 200,000 steps. The list search needs about 5 × 10^9 comparisons.
- Worst case. If many different keys land in one bucket, each lookup compares with many keys. Hash collisions never change the answer, because the table compares the keys, and they only cost time. The stretch beat shows how much.
- Space. The set holds one key for each different pair. That is O(n) keys, and each key holds k parts.
- Trade. The list search stores one copy of each different pair. The set stores the same pairs and adds the table. That memory buys the drop from billions of comparisons to a few hundred thousand steps.
5. Stretch: edges, mistakes and variations#
Edge cases#
Real production data brings edge cases.
Before the first request, firsts = [] and seconds = []. The loop never runs, and the template returns 0. A day with one request, firsts = [7] and seconds = [7], returns 1.
For filters = [[]], the answer is 1, because a shopper who turned no filter on is a real request. For filters = [[], []] it is still 1, since both rows are the empty set. For filters = [] it is 0. An empty collection is a valid key.
For filters = [[1, 1, 2], [2, 1]], the answer is 1. The rows hold the same tags, in another order, with 1 repeated, so they are one set. A key made of the sorted list would still count 2, because the repeat stays in the list. Collapse the repeats as well as the order.
For firsts = [1, -1] and seconds = [-1, -1], the answer is 2. In Java and C++ a negative second number has a long run of 1 bits, so it must be masked before it is packed. Python and JavaScript need no mask, because a tuple and a joined string hold the numbers as they are.
The mistake museum#
This version writes the two numbers one after the other, and uses the text as the key. It looks fine on small numbers. Different pairs can give the same text.
Counterexample: firsts = [1, 12], seconds = [23, 3]. Both pairs read 123, so the bug returns 1, and the right answer is 2.
How often does it bite? For categories 1 to 99 and pages 1 to 99, there are 9,801 pairs and only 9,072 different texts, so 729 pairs are lost.
Keep the pair as a pair, or put a separator between the numbers, such as 1,23 and 12,3.
Writing two numbers one after the other is a bad key: one and twenty-three, and twelve and three, both read one two three.
This Java or C++ version packs the two numbers into one 64-bit number with |, and forgets to mask the second one. A negative int is widened with its sign bits, and those bits overwrite the first number.
Counterexample: firsts = [1, -1], seconds = [-1, -1]. Both pairs pack to the same 64-bit number, all ones, so the bug returns 1, and the right answer is 2.
Mask the second number: seconds[i] & 0xFFFFFFFFL in Java, and (unsigned int)seconds[i] in C++.
In Python, a list or a set cannot be a key at all: {[1, 2]: "x"} raises TypeError: unhashable type: 'list', and so does a tuple that holds a list. Java and JavaScript accept a mutable key, which is worse.
Counterexample: In Java, key = new ArrayList<>(List.of(1, 2)), then map.put(key, "v"), then key.add(3). After that, map.get(key) is null, map.containsKey(key) is false, and map.size() is still 1. The entry sits in the bucket of the old hash, and every lookup goes to the bucket of the new hash.
The old contents do not find it either. map.get(List.of(1, 2)) goes to the right bucket, but the stored key now holds [1, 2, 3]. So equals fails, and the answer is null. The entry can no longer be reached at all.
In JavaScript, a Map compares an array key by identity, so get([1, 2]) with a new array finds nothing even before any edit. In C++ the keys of a map are const, so the edit has to hide behind a pointer.
Copy the collection into a fixed form before you store it, as Template 2 does.
A list used as a key and edited later is lost: in Java the size stays one, but the lookup finds nothing.
A running total of amounts is kept as a floating-point number, and the total is used as a key. Floating-point numbers round.
Counterexample: 0.1 + 0.2 is 0.30000000000000004 in Python, Java, C++ and JavaScript. A map that holds the key 0.1 + 0.2 does not find 0.3, in any of the four.
Keep money and measures as whole numbers, such as cents, or as a canonical text. The practice problem on decimal ids shows the second way.
A report is built by looping over a table, and its order is printed as it comes. A table keeps no order you can rely on, and each language gives its own.
Counterexample: the words ["banana", "apple", "cherry", "date"] in a Python set. Five runs of the same program gave five orders, such as ['cherry', 'date', 'banana', 'apple'] and ['apple', 'date', 'cherry', 'banana'], because Python gives strings a different hash in each run.
Build the output from the input order, or from a structure that keeps order.
A word count uses a plain object: counts[word] = (counts[word] || 0) + 1. An object has keys that you did not put there.
Counterexample: words = ["constructor", "apple", "__proto__"]. After the loop, counts["constructor"] is the text "function Object() { [native code] }1", not 1, because every object inherits a constructor. The word __proto__ is lost: writing to that key tries to change the object's prototype, so Object.keys(counts) lists only constructor and apple.
Object keys are also turned into text. So o[1] and o["1"] are one key, and every object used as a key becomes the text "[object Object]". After o[{a: 1}] = "x", a lookup with any other object, such as o[{b: 2}], finds "x".
Use a Map, which keeps 1 and "1" apart and compares objects by identity, or Object.create(null) for an object with no inherited keys.
Each language at a glance#
I ran every row of this table on one machine, with Python 3.9, Java 23, clang with libc++ for C++, and Node 22.
| Python | Java | C++ | JavaScript | |
|---|---|---|---|---|
| A pair as a key | a tuple | a record, or a long that packs both | unordered_map has no hash for a pair: use map, a packed 64-bit number or your own hash |
a string with a separator |
| A list or array as a key | TypeError |
accepted, compared by contents, and lost if it changes | unordered_map has no hash for a vector: use map, or convert |
accepted, compared by identity |
| Your own class as a key | defining __eq__ alone makes it unhashable, a TypeError: add __hash__, or use a frozen dataclass |
override equals and hashCode together, or use a record |
unordered_map needs a hash and == for it |
Map compares by identity, and a plain object turns it into "[object Object]" |
| NaN as a key | two separate NaN values are two keys | one key | unordered_map: two keys, and count(NAN) is 0. map: undefined, because NaN breaks the order |
one key |
| 0.0 and -0.0 | one key | two keys | one key | one key |
| Order of a table | a dict keeps insertion order (guaranteed since 3.7), a set does not | HashMap unspecified, LinkedHashMap insertion, TreeMap sorted |
unordered_map unspecified, map sorted |
Map and Set keep insertion order; a plain object lists keys such as "2" and "10" first, in number order |
A few more facts from the same run. In Python, 1, 1.0 and True are one key. In Java, Integer 1, Long 1 and Double 1.0 are three keys. In C++, a map holding NaN, NaN and 1.0 ended with one entry: the order that map relies on breaks.
The contract behind every key#
Java states the rule that every language needs. If two keys are equal, their hash codes must be equal. Two keys that are not equal may share a hash code: that is a collision, and it is allowed.
Break the first half and the table breaks. A class that overrides equals and forgets hashCode keeps the default hash, which differs for each object. A lookup with a separate, equal object then goes to another bucket, and in my run it returned null. A Java record, or a frozen dataclass in Python, writes both methods for you.
A table's order is not part of any contract. Java 8 changed how HashMap stores its entries, and programs that printed a HashMap saw their output change. The C++ standard leaves the order of an unordered_map open, so another compiler or library can print another order. Only the ordered structures in the table above promise an order.
Collisions and hash flooding#
A hash collision is two different keys with the same hash. It never changes the answer, because the table compares the keys. It only makes the bucket longer. Hash flooding is the case where an attacker, or bad luck, puts many keys in one bucket, so that each operation compares with them all.
Here is what I measured on one laptop. The times will differ on yours, but doubling the keys made the slow cases about four times slower.
| Language | Test | Result |
|---|---|---|
| Python | 20,000 ints that are multiples of 2^61 - 1, which all have hash 0 | about 2 seconds, against about half a millisecond for 20,000 consecutive ints |
| Java | 65,536 strings with the same hashCode, built from Aa and BB |
about 20 to 40 milliseconds, against about 5 for ordinary strings |
| Java | 40,000 keys of a class with a constant hashCode and no compareTo |
about 3 seconds |
| Java | the same keys, with compareTo |
about 5 to 20 milliseconds |
| C++ | 40,000 ints that are multiples of the bucket count | about 1 second, against half a millisecond |
What each language does about it:
- Python gives strings and bytes a random hash in each process, by default since Python 3.3. Integers hash to themselves, modulo 2^61 - 1, so an attacker can choose integers that collide.
- Java, since Java 8, turns a bucket into a balanced tree once it holds more than 8 entries and the table has at least 64 buckets. The tree compares keys with
compareTowhen the key class has one, andStringdoes, so the strings above stayed fast. A key with a constant hash and no order still slows down. - C++
unordered_maphas no defence. The integer hash is the number itself in the library I tested. Contest programmers use a custom hash with a random seed, or a sortedmap. - JavaScript: Node's V8 seeds its string hash at start. Its flags list
--hash-seed=0, where 0 means random, and--rehash-snapshot, which re-seeds the strings built into the startup snapshot. I did not measure flooding in JavaScript.
Why servers care: a web server puts the fields of every request in a hash table. In 2011 a public talk showed the attack on several popular platforms. One request, with many field names chosen to collide, kept a server's processor busy for a long time. Random string hashes and tree buckets are the fixes that followed.
The realistic interview takeaway is small. Say that a hash map is fast on average, if the hash spreads the keys and an attacker does not choose them.
Say that the worst case is one bucket, O(n) for each operation. If the keys come from users, name a defence: a randomised hash, or an ordered map with O(log n). Do not build the defence unless you are asked.
When the pattern does not apply#
Your team lead asks for the first request after 09:00, or for the largest page number below 50. A hash table finds an equal key, and it has no order. Neither question is about an equal key.
For ordered questions you need a sorted structure: a sorted list with binary search, std::map with lower_bound, or Java's TreeMap with ceilingKey. JavaScript has no built-in sorted map.
Product variations#
Your team lead brings four product changes. Each one asks what the key is.
A game wants the number of different cells a player visited. The pair (row, column) is the key, as in the robot example. When the grid has a known width, row * width + column is one number that holds both parts. It is a good key as long as the column is less than the width.
The report must list each category once, in the order in which it first appears. Keep a list of the categories next to the set, and add a category to the list when it is new to the set. A Python dict, a JavaScript Map and a Java LinkedHashMap do this for you, and a HashMap or unordered_map does not.
A report groups orders by their price, such as 19.99. Do not use the price as a key. Convert it to whole cents, 1999, and use that, or use a canonical text. Round, do not cut.
Cutting 0.29 * 100 to a whole number gives 28 in Python, Java, C++ and JavaScript, and rounding it gives 29.
An interviewer asks: what if someone sends keys that all collide? A good answer names the cost, which is O(n) for each operation. It names one defence: a random seed in Python or C++, a tree bucket in Java, or an ordered map for keys that are not trusted. It does not claim that a hash map is always O(1).
Why this matters in real systems#
6. Say: lock it in#
Explain it back#
Explain it back: write the idea in your own words and get feedback.
In two or three sentences, explain to a teammate what a hash table key must do. Then give two ways in which a key can break a table, and say how you avoid each. The AI tutor checks your answer against the invariant and the key points of this lesson.
Here is how you could explain it in an interview, now that you have built it.
A table finds an entry by the hash of its key, and then compares keys. So the key must be equal exactly when the items are the same, and it must not change while it is stored.
For several fields I keep them apart, with a tuple or a packed number, never glued text. For a list or a set I store a frozen copy.
I never use a floating-point number as a key, and I never take an order from a table. A map is fast on average, and I say so.
The 60-second interview answer#
A hash table hashes the key to find a bucket, and then compares keys in it. So I design the key first. It must be equal for items that are the same, different for items that are not, and fixed for as long as it is stored.
For two fields, I use a tuple in Python and a record or a packed long in Java. In C++ I use a packed 64-bit number, and in JavaScript a string with a separator. I never write the numbers one after the other.
For a list or a set, I store a frozen copy. For numbers, I use whole numbers or a canonical text, not a float.
A table has no order, so I build output from the input order. On average a lookup is O(1). A hostile input can put many keys in one bucket, so for untrusted keys I use a random hash or an ordered map.
Checkpoint#
Checkpoint · Keys
Q1/6 A cache key is made by writing the category and the page number one after the other. Which two requests get the same key?
Answer & explanation
Answer: C
Both (1, 23) and (12, 3) read 123 when the numbers are written one after the other. The pairs (1, 2) and (2, 1) read 12 and 21, and (5, 5) and (55, 5) read 55 and 555.
Q2/6 Why must a key not change while it is stored in a hash table?
Answer & explanation
Answer: B
The table chooses a bucket from the hash of the key when the entry is stored. If the key changes, its hash changes, and the lookup looks in a different bucket. ```quiz %% title: Checkpoint · Languages
Q3/6 In Java, a class overrides equals but not hashCode. You put one object in a HashMap and look it up with a separate, equal object. What does the lookup usually return?
Answer & explanation
Answer: B
The map first uses the hash code to choose a bucket. Two equal objects with different hash codes go to different buckets, so the lookup does not reach the stored entry.
Q4/6 In Java, you put a list in a HashMap as a key, and then add one element to that list. What do containsKey(list) and size() give?
Answer & explanation
Answer: C
The entry stays in the table, so the size is still 1. It sits in the bucket of the old hash, and containsKey looks in the bucket of the new hash, so it returns false.
Q5/6 Why does unordered_map<pair<int, int>, int> not compile in C++?
Answer & explanation
Answer: C
unordered_map needs a hash for its key, and std::hash has no version for a pair. You can write one, pack the two numbers into one 64-bit number, or use map, which needs only an order.
Q6/6 In JavaScript, you run o[1] = "a" and then o["1"] = "b" on a plain object o. How many keys does Object.keys(o) list?
Answer & explanation
Answer: B
Object keys are turned into text, so the number 1 and the text "1" are the same key. A Map keeps them apart, and would hold 2 entries.
Checkpoint · Numbers, order and collisions
Q1/4 Which key is the safest for prices such as 19.99?
Answer & explanation
Answer: C
A whole number is exact. A floating-point number rounds, so 0.1 + 0.2 is 0.30000000000000004 and does not equal 0.3 in Python, Java, C++ or JavaScript.
Q2/4 A Java HashMap of Double keys gets the key NaN twice. How many entries does it hold, and how does Python compare?
Answer & explanation
Answer: B
Java's Double.equals treats NaN as equal to itself. In Python, NaN is not equal to NaN, and a dict only finds a NaN that is the very same object.
Q3/4 Which table keeps the order in which the keys were added?
Answer & explanation
Answer: C
A Map in JavaScript, a dict in Python and a LinkedHashMap in Java keep insertion order. A HashMap, an unordered_map and a set do not give an order you can rely on.
Q4/4 What does hash flooding do to a hash table?
Answer & explanation
Answer: B
Equal hashes never change which key matches, because the table compares the keys. They only make the bucket long. In the lesson, 20,000 Python ints with hash 0 took about 2 seconds, and the answer was still right.
Ten questions on this lesson. Pass with 80% or more to be sure the idea has landed before the next lesson. The checkpoint of this stretch, with its two mixed problems, comes after the next lesson.
Practice ladder#
| Step | Problem | Product line | Level | What it practises |
|---|---|---|---|---|
| 1 | Why the key list changed order | Platform | Easy | Output order that comes from the input, not from a table |
| 2 | Mutable keys in a cache | Search | Medium | A frozen copy of a changing set as the key |
| 3 | Decimal ids that read the same | Ads | Medium | A canonical text in place of a floating-point key |
Review cards#
Review cards from this lesson.
Six cards from this lesson join your spaced-review deck. The first one comes back tomorrow.