Hashing
Quick reference
| Insert / lookup / delete (average case) | O(1) |
| Insert / lookup / delete (worst case) | O(n) |
Recall from Arrays & Strings Fundamentals that array indexing is O(1) because the address is computed directly from the index — base + index × size, pure arithmetic, no searching. Hashing extends that same trick to keys that aren't already small, tidy integers. A hash function takes any key — a word, a tuple, a whole object — and squashes it down to a number, which is then used as a plain array index. Look up "apple" in a hash table and, under the hood, "apple" gets converted to a number, and that number tells you exactly which slot in a backing array to check — no scanning required.
Picture a library that shelves books by a formula computed straight from the title, instead of alphabetically. Given any title, you compute the formula and walk directly to the shelf — no browsing required. That's the whole idea: trade some memory (the backing array has to have room for the formula's possible outputs) for near-instant lookup.
Structures
structure HashMap:
buckets // a plain array (Arrays & Strings Fundamentals) — one slot per possible hash value
size // how many key/value pairs are currently stored
function hash(key):
return someFormula(key) % buckets.length // squashes any key down to a valid array indexcollisions — when two keys land in the same bucket
// two different keys can hash to the same bucket index — a collision.
// one common fix: chaining — each bucket holds a small list instead of one slot
function insert(map, key, value):
bucketIndex = hash(key)
if map.buckets[bucketIndex] is empty:
map.buckets[bucketIndex] = new list
map.buckets[bucketIndex].add((key, value)) // append to the chain, don't overwrite itfrequency count — hash map
function countFrequencies(items):
counts = new HashMap
for item in items:
counts[item] = counts.get(item, default=0) + 1
return countsmembership check — hash set
function hasDuplicate(items):
seen = new HashSet
for item in items:
if item in seen: // O(1) average — a hashed lookup, not a scan
return true
seen.add(item)
return falseThe "average" qualifier matters here more than almost anywhere else — recall the average-vs-worst-case distinction from Big-O Notation. A hash table's speed depends on the hash function spreading keys out well; when that assumption holds (the normal case), lookups are effectively instant.
| Operation | Time | Space | Why |
|---|---|---|---|
| Insert / lookup / delete (average case) | O(1) | O(1) per operation (O(n) total for n entries) | A good hash function spreads keys evenly, so each bucket holds close to zero or one entries — checking a bucket is essentially constant work. |
| Insert / lookup / delete (worst case) | O(n) | O(1) per operation | If every key collides into the same bucket (a poor hash function, or adversarial input crafted to collide), that bucket's chain grows to length n and searching it is a full scan — rare in practice, but real. |
Using a mutable value as a key
A key's hash is computed from its contents at insert time. If the key is a mutable object and its contents change afterward, its hash would be different if recomputed — but the table doesn't recompute it, so the entry is now sitting in the wrong bucket for what the key currently looks like, and future lookups for it silently fail. Keys should be values that don't change once stored.
Assuming iteration order matches insertion order
Some languages' hash map implementations happen to preserve insertion order (or expose a variant that does); others make no such guarantee and can return entries in an order that looks arbitrary. Code that depends on order without checking the specific language's guarantee works by accident in one language and breaks in another.
Reaching for hashing when order actually matters
Hashing gives fast "is this here / what's paired with this," not order — a hash set or map doesn't keep keys sorted, and iterating one doesn't produce anything meaningful about relative order. Problems that need "the smallest," "in sorted order," or "the next largest" need a different tool even if fast lookup is also part of the problem.
Collisions silently degrading performance
Code that assumes every hash map operation is O(1) without exception can be quietly O(n) per operation on data that collides heavily — an attacker who knows your hash function can sometimes construct exactly such input on purpose. "Average case O(1)" is a property of typical data, not a guarantee for all data.
Sign in to mark problems done — progress syncs across devices.