# Hash Functions: What Makes a Good One (and Why Yours Isn't)

> Between 'sum the bytes' and SHA-256 lies the workhorse category: non-cryptographic hashes. What avalanche means, how hash quality turns into hash-table throughput, and why every language runtime switched to seeded hashing.

URL: https://harshith.in/blog/hash-functions-non-crypto/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: algorithms, systems, fundamentals

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.