4.3 — Hashing

An array can find element 5 instantly because the index is the address. A hash table asks a harder question: can we get that same instant lookup when the key is "user_8814@example.com" instead of 5?

The answer is yes, and the trick is embarrassingly direct. Turn the key into a number, and use that number as an array index.

const buckets: string[][] = new Array(16);           // (1)
const index = hash("user_8814@example.com") % 16;    // (2)
buckets[index].push("user_8814@example.com");        // (3)

1. A plain array of 16 slots, each holding a list.
2. hash turns the string into some large integer; % 16 folds that integer into the range 0–15 so it is a valid index.
3. Store it there. To look it up later, run the same two steps and go straight to that slot.

Everything else in this chapter is the consequences of those three lines: what makes a good hash, what happens when two keys land in the same slot, why the table has to grow, and what "O(1) average" is quietly assuming.

1. What a hash function has to do

A hash function takes a value of any size and returns a fixed-size integer. Three properties matter for a hash table, and they are not the same three that matter for cryptography (Chapter 8.2 covers that case, where the requirements are far stricter).

It must be deterministic. The same key must always produce the same number. Otherwise you cannot find what you stored. This sounds trivial until you hash an object whose field order can vary, or a floating-point number where 0 and -0 compare equal but have different bit patterns.

It must spread keys evenly. If every key hashed to 7, all your data lands in one slot and the table degenerates into a linked list. The goal is that keys which are similar ("user_1", "user_2") land in unrelated slots — the avalanche property, where flipping one bit of input flips about half the output bits.

It must be fast. A hash table's whole selling point is speed. A hash function that takes a microsecond has already lost to a binary search.

Here is a real one, small enough to read completely. This is FNV-1a, used in practice because it is short, fast and spreads well:

function fnv1a(key: string): number {
  let h = 0x811c9dc5;                            // (1)  2166136261, the FNV offset basis
  for (let i = 0; i < key.length; i++) {
    h ^= key.charCodeAt(i);                      // (2)  mix in this character
    h = Math.imul(h, 0x01000193);                // (3)  multiply by the FNV prime, 16777619
  }
  return h >>> 0;                                // (4)  force to unsigned 32-bit
}

1. A fixed starting value. It is not magic — it just needs to not be zero, because XOR-ing into zero and multiplying would let leading zero bytes have no effect.
2. XOR folds the character's code into the accumulated value, changing bits all over it.
3. The multiply is what creates avalanche. Multiplying by a large odd number carries influence from low bits upward across the whole 32-bit word, so a change in the last character still affects the high bits. Math.imul is used rather than * because JavaScript numbers are 64-bit floats and would lose precision; imul does true 32-bit integer multiplication (Chapter 1.4 covers why floats cannot hold large integers exactly).
4. >>> 0 reinterprets the result as an unsigned 32-bit integer, since JavaScript's bitwise operators produce signed values.

Order matters here: XOR-then-multiply (FNV-1a) spreads better than multiply-then-XOR (the original FNV-1), because the final character still gets multiplied through.

Why % tableSize and not something else. The modulo folds an arbitrary 32-bit number into a valid index. If the table size is a power of two you can use h & (size - 1) instead, which is much faster than division — but it also throws away all the high bits and keeps only the low ones, so it only works if the hash function spreads the low bits well. Java's HashMap uses power-of-two sizes and compensates by XOR-ing the high 16 bits down into the low ones first. Implementations that use prime table sizes do so because a prime modulus mixes in contributions from all the bits, which forgives a mediocre hash function.

2. Collisions are not an edge case, they are the normal case

Two different keys hashing to the same slot is a collision. Beginners treat this as a rare accident to be handled defensively. It is not rare — it is guaranteed, and much sooner than intuition suggests.

The birthday paradox is the reason. In a room of 23 people there is about a 50% chance two share a birthday, even though there are 365 days. The general result: with N possible slots you expect a collision after roughly \sqrt{N} items. For a 32-bit hash, N = 4.3 billion and \sqrt{N} \approx 65{,}536 — so a table holding 65 thousand keys will almost certainly have two keys with the identical full hash, before you even apply the modulo. Fold that into 16 slots and you have collisions after about 5 keys.

So a hash table is not "an array plus a hash function". It is "an array plus a hash function plus a collision strategy", and there are two families.

The two collision strategies. Chaining keeps colliding keys outside the array in a list, so the array only ever holds pointers. Open addressing keeps everything inside the array and pushes the colliding key to another slot, which is faster to read but far more delicate to delete from.

Separate chaining. Each bucket holds a list of entries. On collision, append. Lookup finds the bucket, then walks the (usually very short) list comparing keys with real equality — the hash gets you to the bucket, but only a full key comparison can confirm a match, because two different keys can legitimately share a hash.

Chaining is simple, tolerates a high load factor (entries divided by buckets) above 1, and deletion is trivial. Its cost is a pointer chase per entry and one allocation per node. Java's HashMap uses chaining and, since Java 8, converts a bucket into a balanced tree once its list exceeds 8 entries — which turns the worst case from O(n) into O(\log n) and was added specifically as a defence against the attack in section 5.

Open addressing. Everything lives in the array itself. On collision, probe for another slot by a fixed rule: linear probing tries i+1, i+2, …; quadratic probing tries i+1, i+4, i+9, …; double hashing uses a second hash function to choose the step size.

Open addressing is faster to read, because the probed slots are usually in the same cache line, and it allocates nothing per entry. Its costs are real: it needs a load factor well under 1 (usually below 0.7) or probe sequences get long, and deletion is genuinely hard. If you simply empty a slot, you break the probe chain of any key that had to jump over it, and those keys become unfindable. The standard fix is a tombstone: a marker meaning "something was here, keep probing". Tombstones accumulate and eventually force a rebuild.

Linear probing also suffers from primary clustering: a run of occupied slots gets longer at both ends every time anything hashes into it, because any key landing anywhere in the run must probe past all of it. Quadratic probing and double hashing exist to break up those runs.

Python's dict, Ruby's Hash and Rust's HashMap use open addressing variants; Rust's uses SwissTable, which stores one byte of each key's hash in a compact metadata array so a single SIMD instruction can test 16 slots for a match at once.

3. Growing: why the load factor is the real knob

The average chain length is the load factor \alpha = n / \text{buckets}. Lookup costs about 1 + \alpha probes for chaining. So keeping \alpha bounded by a constant keeps lookup constant, and that is the whole reason a hash table resizes.

When \alpha crosses a threshold — 0.75 in Java, 2/3 in Python, 0.875 in Rust's SwissTable — the table allocates a bigger array (usually double) and rehashes every key into it. Rehashing is required, not optional: the index is hash % size, so changing size changes where everything belongs.

That resize is O(n), and it is amortized away by the same doubling argument as the dynamic array in Chapter 4.2. But it has a consequence worth knowing: a single insert can occasionally take milliseconds on a large table. Systems that cannot tolerate that use incremental rehashing — keep both tables alive and migrate a few buckets on every operation until the old table is empty. Redis does this, which is why a Redis instance holding a hundred million keys never stalls on a resize.

The distributed version of this problem is far worse, and Chapter 10.6 covers it: if hash % N decides which server holds a key, then adding one server changes the answer for nearly every key and empties the entire cache at once. Consistent hashing is the fix, and it exists because plain modulo hashing does not survive a changing N.

4. What "O(1) average" actually assumes

This is the sentence to get precise about, because it is the most commonly over-claimed complexity in the field.

A hash table lookup is:

• O(1) average, assuming the hash function spreads your particular keys evenly across buckets, and the load factor is bounded.
• O(n) worst case, when every key lands in one bucket.

Both parts are true simultaneously. The average case is not a guarantee — it is a statement conditional on an assumption about your data. Compare that with the amortized O(1) of push in Chapter 4.1, which is a guarantee: n pushes cost O(n) no matter what an adversary does.

When does the assumption break in ordinary code, with no attacker involved?

A bad custom hash. Hashing a Point object as x + y sends (1,4), (2,3) and (3,2) all to 5. Hashing objects by a field that is often the same value — a status enum, a country code — puts every record in a handful of buckets.

Mutating a key after insertion. If you use a mutable object as a key and then change a field the hash depends on, the entry is now in the bucket for its old hash. Looking it up computes the new hash, goes to a different bucket, and finds nothing. The entry is still in the table, consuming memory, permanently unreachable. This is the reason strings are immutable in most languages and the reason Java's documentation warns against mutable keys.

Inconsistent equals and hashCode. The unbreakable contract is: if two keys are equal, their hashes must be equal. The converse need not hold. Override equality without overriding the hash and your objects compare equal but land in different buckets, so a lookup misses — a bug that is invisible in small tests and appears at scale.

5. Hash flooding: when the average case is chosen by an attacker

In 2011 a presentation at the Chaos Communication Congress showed that most web frameworks were trivially vulnerable to a denial-of-service attack based entirely on this complexity gap.

The attack: a web server parses POST form data into a hash map keyed by field names. The hash function is public and deterministic. So an attacker computes thousands of field names that all hash to the same bucket, and sends one request containing them. Every insertion walks the whole chain, the parse becomes O(n^2), and a single small request burns minutes of CPU. A handful of such requests take a server down. PHP, Java, Python, Ruby, Node.js and ASP.NET were all affected.

Two fixes are used together.

Randomised seeding. The hash function takes a secret random seed chosen at process start, so the attacker cannot predict which keys collide. This is why Python's hash("abc") returns a different number in each new process unless PYTHONHASHSEED is set, and it surprises people who assumed hashes were stable across runs. The lesson generalises: never persist a language's built-in hash value to disk or send it across a network, because it is not stable.

A worst-case fallback. Java's tree-ified buckets (section 2) mean that even a perfect collision attack only degrades lookup to O(\log n) rather than O(n).

Chapter 8.5 covers this as one of the denial-of-service families, alongside ReDoS from Chapter 3.6.10 — both are the same shape of bug, where an attacker chooses input that hits the worst case of an algorithm whose average case is fine.

6. What JavaScript's Map and Python's dict actually do

Both are ordered hash maps, and both got there by a route worth knowing.

JavaScript objects versus Map. A plain {} was never designed as a hash map. Its keys are coerced to strings, so obj[1] and obj["1"] are the same entry, and every object inherits from Object.prototype so obj["toString"] returns a function you never stored — the prototype pollution hazard covered in Chapter 3.6.11. V8 also optimises objects with a fixed set of properties into hidden classes (Chapter 3.6.9), which is fast for records but degrades when you use an object as a growing dictionary.

Map was added to fix all of that: any value can be a key including objects and NaN, keys are compared by identity rather than string-coerced, insertion order is preserved by specification, and it has a real size. Use Map when the keys are data and {} when the keys are known field names.

Python's compact dict. Since version 3.6, dict keeps two structures: a dense array of (hash, key, value) entries in insertion order, and a sparse array of indices into that dense array. The sparse array is the hash table; the dense array is the storage. This saves a lot of memory, because the sparse array holds small integers rather than full entries, and it gives insertion-order iteration as a side effect. That side effect became a language guarantee in 3.7 — the ordering was an implementation detail that everyone relied on, so it was standardised.

Both languages therefore give you the same practical contract: hash-table speed, plus a defined iteration order. That combination is not free elsewhere — C++'s unordered_map and Java's HashMap have no order, and you use LinkedHashMap if you need one.

7. Sets, and the two problems hashing solves in interview questions

A hash set is a hash map with no values — just the keys. Membership testing in O(1) average.

Across the problem chapters you will use hashing for exactly two jobs, over and over:

Job one: "have I seen this before?" Duplicate detection, cycle detection in a state graph, visited-set in BFS and DFS. The reflex: a nested loop asking "does this element appear elsewhere" is O(n^2) and a hash set makes it O(n).

Job two: "group things that share a property". This is the more valuable one, and the trick is choosing what to hash. Grouping anagrams together, for instance:

function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();          // (1)
  for (const word of words) {
    const key = [...word].sort().join('');             // (2)  "eat" → "aet", "tea" → "aet"
    if (!groups.has(key)) groups.set(key, []);         // (3)
    groups.get(key)!.push(word);
  }
  return [...groups.values()];                         // (4)
}

1. A map from a derived key to the list of words sharing it.
2. This line is the whole problem. Two words are anagrams exactly when their sorted letters match, so the sorted string is a fingerprint that is identical for anagrams and different for everything else. Choosing this key is the insight; the rest is bookkeeping.
3. Standard get-or-create.
4. The grouped lists.

Time is O(n \cdot k \log k) for n words of length k, dominated by sorting each word. Using the 26-slot character count from Chapter 4.2 as the key instead (joined into a string like "1#0#0#2#…") drops the per-word cost to O(k) and the total to O(nk).

The transferable lesson: when a problem says "find all the things that are equivalent under some rule", define a fingerprint function that maps equivalent things to the same key, and hash on the fingerprint. Chapter 4.4 is built almost entirely on this move.

What the interviewer will push on

"You said hash lookup is O(1). Under what conditions?" They want the assumption named: a hash that spreads these keys evenly, and a bounded load factor. The worst case is O(n). A candidate who says "O(1), always" has memorised a fact; one who says "O(1) average, O(n) worst case if the keys all collide, and here is when that happens" has understood it.

"What is the difference between amortized O(1) and average O(1)?" Amortized is a guarantee about a sequence and holds against any adversary. Average is conditional on an input distribution and can be defeated by an attacker who chooses the keys. Hash tables are average; dynamic-array push is amortized. This distinction is asked precisely because most people use the words interchangeably.

"Why is deletion harder in open addressing?" Because emptying a slot breaks the probe chain of keys that jumped over it, making them unfindable. The fix is a tombstone marker, and tombstones accumulate until you rebuild. Chaining has no such problem, which is a real reason to prefer it.

"You have a mutable object as a map key and you change one of its fields. What happens?" The entry becomes unreachable — it sits in the bucket for the old hash while every lookup computes the new one. Not an exception, not a wrong value: silently missing data plus a leak.

"How would you make a hash table safe against an attacker who controls the keys?" Random per-process seed so collisions cannot be precomputed, plus a worst-case fallback such as tree-ifying long buckets. Then mention that this is why Python's hash() differs between runs, which shows you have met the consequence and not just the theory.

One thing to volunteer: say which structure you would use if you needed ordered access. A hash map cannot answer "give me the smallest key" or "everything between A and M" at all — those need a balanced tree (Chapter 4.13), which is O(\log n) per operation but keeps things sorted. Naming what hashing cannot do is a stronger signal than listing what it can.

Recall

• A hash table is an array plus a hash function plus a collision strategy; collisions are the normal case, arriving after roughly \sqrt{N} keys by the birthday paradox.
• Separate chaining keeps colliding keys in a list per bucket (simple, deletes easily, tolerates load factor above 1); open addressing probes for a free slot in the array (faster reads, but needs tombstones on delete and a load factor under ~0.7).
• The load factor is the knob: cross the threshold and the table doubles and rehashes everything, which is O(n) and amortized away.
• Lookup is O(1) average, O(n) worst case — average is an assumption about your keys, unlike the amortized guarantee of array push.
• The contract that must never break: equal keys must have equal hashes. Mutating a key after insertion makes its entry permanently unreachable.
• Hash flooding turns the worst case into a denial-of-service attack; the fixes are a random per-process seed and a tree-ified fallback for long buckets.
• The two jobs hashing does in problems: "have I seen this?" and "group by a fingerprint I choose".

Self-test: Why does a 32-bit hash collide after about 65,000 keys and not after 4 billion? · Why can you not simply blank a slot when deleting from an open-addressed table? · What breaks if a class overrides equality but not its hash? · Why does hash("abc") differ between Python runs, and what does that forbid you from doing? · What question can a balanced tree answer that a hash map cannot answer at all?

Next: 4.4 is the first problem set. Nine NeetCode problems, one page each, and every one of them is the same move you just learned — replace a nested scan with a hash lookup, and choose the key well.