Hash Tables, Sets, and Maps: Average O(1) Lookup
How hashing turns 'is this present' into an average-O(1) operation, what a collision is, and why worst-case behavior can still degrade to O(n).
What you'll learn
- Explain how a hash function turns a key into a bucket index
- Explain what a hash collision is and how chaining resolves it
- State honestly that hash table lookup is average-case O(1), not guaranteed O(1)
Prerequisites
Explanation
A hash table stores key-value pairs by feeding each key through a hash function that produces a number, which is then reduced (typically via modulo) to an index into a fixed-size backing array of buckets. hash("alice") -> 8492 -> 8492 % 16 -> bucket 12. Looking up "alice" recomputes the same hash, jumps directly to bucket 12, and checks what's there — no scanning of every entry required, which is the entire mechanism behind hash tables' headline O(1) average-case lookup, insertion, and deletion.
Two different keys can hash to the same bucket — a collision — which is a normal, expected occurrence, not a bug or a failure of the hash function. The standard resolution is chaining: each bucket holds a small list of every key-value pair that hashed there, and a lookup that lands in a bucket then does a short linear scan of that bucket's list to find the exact matching key. As long as the hash function distributes keys roughly evenly and the table resizes (like a dynamic array) to keep the average bucket short, that scan stays small — genuinely constant on average, hence "average-case O(1)."
This is precisely why the honest, complete statement is "average-case O(1)," not "O(1)" full stop: the worst case for a hash table is O(n) — if every key happened to hash to the same bucket (a pathological hash function, or, in adversarial contexts, deliberately crafted colliding input), every single lookup degrades to a full linear scan of one giant bucket. A well-designed hash function makes this vanishingly unlikely for typical, non-adversarial data, but it's a real possibility the "O(1)" shorthand glosses over — repeating "hash lookup is O(1)" without the "average case" qualifier is a genuinely common, genuinely incorrect claim worth avoiding precisely because it's so common. A Set is a hash table storing only keys (no associated value) — its entire purpose is the same average-O(1) "is this present" check; a Map is the general key-to-value version.
Example
A simplified hash table with explicit bucket chaining, showing collisions being handled correctly.
function simpleHash(key, bucketCount) {
let sum = 0;
for (const ch of String(key)) sum += ch.charCodeAt(0);
return sum % bucketCount;
}
function makeHashTable(bucketCount) {
return Array.from({ length: bucketCount }, () => []); // each bucket starts as an empty chain
}
function put(table, key, value) {
const bucket = table[simpleHash(key, table.length)];
const existing = bucket.find(pair => pair[0] === key);
if (existing) existing[1] = value;
else bucket.push([key, value]);
}
function get(table, key) {
const bucket = table[simpleHash(key, table.length)];
const found = bucket.find(pair => pair[0] === key);
return found ? found[1] : undefined;
}
const table = makeHashTable(4);
put(table, "alice", 30);
put(table, "bob", 25);
console.log(get(table, "alice")); // 30 -- direct bucket jump, then a short scan within itTry it yourself
Try put/get with a key that wasn't inserted, and confirm get returns undefined rather than throwing.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write hasDuplicates(items) using a Set to check (in one pass, average O(n) overall) whether items contains any duplicate value. Do NOT use nested loops or Array.prototype.includes inside a loop -- use the Set's average-O(1) membership check.
Checks: detects a duplicate correctly · correctly reports no duplicates · handles an empty array
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write groupAnagrams(words) that groups words which are anagrams of each other (same letters, any order) using a Map keyed by each word's SORTED letters. Return an array of groups (arrays), in the order each group was first encountered.
Checks: correctly groups multiple sets of anagrams · handles an empty input array · handles a single word with no anagram partners
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Saying 'hash table lookup is O(1)' without the 'average case' qualifier -- the honest, complete claim is average-case O(1); worst case is O(n) when many keys collide into the same bucket.
- Using an object with mutable keys, or a poorly-distributed custom hash function, that causes most entries to collide into a small number of buckets -- this silently degrades every operation toward the O(n) worst case.
- Reaching for a nested loop or repeated Array.includes() to check for duplicates/membership across a large array, when a Set gives the same answer in average O(n) total instead of O(n^2).
Knowledge check
Takeaway
A hash table's O(1) is an average-case claim, not a guarantee — it depends on a hash function that distributes keys well enough that no bucket's chain grows long; the honest worst case, when that assumption breaks, is O(n).
Summary
A hash function maps a key to a bucket index; collisions (different keys, same bucket) are resolved via chaining, a short list per bucket. Hash table/Set/Map operations are average-case O(1), worst-case O(n). Use a Set for membership checks and a Map for key-to-value lookup instead of scanning an array.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.