Hash functions

Turn a key into an integer, spread evenly. A table is only as good as its hash.

The one rule

• Mix the whole key — every byte influences the result
• Fast: O(key length), run on every lookup
• Deterministic + good avalanche (1 bit in → ~half the bits change)
• Failure mode: hashing on part of the key (first letter, length)

Watch a good vs a bad hash

FNV-1a stays even blue. First-letter hash lights up a few buckets red. Same words, same buckets — only the mixing differs.

Distribution: even vs skyline

First-letter: 51 words in one bucket, 11 buckets empty. Chi-square 509 vs 15.

Match the hash to the job

• Table: fast non-crypto — FNV, polynomial, SipHash (hash())
• Security: cryptographic — SHA-256 (hashlib), never for tables
• Randomize the seed → resist collision-flooding DoS

Takeaway

Mix the whole key, keep it fast. Use hash(). Next: sets and multisets — hash tables of keys.