Skip to content
Distillate

Hashing

The correctness linchpin. Weak/insufficiently-independent hashing is why existing JS libs measure worse FPR than theory. Getting this right is a differentiator.

Strategy

Derive all probe positions from a small hash by enhanced double hashing, not from N independent hash functions. One hash (murmur3_x86_128) serves every structure: Bloom and Blocked take two of its four 32-bit output words as a/b; Fuse takes its first 64-bit lane.

Kirsch-Mitzenmacher with the RocksDB correction:

g_i = (h1 + i*h2 + i*i) mod m      for probe i = 0..k-1

The + i*i term avoids the degenerate-independence flaw of plain h1 + i*h2. No asymptotic FPR loss vs independent hashes. Kirsch and Mitzenmacher, “Less Hashing, Same Performance” (2006); RocksDB issue #4120.

Default hasher

One hash for every structure except Top-K (below), pinned together with how each structure maps it to positions as flags variant 0 (see serialization.md):

  • murmur3_x86_128 (flags variant 0). Pure Math.imul, one pass over the key, four 32-bit output words. No emulated 64-bit multiply, so it is fast on V8 for every structure. Bloom and Blocked read two words as the double-hash a/b; Fuse reads the first 64-bit lane (h1lo/h1hi) for its fingerprints, retry mixSeed, and Lemire mulhi64 reduction.

A single pass of murmur3_x86_128 beats the previous two passes of murmur3_x86_32 for Bloom/Blocked (both words in one traversal) and replaces the emulated MurmurHash3_x64_128 for Fuse (pure Math.imul, no partial-product multiply), so the whole library shares one hash. Measured on M5: Fuse query about 2x faster, Bloom/Blocked lookups about 1.3x faster than the two-pass baseline.

Pure-JS, zero-dep, synchronous, universal. Chosen because AMQ keys are usually short (IDs, URLs, tokens) where pure-JS beats the WASM call-boundary + marshaling overhead. The 64-bit lane helpers (mul64/fmix64) live once in core/hasher.ts and are now used only by Fuse’s reduction, not the hash body.

  • Carry 64-bit as two 32-bit lanes (hi/lo as Numbers). Never BigInt in hot paths (heap-allocated, ~10x slower).
  • hash128 is allocation-free: flat number locals (no lane objects), inline little-endian byte reads (no DataView), results written to a reused module-scope struct. Zero per-call heap allocation beyond the returned lanes, so steady-state hashing adds no GC pressure. Pure 32-bit Math.imul arithmetic, so no emulated 64-bit multiply in the hash body.
  • All lane math unsigned: >>> 0. This is the #1 source of JS hash-port bugs.
  • Hash once, reuse across all probes. (Incumbent recomputes per op; see bloom-filters issue #60.)
  • String keys go through encodeKey (src/core/bytes.ts), which writes the key’s UTF-8 into a reused, grow-on-demand buffer, so steady-state string hashing allocates nothing (no per-op Uint8Array). The bytes are the same UTF-8 as encode() on every path, so serialized filters stay cross-language readable.
  • Strings of up to 12 chars that are all ASCII are copied with charCodeAt, since an ASCII char’s UTF-8 byte is its code. The first char above 0x7F hands the whole string to TextEncoder.encodeInto, as does any string over 12 chars. For a short key the native call cost as much as the hash: 18.7 ns to encode against 21.4 ns to hash 8 chars on an M5.
  • Why 12: the copy beat encodeInto up to 12 chars and lost from 13 or 14 on both CPUs measured (Apple M5, Intel i5-1235U), by up to 25% at 4 chars. V8 stores a concatenation of 13+ chars as a rope, where charCodeAt costs about twice as much, so 13 is also where keys built by + or template literals turn against the copy. Strings of 12 or fewer are never ropes.
  • Top-K shares the buffer: add and count hash from it and copy a key only when storing it.
  • Hot paths allocate nothing per call. Bloom/Blocked call probeInto/hash32x2Into, which encode the key once into the reused buffer and run one murmur3_x86_128 pass, reading two of its output words. Fuse calls hash128KeyInto(key, seed, out), which writes lanes into a caller-owned struct. hash128/hash128Key keep returning fresh objects for external/test use.

Keyed slot hash (Top-K)

Top-K places keys with HalfSipHash-1-3 (src/topk/halfsip.ts) under 64 random bits per sketch, not murmur.

  • Why: murmur3 has multicollisions that hold for every seed (Aumasson and Bernstein 2012; Ahle for x64_128), so a secret seed cannot stop crafted keys from sharing a slot. Keys brute-forced to one murmur slot made linear-probing add 174x slower at capacity 32,768. Top-K is the structure most often fed untrusted keys (IPs, URLs, user agents).
  • Possible only for Top-K: its frame stores entries in canonical order, so no stored byte depends on slot placement. The key never reaches the frame, bytes stay deterministic, and Top-K has no seed.
  • Cost: HalfSipHash runs at 72 to 78% of murmur’s rate on 8 to 64 byte keys; the Zipf add rate is unchanged within noise.
  • The key is drawn on the first hash, not in the constructor: Cloudflare Workers refuse crypto.getRandomValues at module scope. The only randomness in the package.
  • Verified against the Linux kernel’s test_vectors_hsiphash (HalfSipHash-1-3 build).

Pluggable

interface Hasher {
  hash64(
    key: Uint8Array,
    seed: number,
  ): { h1: number; h2: number; hi1: number; hi2: number };
}

Users may inject their own. Ship xxhash-wasm as an optional fast path for throughput-bound Node/Bun over large keys. Never the default: WebAssembly.compile is blocked on some edge runtimes, the exact portability distillate sells.

Reduction to range

Lemire multiply-shift ((h * m) >>> shift) instead of modulo. For m > 2^32 this needs 64-bit-lane math (another reason to keep the lane representation).

Portability

The flags variant tells a reader which scheme produced the stored bits, and it pins the hash and the index mapping: which output words a structure reads, the probe scheme, the reduction to range, and each structure’s bit layout (the per-structure list is in serialization.md). Any change to one of those takes a new variant even when the hash is unchanged, because the stored bits change while variant 0 would still claim to describe them. Guava hit exactly this: MURMUR128_MITZ_32 and MURMUR128_MITZ_64 share a hash and still needed a new Strategy ordinal. A filter is only cross-language-readable if both sides hash identically; murmur3_x86_128 is fully specified and trivially reimplementable in Rust/Go. A reader rejects a frame whose version or variant it does not implement (UnknownVersionError/UnknownHashVariantError) rather than misread it. The caveat runs one way: a newer reader rejects an older frame, but an older reader predates the check and would silently misread a newer frame, so a consumer must be at least as new as the producer.