nx_murmur3.nx
buildroot/runtime/nx_murmur3.nx
about
murmur3.nx -- MurmurHash3 (Austin Appleby 2008/2011).
Fast non-cryptographic hash. Distributes well across the
output range, fast (4-byte chunks), suitable for hash tables
when adversarial inputs aren't a concern (otherwise use
siphash.nx).
Used by: ClickHouse, Cassandra, Hadoop, Lucene, RocksDB
secondary indices, Bloom filters, sketch data structures.
We ship only the 32-bit variant (MurmurHash3_x86_32) because
it's the most widely deployed. 64-bit and 128-bit variants
exist (x86_128, x64_128) and produce different output.
Invariants:
MM1 Pure function: hash(seed, bytes) is deterministic; no
global state, no random.
MM2 Output is exactly 32 bits packed into i64's low half.
MM3 NOT cryptographically secure. An attacker can craft
keys that collide; never use as a MAC or to defend
against algorithmic-complexity attacks on hash tables
in adversarial contexts.
dependencies 1 imports · 14 importers
diagram shows first 10 each side; +0 more imports, +4 more importers in the complete lists below.
imports: nx_syscalls.nx
imported by: nx_bloom.nxnx_sketch_bloom.nxnx_sketch_cms.nxnx_sketch_counting_bloom.nxnx_sketch_cpc.nxnx_sketch_cpc_dense.nxnx_sketch_hll.nxnx_sketch_hll4.nxnx_sketch_hll_packed.nxnx_sketch_hllmap.nxnx_sketch_kmv.nxnx_sketch_linear_counter.nxnx_sketch_theta.nxnx_sketch_tuple.nx
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| none |
consts
| 32 | const MM_C1: i64 = 0xCC9E2D51 |
| 33 | const MM_C2: i64 = 0x1B873593 |
| 34 | const U32_BITS: i64 = 0xFFFFFFFF |
functions
| 37 | func mm_rotl32(x: i64, r: i64) -> i64 called by 1: murmur3_32 |
| 44 | func mm_load_u32_le(buf: *u8, off: i64) -> i64 called by 1: murmur3_32 |
| 54 | func murmur3_32(seed: i64, key: *u8, len: i64) -> i64 called by 21: bloom_insertbloom_containsmainnx_bloom_insertnx_bloom_containsnx_cms_add+15 calls 2: mm_load_u32_lemm_rotl32 |
| 96 | func main() -> i64 calls 1: murmur3_32 |