Hashing

HASHING DSA · 03 — the O(1) magic behind every dict, map & set — and the collisions you must tame a hash table trades a little math for near-instant lookup: turn a key into an array index and jump straight there. it's the most-used data structure in all of programming — and the engine under DDIA's hash index, hash joins & sharding. 1 · THE HASH TABLE goal: store key → value with O(1) average insert / lookup / delete. the trick: compute WHERE to look. 'cat' key hash() hash function 3941 % size fit to table = 5 0 1 2 3 4 5 6 7 'cat'→val array of buckets a HASH FUNCTION maps arbitrary input → a fixed-size integer, deterministically. good = FAST + UNIFORM (spreads keys evenly) + deterministic. index = hash(key) % table_size. lookup repeats the exact same computation → lands on the same bucket → O(1). no scanning the whole table. (note: this is NOT a cryptographic hash — those are for security, a different job. here we only want spread.) a hash SET is the same thing storing only keys (membership); a hash MAP stores key→value. dict, object, {}, Map. the whole idea in one line: don't SEARCH for the slot — COMPUTE it. 2 · COLLISIONS (two keys, one bucket — inevitable) pigeonhole: more possible keys than buckets → some keys collide. HOW you resolve it defines the table: A · CHAINING 0 1 2 3 k1 k2 each bucket holds a LINKED LIST; collision → append. lookup = hash, then scan the short list. simple, degrades gracefully. (Java HashMap; trees for long chains.) B · OPEN ADDRESSING (probing) 0 1 2 3 4 taken probe → next free store everything IN the array; on collision PROBE for the next free slot (linear/quadratic/double-hash). cache-friendlier (no pointers), but clusters; delete needs TOMBSTONES. (Python dict, Go map.) the tradeoff: chaining is simple & delete-friendly; open addressing is cache-friendly & compact. both are common. either way, keep collisions RARE and lookups stay ~O(1) — which is the load factor's job → 3 · LOAD FACTOR, RESIZING & THE REAL COMPLEXITY LOAD FACTOR α = entries / buckets. as α climbs, buckets fill, collisions rise, and lookups slow down. when α crosses a threshold (~0.7), the table RESIZES: allocate a bigger array (2×) and REHASH every key into it. that's an O(n) step — but rare (geometric), so it's AMORTIZED O(1), exactly like the dynamic array (l.01/02). THIS is why 'dict is O(1)': it's kept sparse by resizing. complexity, honestly: insert / lookup / delete AVERAGE O(1) (good hash + low load factor) WORST O(n) (all keys collide → one long chain) resize O(n) once in a while, amortized away the worst case is REAL: an attacker who knows your hash can feed colliding keys → 'HashDoS' (a DoS via O(n) lookups). mitigations: a good hash, a RANDOMIZED seed per process (SipHash), tree-upgraded buckets. 4 · WHAT HASHING BUYS YOU & when NOT to use it · SET membership ('have I seen this?') — dedup, visited-sets · MAP key→value — caches, memoization (l.01), config, counts · FREQUENCY / group-by — count occurrences, bucket records · two-sum in O(n) on an UNSORTED array (a seen-map, vs l.02's sorted two-pointer) · HASH JOIN — build a map of one table, probe with the other (DDIA batch, ties MapReduce map-side join) DDIA callbacks: the hash index (Bitcask), hash partitioning / sharding, Bloom filters (probabilistic membership). WHEN NOT TO: hashing is UNORDERED. no range queries, no 'next largest', no sorted iteration, no prefix search. HASH TABLE = O(1) average, but NO order. TREE (l.05) = O(log n), but SORTED / range-queryable. need instant key lookup → hash. need order, ranges, or 'closest' → a balanced tree. that's the whole choice. JARGON, DECODED hash table = key→index→bucket store · hash function = arbitrary input → fixed-size int (fast, uniform, deterministic) · bucket = an array slot · hash set / map = keys only / key→value collision = two keys → same bucket (inevitable, pigeonhole) · chaining = bucket holds a linked list · open addressing = probe for the next free slot (linear/quadratic/double hash) · tombstone = a deleted-marker slot load factor α = entries/buckets · resize/rehash = grow the table & re-place keys (amortized O(1)) · HashDoS = adversarial colliding keys forcing O(n) · SipHash = a keyed hash that defeats it average O(1) vs worst O(n) = typical vs all-collide · hash join = build-a-map + probe · Bloom filter = probabilistic 'maybe/definitely-not' set (DDIA) · hashing is UNORDERED — trees (l.05) when you need order