Where it runs
1. The problem
The built-in Map and Set from the lessons on collections find the value for a key in about one step, however many keys they hold. This lesson shows how they do it. How does a structure go straight to the right place without checking every entry?
They use a hash function. It is a small rule that turns any key into a number, and the number points at a slot. Once the number is computed, there is nothing to search: you go straight to that slot.
2. In plain words
Take the key "dog" and a table with 3 slots, numbered 0, 1 and 2. A fixed rule turns "dog" into a slot number. This lesson's rule gives 2 (the next section shows the arithmetic). So "dog" is stored in slot 2.
Later you look for "dog". You run the same rule on the same key and get 2 again. You go straight to slot 2, and the key is there. Slots 0 and 1 are never checked. The rule is all it takes: a key goes in, a slot number comes out, and the same key always leads to the same slot.
3. The idea
A hash function is a rule that takes a key and returns a number. We want a rule that is cheap to compute and always gives the same number for the same key.
A simple rule for text: add up the character codes of all the letters. A character code is the number a computer uses for a letter: "a" is 97, "b" is 98, and so on. The word "cat" becomes 99 + 97 + 116 = 312. That sum is the "raw" hash, not yet a slot number.
The sum can be large, but a table has a limited number of slots. Say there are numBuckets of them, numbered 0 up to numBuckets - 1. To turn the big sum into a valid slot number, take the remainder after dividing the sum by numBuckets. The remainder is written with the sign %, and the operation is called modulo. For example, 312 % 3 is 0, because 312 divides by 3 with no remainder. The remainder is always between 0 and numBuckets - 1, exactly the range of slot numbers. So bucketIndex = sum % numBuckets always points at a real slot.
A slot in a hash table is called a bucket. Here is how "cat", "dog" and "bird" land in a table of 3 buckets:
Now a lookup. To find "dog", run the rule again: 100 + 111 + 103 = 314, and 314 % 3 = 2. Go straight to bucket 2 and skip buckets 0 and 1. That is why a hash structure answers in about one step.
Look at bucket 0: it holds two keys. "cat" gave the sum 312, and "bird" gave 98 + 105 + 114 + 100 = 417. Both sums divide by 3 with no remainder, so both keys landed in bucket 0. Two different keys in one bucket are called a collision. It is not a bug. When there are more keys than buckets, collisions cannot be avoided. In this lesson we find one key and stop there. What to do with a crowded bucket is the next lesson.
4. What it costs
The hash function walks over the key's letters once. For a short key that is practically O(1). Picking the bucket is one modulo, also O(1). So finding the bucket for a key takes constant time, however many keys the table already holds. Checking every entry would cost O(n).
Memory: O(numBuckets) for the empty table and O(n) for the n stored keys. distribute walks over the keys once, but each key costs its own letter walk, and the table starts with numBuckets empty lists. So its time is O(numBuckets + the total length of all keys), which is O(numBuckets + n) when the keys are short.
One honest note: "about one step" holds only if the keys spread evenly over the buckets. If a bad hash puts every key into one bucket, a lookup turns back into checking entries one by one. How to spread keys evenly and how to handle a crowded bucket come in the next lessons.
6. Where this shows up
Sharding (splitting data into parts kept on different servers) does the same thing. A cache or a database is split into N parts. To decide which part holds a key, the system hashes the key and takes the remainder after dividing by N. That is exactly bucketIndex. So the same key always lands in the same part, and a read finds what was written. Kafka partitions and spreading load over servers use the same idea with a stronger hash function. Consistent hashing in distributed caches works differently: it assigns keys to parts so that adding a server moves only a few keys. Every Map, Set, Python dictionary and hash index in a database starts the same way: a key becomes a number, and the number becomes a slot.
On LeetCode
Problems where you turn each item into a key and drop it into a bucket, so items with the same key meet, such as anagram groups, pairs by remainder, or a hash set you build yourself.
Sorting a word's letters gives every anagram the same key, just as "ab" and "ba" landed in one bucket.
Bucket each song by its length % 60 and count pairs between bucket r and bucket 60 minus r.
Build the table yourself and pick each key's bucket with key % numBuckets, as bucketIndex does.
Your task (Tier 1)
Write two functions: bucketIndex(key, numBuckets) and distribute(keys, numBuckets).
bucketIndex turns a text key into a bucket number. distribute uses it to spread a list of keys over the buckets.
bucketIndex(key, numBuckets):keyis text,numBucketsis a positive whole number. Returns the bucket number for the key, always from0up tonumBuckets - 1.distribute(keys, numBuckets):keysis a list of text values. Returns a list ofnumBucketslists, with each key placed in its bucket.
Steps:
- For
bucketIndex: add up the character code of every letter inkey. Divide that sum bynumBucketsand return the remainder (the modulo). Equal keys give equal sums, so they always land in the same bucket. - For
distribute: makenumBucketsempty lists. For each key, find its bucket withbucketIndex, then add the key to that list. Keep the input order inside each bucket. Return the list of buckets.
Done when all tests pass:
bucketIndex:
("cat", 3)->0("dog", 3)->2("anything", 1)->0(one bucket, everything lands in0)("", 5)->0(an empty key sums to0)("ab", 4)->3and("ba", 4)->3(same letters, same bucket)
distribute:
(["cat","dog","bird"], 3)->[["cat","bird"], [], ["dog"]](["ab","ba"], 4)->[[], [], [], ["ab","ba"]](a collision shares a bucket)(["a","b","c"], 1)->[["a","b","c"]]([], 3)->[[], [], []](empty list, must not crash)
Practice
bucketIndex / distribute
export function bucketIndex(key, numBuckets) {
// Your code here. The task is described in the box above the editor.
}
export function distribute(keys, numBuckets) {
// Your code here. The task is described in the box above the editor.
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.