Every hash table you use rests on an unexamined assumption: that the hash function scatters keys uniformly. When it does, lookups are O(1). When it doesn’t, your hash table is a linked list with extra steps — and sometimes an attacker is the one deciding it doesn’t. The interesting engineering lives in a category most developers never look at directly: fast, non-cryptographic hashes.

The Job Description

A hash-table hash has exactly two requirements: uniformity (spread real-world keys evenly across buckets) and speed (you pay it on every operation). The subtle part is that real keys are not random — they’re user_1, user_2, user_3, sequential IDs, aligned pointers, strings sharing long prefixes. A good hash must turn structured input into unstructured output.

The property that captures this is avalanche: flip any single input bit and each output bit should flip with probability ½. Weak hashes fail visibly here. The classic “sum of bytes” maps "ab" and "ba" together (anagram-blind); h*31 + c (Java’s String.hashCode) is fine-ish for strings but its low bits are so poorly mixed for numeric-ish keys that HashMap runs the result through a supplemental mixing step before using it. Identity-hashing integers (CPython, famously: hash(1) == 1) is a deliberate bet that sequential keys landing in sequential buckets is good (it is — until keys share a stride matching the table size).

The Modern Toolbox

text
  FNV-1a        ~1 byte/cycle    one multiply+xor per byte; fine for tiny keys
  MurmurHash3   ~3 bytes/cycle   the 2010s default; strong avalanche
  xxHash/XXH3   >10 bytes/cycle  SIMD-wide; saturates memory bandwidth
  wyhash        ~fastest today   Go/Zig runtime default lineage
  SipHash-1-3   slower           cryptographically keyed — see below

Two design notes worth internalizing from these: they process words, not bytes (an 8-byte load and one multiply mixes 8 bytes at once — byte-at-a-time is the first thing to abandon), and they finish with a finalizer — a few multiply-shift-xor rounds that exist purely to pass avalanche on the last bytes. That finalizer (e.g. Murmur’s fmix64) is itself the right answer to “how do I hash one integer well”: three lines, full avalanche.

One more trap between hash and bucket: hash % table_size. If the table size is a power of two, the modulo keeps only the low bits — a hash with weak low bits collapses. That’s why implementations either force odd/prime-ish sizing, mix high bits down (Java shifts h ^ (h >>> 16)), or use fibonacci hashing (multiply by 2⁶⁴/φ and take the top bits, which are the best-mixed).

When the Adversary Picks Your Keys

Non-crypto hashes are fully predictable, and that’s an attack surface. Post a JSON body whose keys all hash to one bucket and the server’s parser builds a one-bucket hash table: every insert is O(n), the request is O(n²), and a few hundred KB of crafted keys eats a core for minutes. This is hash flooding (hashDoS), demonstrated against every major web platform in 2011.

The fix the whole industry converged on: SipHash, a keyed hash designed to be unpredictable-without-the-key while staying fast on short keys. The runtime picks a random seed at startup; the attacker can’t precompute collisions. Python, Ruby, Rust, Perl, Haskell all default to it for their dict/hash types. This is also why your language’s hash values differ between runs — iteration-order randomization isn’t rudeness, it’s armor (and it flushes out code that ever depended on dict order). Rust’s HashMap docs spell the trade honestly: SipHash by default for safety, swap in FxHash/ahash for speed when the keys aren’t adversarial — compiler-internal tables do exactly that.

Choosing

The decision tree is short. Hostile or user-supplied keys → keyed SipHash (or your runtime’s default, which already is). Trusted keys, hot path → xxHash/wyhash family, or a strong integer finalizer for scalar keys. Checksumming files or sharding across machines → make sure you want a hash and not CRC32C (error detection, hardware instruction) or a cryptographic digest (integrity against tampering). And never truncate a good hash by % 2^k without checking your low bits — or just steal fibonacci hashing.

Takeaways

  • Hash tables are O(1) only relative to hash quality; avalanche is the property that turns structured keys into uniform buckets.
  • Modern hashes win by word-wide processing plus a mixing finalizer — reuse the finalizer for integer keys.
  • Power-of-two tables use only the low bits; mix high bits down or multiply-shift.
  • Predictable hashes + attacker-chosen keys = hash flooding; runtimes default to seeded SipHash for a reason.
  • Speed-tier (xxHash/wyhash) for trusted keys, keyed (SipHash) for untrusted; don’t confuse hashing with checksums or crypto digests.