Hash Table
What you'll build
A HashTable class with set, get, delete, and keys methods, using a simple hash function and separate chaining for collisions.
Goals
- Implement a hash function mapping string keys to bucket indices
- Handle collisions with separate chaining (arrays per bucket)
- Provide get/set/delete/keys operations
- Understand why hash tables give O(1) average lookup
Prerequisites
- Objects and property access
- Arrays and array methods
- String methods (charCodeAt)
Steps
- 1
Design the bucket array
A hash table is an array of buckets. Each bucket is an array of [key, value] pairs. Pick a fixed capacity (e.g. 53) and initialize all buckets as empty arrays.
Codeclass HashTable { constructor(capacity = 53) { this.capacity = capacity; this.buckets = Array.from({ length: capacity }, () => []); } }Expected result
A HashTable with 53 empty buckets.
- 2
Write the hash function
Implement a hash function that converts a string key to a bucket index. A common approach: sum char codes, multiply by a prime, then mod by capacity.
Code_hash(key) { const PRIME = 31; let total = 0; for (let i = 0; i < Math.min(key.length, 100); i++) { total = (total * PRIME + key.charCodeAt(i)) % this.capacity; } return total; }Expected result
_hash('name') returns a number in [0, capacity).
Hint
Using a prime multiplier spreads keys out, reducing collisions.
- 3
Implement set with collision handling
To set a key, hash it to find the bucket, then check if the key already exists in that bucket. If so, update the value; otherwise push a new [key, value] pair.
Hint
Walk the bucket array and compare the first element of each pair to the key.
- 4
Implement get and delete
get hashes the key, walks the bucket, and returns the matching value (or undefined). delete finds and removes the matching pair. Both rely on the same bucket-walk logic.
Hint
Use array.findIndex on the bucket, comparing pair[0] to the key.
- 5
Test with collisions
Insert several key/value pairs, retrieve them, delete one, and confirm the rest are intact. Verify that keys hashing to the same bucket still work (collision handling).
Codeconst ht = new HashTable(); ht.set('name', 'Alice'); ht.set('age', 30); ht.set('city', 'Beijing'); console.log(ht.get('name')); // Alice console.log(ht.get('age')); // 30 ht.delete('age'); console.log(ht.get('age')); // undefinedExpected result
get returns Alice, 30, then undefined after delete.
Try it yourself
class HashTable {
constructor(capacity = 53) { /* TODO */ }
_hash(key) { /* TODO */ }
set(key, value) { /* TODO */ }
get(key) { /* TODO */ }
delete(key) { /* TODO */ }
}class HashTable {
constructor(c = 53) { this.capacity = c; this.buckets = Array.from({length:c}, () => []); }
_hash(k) { let t = 0; for (let i = 0; i < Math.min(k.length,100); i++) t = (t*31 + k.charCodeAt(i)) % this.capacity; return t; }
set(k, v) { const i = this._hash(k); const b = this.buckets[i]; const ex = b.find(p => p[0] === k); if (ex) ex[1] = v; else b.push([k, v]); }
get(k) { const b = this.buckets[this._hash(k)]; const p = b.find(x => x[0] === k); return p ? p[1] : undefined; }
delete(k) { const b = this.buckets[this._hash(k)]; const i = b.findIndex(p => p[0] === k); if (i !== -1) b.splice(i, 1); }
}What you learned
You built the data structure that powers JavaScript objects and Map — and saw how a hash function plus collision handling gives near O(1) lookups.
Related Resources
Related Lessons
Related Glossary
- Hash Table
Key-value store with O(1) average lookup.
Related Glossary
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
- Hash Table
Key-value store with O(1) average lookup.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.