Where it runs
1. The problem
In step 14 a hash function (a rule that turns a key into a number) picked a bucket (a numbered slot) for each key. A lookup stopped walking the whole list and looked into one bucket. But two different keys can get the same bucket number. That is a collision. If a bucket holds only one value, the second key writes over the first one, and data is lost.
You need a bucket that holds more than one key while lookups stay fast. This step builds it.
2. In plain words
Take two keys from the tests, "a" and "i", and a table of 8 buckets. The hash of "a" is 1, and the hash of "i" is 1 too. Both keys belong in bucket 1.
So bucket 1 keeps a short list instead of one value. The list holds ["a", 1] and then ["i", 2], each key stored next to its value. To read "i", you go to bucket 1 and walk its list: ["a", 1] has the wrong key, ["i", 2] has the right one, the answer is 2. That took two checks. The other 7 buckets were never looked at. Sharing a bucket is fine as long as no bucket gets crowded.
3. The idea
A bucket is the slot of the table a key lands in. When two keys land in the same bucket, that is a collision. Separate chaining solves it this way: each bucket holds a small list of entries instead of one value. That list is called the chain.
Each entry in a chain is a pair of a key and its value: [key, value]. You must keep both. One bucket can hold several different keys, and the only way to tell them apart is the key stored next to each value.
Every operation starts with the same two moves. First hash the key and pick the bucket. Then walk that bucket's short chain and compare each stored key with the one you want.
set(key, value): walk the chain. If an entry already has this key, replace its value. If no entry matches, add a new[key, value]pair.get(key)andhas(key): walk the chain and return the value you found (or yes and no forhas). If the chain ends with no match, the key is not there.delete(key): walk the chain and remove only the pair whose key matches.
The hash is the same as in step 14: add up the character codes of the key and take the remainder after dividing by the number of buckets. Our table always has 8 buckets. It cannot grow yet.
Trace it step by step. set("a", 1): the code of "a" is 97, and 97 % 8 = 1, so bucket 1. The chain is empty, so add ["a", 1]. set("i", 2): the code of "i" is 105, and 105 % 8 = 1, bucket 1 again. That is a collision. The chain holds only ["a", 1], whose key does not match, so add ["i", 2]. Now get("a"): bucket 1, the first pair ["a", 1] matches, return 1. get("i"): bucket 1, the pair ["a", 1] does not match, the next one ["i", 2] does, return 2. Both keys sit in one bucket, and both come back right.
4. What it costs
Time is O(1) on average. If the hash spreads keys evenly, every chain stays short, with a couple of entries. A hash plus a short walk take about constant time, however many keys the table holds.
The worst case is O(n). If every key lands in one bucket, one chain holds all n entries. A lookup walks the whole chain, and that is a full linear pass again. A good hash and a table that is not overfull keep you far from this case.
Memory is O(n): one [key, value] pair per key, plus the 8 bucket lists. That is the price of O(1) access on average.
6. Where this shows up
Real hash tables inside programming languages are built this way. Java's HashMap uses separate chaining. When a chain gets too long, Java turns it into a balanced tree (a structure where a search takes O(log n)). Session stores link a login token to a user this way. Symbol tables in compilers, routing tables (which code answers which address) and in-memory caches all run on the same scheme of buckets and chains. Once you have written such a table yourself, map.get(key) is no mystery: it is a hash and a short walk along a chain.
On LeetCode
Interview problems that ask you to build a hash map or hash set yourself, and the follow-up question of what happens when two keys collide.
Each bucket holds a chain of [key, value] pairs, and put, get and remove walk it like set, get and delete here.
The same chains with keys only, since a set stores no values.
Solve it with your own chained table in place of Map, storing each number with its index.
Your task (Tier 1)
Build the four methods of the HashMap class: set, get, has and delete. The constructor (8 buckets), the _hash helper and the size getter are already written for you.
Two keys can hash to the same bucket (a collision). Chaining handles it: each bucket is a list of [key, value] pairs. Every method hashes the key, takes that bucket and goes through its short list.
- Effect:
setanddeletechange what the map holds. - Return:
getgives a value or nothing;hasgivestrue/false;deletegivestrue/false.
Steps:
set(key, value): find the bucket with_hash(key). Go through its pairs. If a pair has this key, change its value and stop (the size stays the same). If none matches, add[key, value]to the bucket and add 1 to the size.get(key): go through the key's bucket. Return the value of the matching pair, or nothing (undefined) if none matches.has(key): go through the key's bucket. Returntrueif the key is there, otherwisefalse.delete(key): go through the key's bucket. If a pair has the key, remove that one pair, take 1 off the size and returntrue. If not, returnfalse.
Done when all tests pass:
set("a",1),set("b",2), thenget("a")->1,get("b")->2,size->2set("a",99)on top of"a"->get("a")->99,sizestays2(an overwrite adds no pair)set("a",1),set("i",2)share a bucket, yetget("a")->1andget("i")->2(a collision, both kept)- after
delete("a"):has("a")->false,get("i")still2; a seconddelete("a")->false - empty map:
get("anything")->undefined,has("anything")->false,delete("anything")->false,size->0
Practice
HashMap with separate chaining
export class HashMap {
constructor() {
this.numBuckets = 8;
this.buckets = Array.from({ length: this.numBuckets }, () => []);
this._size = 0;
}
_hash(key) {
let sum = 0;
for (let i = 0; i < key.length; i++) sum += key.charCodeAt(i);
return sum % this.numBuckets;
}
set(key, value) {
// Your code here. The task is described in the box above the editor.
}
get(key) {
// Your code here. The task is described in the box above the editor.
}
has(key) {
// Your code here. The task is described in the box above the editor.
}
delete(key) {
// Your code here. The task is described in the box above the editor.
}
get size() {
return this._size;
}
}
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.