Hash Tables

What is it?

Searching an array for a value means checking items one at a time until you find it — slow once there's a lot of data. A hash table solves this by converting a key (like a name or an id) into a number using a hash function, and using that number to jump directly to where the value is stored. In JavaScript, plain objects and the Map class are both backed by this idea.

Explain like I'm 10

A hash table is like a coat check at a theater. Instead of searching through every coat to find yours, you're handed a numbered ticket (the hash), and the attendant goes directly to that numbered spot to retrieve your coat.

Examples

Using an object (or Map) as a hash table

const ages = {};

ages["amara"] = 28;
ages["diego"] = 34;

console.log(ages["amara"]); // 28 — near-instant lookup, not a search

const map = new Map();
map.set("amara", 28);
console.log(map.get("amara")); // 28

How it works

A hash function takes a key and converts it into a number (a "hash") that maps to a specific storage slot. Looking up a key just means: hash the key, jump to that slot, and read the value — no scanning required. When two different keys happen to hash to the same slot (a "collision"), the table has strategies (like storing a small list at that slot) to handle it correctly.

key "amara"
       ↓ hash function
    number: 42
       ↓
   slot 42 → 28

Why does it exist?

Hash tables give near-instant lookups, insertions, and deletions on average — O(1) — which makes them essential for counting frequencies, caching results, deduplicating data, and implementing sets and dictionaries efficiently.

When to use it

Reach for a hash table (object or Map) whenever you need to look something up by a key quickly — counting occurrences, checking for duplicates, caching results, or building a dictionary of any kind.

When not to use it

If order matters and you need to process items in a specific sequence, a hash table doesn't guarantee position the way an array does. And for a small, fixed handful of values, just checking each one directly can beat setting up a hash table at all.

Common mistakes

• Assuming object/array key order is always guaranteed in every situation — it mostly is in modern JavaScript for string keys, but it's a detail worth knowing rather than relying on blindly.

• Using an object when a Map would be safer, e.g. when keys aren't simple strings or when key order and size (.size) matter.

• Forgetting that average-case O(1) lookup can degrade if many keys collide (a rare but real edge case).

Practice exercises

1. Easy:

   Use an object to count how many times each word appears in a sentence.

2. Medium:

   Write a function that returns true if an array contains any duplicate values, using a hash table for O(n) performance.

3. Hard:

   Solve the 'two sum' problem (find two numbers in an array that add up to a target) in O(n) time using a hash table.

Interview questions

What is a hash function?

A function that converts a key into a number used to determine where its value is stored, ideally spreading keys evenly across storage slots.

What is the average time complexity of a hash table lookup?

O(1) on average, since the hash function typically jumps directly to the right slot.

What is a hash collision, and how is it handled?

A collision happens when two different keys hash to the same slot. It's commonly handled by storing multiple entries at that slot (e.g. in a small list) and checking each one.

What three properties should a good hash function have?

It should be deterministic (the same key always produces the same hash), fast to compute (so it doesn't erase the O(1) benefit), and spread keys uniformly across the available slots to minimize collisions and keep chains/probe sequences short.

What is the load factor of a hash table, and why does it matter?

The ratio of stored entries to the number of slots (n / capacity). As load factor rises, more keys compete for the same slots, so collisions become more likely and chains (or probe sequences) get longer — pushing lookup/insert time away from O(1) and toward O(n) in the worst case. Implementations resize once load factor crosses a threshold to keep it bounded.

Why is resizing a hash table (rehashing) an O(n) operation, and why doesn't that ruin the 'O(1) average' claim for insertion?

Resizing allocates a larger backing array and reinserts every existing entry, since each entry's slot depends on hash(key) % capacity — a different capacity means a different slot for almost every key. This is O(n), but resizes happen exponentially less often as the table grows (typically when doubling capacity), so — exactly like a dynamic array — the cost amortizes to O(1) per insertion on average across a sequence of operations.

What is separate chaining, and what does it cost in the worst case if every key hashes to the same slot?

Each slot holds a small secondary structure (commonly a linked list, sometimes a balanced tree) of all entries that hashed there; looking up a key means hashing to find the slot, then scanning that slot's structure for a match. If every key collided into one slot, that structure would hold all n entries, degrading lookup to O(n) — the same as a linear scan.

What is open addressing, and how does linear probing resolve a collision under it?

Unlike chaining, open addressing stores every entry directly in the backing array itself with no secondary structure. On a collision, linear probing just checks the next slot ((hash + 1) % capacity), then the next, and so on, until an empty slot is found — insertion and lookup both follow the same probe sequence.

What is primary clustering in linear probing, and why does it make things worse as load factor rises?

Once several keys collide near each other, linear probing places them in one unbroken run of occupied slots. Any new key that hashes anywhere into that run has to probe through the whole cluster to find a free slot, and every insertion into the cluster makes it longer — so clusters tend to grow and merge, degrading average probe length well before load factor gets close to 1.

How does quadratic probing try to reduce clustering compared to linear probing, and what's the tradeoff?

Instead of checking the next slot, it checks slots at increasing squared offsets (hash+1², hash+4, hash+9...), scattering probes further from the original slot so keys colliding at the same start point don't pile into one contiguous run. The tradeoff is secondary clustering: keys that hash to the exact same original slot still follow the identical probe sequence as each other.

How does double hashing address both primary and secondary clustering?

It computes the probe step size from a second hash function of the key, so keys that collide at the same slot from the first hash almost always take different step sizes and follow different probe sequences — unlike linear probing (same fixed step for everyone) or quadratic probing (same fixed offsets for everyone colliding at that slot).

Why can't you just delete an entry from an open-addressing hash table by clearing its slot to empty?

Probing relies on scanning a contiguous (or formulaic) sequence of occupied slots until it hits an empty one to know a key isn't present. If a slot in the middle of a probe sequence is cleared to empty after deletion, a later lookup for a different key that probed past that slot will stop early there and incorrectly conclude the key isn't present, even though it's stored further along.

How do open-addressing hash tables actually support deletion, given the problem with clearing a slot outright?

They mark the deleted slot with a special 'tombstone' marker instead of empty. Lookups treat a tombstone as 'occupied, keep probing past it,' while insertions treat it as available to reuse — preserving correct probing for existing keys while still letting the slot be reclaimed.

Why does average-case hash table lookup stay close to O(1) even though the worst case is O(n)?

With a good hash function and a load factor kept below some bound (via resizing), the expected number of entries sharing any slot stays close to a small constant, independent of n — the O(n) worst case only shows up in the pathological scenario where most or all keys collide into the same slot.

What is a 'hash flooding' attack, and how do some languages defend against it?

An attacker who knows (or can guess) a hash function crafts many keys that all collide into the same slot on purpose, driving that server's hash table operations toward O(n) each and causing a denial-of-service. Some languages/runtimes defend by seeding the hash function with a random value at process startup, so an attacker can't predict which keys will collide without knowing the runtime's secret seed.

What is the practical difference between using a plain JavaScript object and a `Map` as a hash table?

Map allows any value (including objects and functions) as a key with reference equality, reliably preserves insertion order, and reports its size directly via .size. A plain object effectively coerces non-symbol keys to strings, mixes in inherited properties from its prototype unless guarded against, and reorders integer-like keys numerically ahead of everything else.

Two different object instances with identical contents are used as keys in a JavaScript `Map` — are they treated as the same key?

No. Map key comparison for objects uses reference identity (are they literally the same object in memory), not structural/value equality — two distinct objects with identical properties are two distinct keys, even though both look like { a: 1 }.

Why is `NaN` a usable `Map` key, given that `NaN !== NaN` in JavaScript?

Map uses the SameValueZero algorithm for key comparison, not strict equality (===). SameValueZero treats NaN as equal to itself — the one case where it differs from === — so map.set(NaN, 1) followed by map.get(NaN) reliably returns 1.

What's the time complexity of checking whether an array contains any duplicate values, using a hash table versus not?

With a hash table (a Set), it's O(n) — one pass inserting each element and checking whether it's already present, each check O(1) average. Without one, comparing every pair is O(n²); sorting first and scanning for adjacent duplicates is O(n log n) — better than brute force but still worse than the hash-table approach.

How does the 'two sum' problem go from O(n²) to O(n) using a hash table?

Brute force checks every pair of numbers for one that sums to the target, O(n²). Instead, walk the array once, and for each number check whether target - number has already been seen (stored in a hash map from value to index); if so, the pair is found immediately. Since each lookup and insert is O(1) average, the whole pass is O(n).

Why can't you efficiently binary-search or iterate a hash table in sorted key order the way you can an array?

A hash table's slot for a key is determined by that key's hash value, not by any relationship to other keys' order — similar keys can land in completely unrelated slots. There's no ordering to exploit, so finding a range or the minimum/maximum key requires scanning every entry, O(n), regardless of the O(1) average lookup for a known key.

What is a hash set, and how does it relate to a hash table?

A hash set stores only keys (no associated values), using the same hashing and collision-handling machinery as a hash table, to answer 'have I seen this value before?' in O(1) average time — it's a hash table with the value slot dropped, used purely for membership testing and deduplication.

Why do a hash map and a doubly linked list, used together, give an LRU cache O(1) `get` and `put`?

The hash map gives O(1) average lookup from key to the linked-list node holding that entry. The doubly linked list keeps entries ordered by recency and, since each node knows both neighbors, supports O(1) removal from anywhere and O(1) re-insertion at the front — together letting a cache find a key instantly and reorder/evict without scanning.

What is consistent hashing, and what problem does it solve that a plain `hash(key) % N` scheme doesn't?

In a plain hash(key) % N scheme, adding or removing one server (changing N) reshuffles almost every key to a different server, invalidating nearly the whole distributed cache at once. Consistent hashing maps both keys and servers onto a shared ring of hash values, assigning each key to the next server clockwise from it — adding or removing a server then only reassigns the keys between it and its neighbor, not the whole keyspace.

What is a Bloom filter, and how is it different from a hash set?

A Bloom filter is a probabilistic structure that answers 'definitely not present' or 'possibly present' using a fixed-size bit array and several hash functions, trading a small false-positive rate for huge space savings since it never stores the keys themselves. A hash set stores real keys and gives an exact, never-wrong membership answer, at the cost of memory proportional to the number of keys.

Why might a hash table implementation upgrade a slot's collision list into a balanced tree once it grows past a certain size (as Java's `HashMap` does)?

A plain linked-list bucket degrades to O(n) lookup within that bucket if enough keys collide there (from a hash-flooding attack or bad luck). Converting a sufficiently long bucket into a balanced tree (like a red-black tree) bounds worst-case lookup within that bucket to O(log n) instead of O(n), trading a bit of extra bookkeeping for a much better worst case.

What is perfect hashing, and why does it only apply to a fixed, known set of keys?

It constructs a hash function (often a two-level scheme) guaranteed to have zero collisions for a specific, predetermined set of keys, giving true O(1) worst-case lookup — not just average case. It requires knowing the full key set in advance to build that collision-free function, so it doesn't work for a table that must accept arbitrary future insertions.

What is cuckoo hashing, and what's its worst-case lookup guarantee?

Each key has two candidate slots (via two hash functions, often across two tables), and a lookup checks at most those two fixed slots — giving O(1) worst-case lookup, unlike chaining's O(n) worst case. Insertion can be more expensive: if both of a new key's slots are taken, it evicts whichever occupant is there and re-inserts that key into its own alternate slot, potentially triggering a chain of evictions or, rarely, a full rehash if a cycle is detected.

What's the time complexity of iterating over every entry in a hash table, and does table capacity affect it?

O(n + capacity) in general — every stored entry must be visited (O(n)), plus every slot must at least be checked for occupancy (O(capacity)) in a simple array-of-buckets implementation. Since capacity is normally kept proportional to n via resizing at a bounded load factor, this is usually just described as O(n).

Why is using a mutable object as a dictionary key risky in languages where hashing is based on the object's *contents* (unlike JavaScript's `Map`, which hashes objects by reference)?

If the hash is computed from the object's current field values, mutating the object after insertion changes what its hash would now compute to, but the table doesn't know to move it. A later lookup with an object of the same, now-mutated contents hashes to a different slot than where the original entry actually lives, and the entry becomes silently unreachable.

Why does a hash table with a well-chosen hash function and controlled load factor still occasionally show a few lookups taking longer than others, even without an attack?

Even a well-distributed hash function will, by ordinary chance, sometimes place several keys in the same slot or nearby probe positions — the birthday-paradox effect means collisions among some pairs of keys are expected well before the table is anywhere near full, so a handful of lookups doing a few extra comparisons is normal, not a sign of a broken hash function.

How would you design a hash function for strings, at a high level, and why is a simple sum of character codes a poor choice?

A common, effective approach is a polynomial rolling hash — treat the string as digits of a number in some base p (s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1]), then reduce modulo the table size. Simply summing character codes is poor because it ignores order entirely — anagrams like 'listen' and 'silent' would hash identically, causing far more collisions than necessary among unrelated-looking keys that happen to share the same letters.

Scenario: you're building a cache that must evict the least-recently-used entry once it hits a size limit, and needs O(1) `get`/`put`. Why is a hash table alone not enough?

A hash table alone gives O(1) lookup by key, but has no built-in notion of access recency and no cheap way to find and evict 'the oldest-touched entry' without scanning every entry, O(n). It needs to be paired with an ordering structure (a doubly linked list) that a hash table doesn't provide on its own.

What is the practical difference between a hash table's worst-case and average-case complexity, and why do interview answers usually default to quoting the average case?

Worst case (O(n)) only shows up when collisions are unusually bad — a poor hash function, adversarial input, or extreme bad luck. With a well-distributed hash function and a bounded load factor, the expected behavior across normal inputs is O(1), which is what's actually observed in practice for essentially all real-world usage — so O(1) average is the practically meaningful number, while O(n) worst case is the theoretical floor to be aware of.

What's the difference between a hash table's `capacity` and its `size`, and why does an implementation usually keep capacity a prime number or a power of two?

size is the number of entries actually stored; capacity is the number of slots in the backing array. Using a prime number of slots (with modulo-based hashing) or a power of two (with bitmask-based hashing) tends to spread hash values across slots more evenly for common hash functions, reducing the chance that a poorly-mixed hash accidentally lands many keys in a small subset of slots.

Compare a hash table to a balanced binary search tree (like a red-black tree) as a dictionary implementation — what does each give up?

A hash table gives O(1) average lookup/insert/delete but O(n) worst case, no ordering, and no efficient range queries or min/max. A balanced BST gives a steady O(log n) worst case for all three operations, keeps keys in sorted order, and supports range queries and ordered traversal — at the cost of being slower on average than a well-behaved hash table for a plain 'get by exact key' lookup.

Why would `for...in` over a plain JavaScript object used as a hash table be riskier than iterating a `Map`'s entries?

for...in walks enumerable properties up the prototype chain, not just the object's own inserted keys — if the object's prototype (or a library) has added enumerable properties, they'll show up mixed in with the actual data unless guarded with hasOwnProperty (or Object.keys/entries used instead). Map's iteration only ever visits entries explicitly set on it, with no prototype-chain surprises.