Hashing

The hashers behind the dictionaries and sets.

Generated by bin/build_library_doc.py from the kernel sources. Do not edit by hand: change the generator, or the doc comments in kernel/src/, and re-run it.

Hashing

INTERFACE Hasher

Hasher Distinct in shape from Hashable: Hashable is "this type knows how to hash itself" (hash() on SELF); Hasher OF K is "this object knows how to hash values of type K" (hash(K key) on a separate hasher instance). The latter is the contract for pluggable hashing — a Dictionary / Set may be constructed with a custom Hasher, and when none is supplied the impl constructs a kernel default that delegates to the key's own Hashable.hash().

Implementations should be: - Deterministic: equal K values per Equatable[K] produce equal hashes. Calling hash() twice with the same key yields the same result. - Pure: no observable side effects, no I/O, no mutation of SELF or any reachable state. - Well-distributed for the K-set actually used as keys.

See: interfaces.ev → Hashable; HashConstants.ev → FNV-1a constants.

Hasher OF K — pluggable hash-function interface for Dictionary keys and Set elements. Supply a custom implementation at construction to override the default (which hashes via the key's own Hashable.hash()).

_{kernel/src/Hasher.ev:38}

Methods

METHOD hash(REFERENCE K key) RETURNS uint64

The key is BORROWED, not taken. A bare K key parameter is a type-parameter param, which emits by value — so every call site materialises an owned K (_ev_duplicate) just to compute a hash. Hashing only reads, so it borrows.

CLASS DefaultHasher

IMPLEMENTS Hasher, Cloneable

DefaultHasher implements Hasher OF K (Hasher.ev) for every legal key type in one class. A Dictionary / Set constructed without an explicit hasher CREATEs one of these.

TWO HASHING PATHS, selected at compile time on K's kind:

• K IMPLEMENTS Hashable (String + user classes that declare it): delegate to the key's own hash(). The WHEN K IMPLEMENTS Hashable gate narrows K to a class, so key->hash() reaches THROUGH the _ev_unique<K> handle to the real method. (A bare ELSE would not narrow, and key->hash() would hit the handle, which has no hash() member — this is why the class path MUST be guarded.)

• everything else (numeric primitives + char): FNV-1a mix of the value reduced to a uint64, then FNV-1a mixed. That reduction is a WIDENING for integers and char (exact — a char widens its code point) but it must NOT be one for a float: widening truncates the mantissa, so distinct values would collide. A float therefore takes its own arm and is hashed over its exact binary64 BITS, with -0.0 folded onto 0.0 so that IEEE-equal keys hash alike (NumericUtilities.floatHashBits). Primitives are NOT IMPLEMENTS Hashable (they are Hashable at the type level only — there is no callable .hash()), so they fall to this branch correctly.

Note: a specific-width gate like WHEN K IS float64 is illegal — E1104 only admits IS PRIMITIVE / IS Numeric / IS <class> / IS <group> as kinds, not individual primitive widths. Hence WHEN K IS Floating, a GROUP over both float widths (interfaces.ev), which is admitted where a bare width is not.

See: Hasher.ev (the interface), HashConstants.ev (FNV-1a constants), interfaces.ev → Hashable. DefaultHasher OF K — universal kernel hasher. Delegates to the key's own hash() when K is Hashable (String, user classes); FNV-mixes the widened value for numeric / char keys.

_{kernel/src/DefaultHasher.ev:49}

Constructors

INIT()

Methods

METHOD clone() RETURNS DefaultHasher[K]

Cloneable — so a DefaultHasher can sit in a dictionary's concrete H slot (the dictionaries DUPLICATE their hasher when cloned). Stateless, so a fresh instance is an exact copy.

METHOD hash(REFERENCE K key) RETURNS uint64

CLASS StringHasher

IMPLEMENTS Hasher

A non-parametric Hasher OF String. Functionally identical to DefaultHasher[String] (both delegate to String.hash()), but provided as a concrete named type so the canonical spelling

Dictionary[String, V, StringHasher]

reads naturally and the docs have a concrete hasher to point at.

See: Hasher.ev (the interface), DefaultHasher.ev (the universal hasher), String.ev → hash(). StringHasher — Hasher OF String delegating to String's own FNV-1a hash(). The default hasher for String-keyed Dictionary / Set.

_{kernel/src/StringHasher.ev:25}

Constructors

INIT()

Methods

METHOD hash(REFERENCE String key) RETURNS uint64

CLASS SipHasher

IMPLEMENTS Hasher, Cloneable

A DoS-resistant Hasher OF K backed by SipHash-2-4-64. Keyed by a process-global 16-byte secret (EV_siphash_native.hpp, seeded once from OS entropy), so an attacker cannot predict bucket distribution (hash-flooding defense). The default hasher inside ProHashDictionary; opt-in elsewhere as Dictionary[K, V, SipHasher[K]] / Set[V, SipHasher[V]].

hash() — the 64-bit SipHash-2-4 digest. (Formerly this class also exposed a 128-bit digest; the 128-bit half was removed because nothing consumed it — ProHashDictionary stores and keys on the low 64 bits — so computing it was pure waste. See benchmarks/s04_dict/envzn_siphash_opt for the measurement.)

A String key is absorbed as its raw UTF-8 bytes (via a ByteBuffer). A primitive key is absorbed as the eight bytes of its widened value, mirroring DefaultHasher's primitive path.

_{kernel/src/SipHasher.ev:31}

Constructors

INIT()

The DEFAULT — canonical SipHash-2-4, keyed from OS entropy.

INIT(SipVariant v)

Opt in to the SipHash-1-3 round schedule (a third fewer rounds; the schedule Rust ships). Still keyed from OS entropy. 1-3 is a WEAKER PRF than 2-4 — choosing it is a security decision, not a performance one. See SipVariant.

INIT(uint64 key0, uint64 key1)

Adopt an explicit key — used by clone(), and available when a caller needs a REPRODUCIBLE digest (a fixed key hashes deterministically across runs).

INIT(uint64 key0, uint64 key1, SipVariant v)

Methods

METHOD clone() RETURNS SipHasher[K]

Cloneable — so a SipHasher can sit in a dictionary's concrete H slot (the dictionaries DUPLICATE their hasher when cloned). The clone MUST carry the SAME key AND the same variant: re-seeding (or re-scheduling) here would make the clone disagree with the entries the cloned dictionary copied over, and every lookup in the copy would miss.

METHOD roundSchedule() RETURNS SipVariant

Which round schedule this hasher runs.

METHOD hashSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS uint64

SipHash-64 over a RAW BYTE SLICE buf[off .. off+len) — the fast byte path, and the one byte-keyed callers (StringKeyedDictionary / ProHashDictionary) should use.

This is what hashBuffer below cannot be. It absorbs each 64-bit message word with ONE System->memoryWord wide load instead of assembling it from eight bounds-checked per-byte accessor calls, and HOTLOOP hoists the trailing bytes' per-element bounds check into a single up-front range check. Neither skips a check — both move it — so the memory-safety floor is unchanged.

METHOD hashBuffer(REFERENCE ByteBuffer bytes) RETURNS uint64

SipHash-64 over a ByteBuffer — the byte-sequence core for the generic Hasher OF K String path.

This used to assemble each 64-bit word from EIGHT bounds-checked, handle-indirected bytes[i] accessor calls — the per-element dispatch the s05 study named as the real bottleneck. It no longer does: ByteBuffer.data() hands back a non-owning REFERENCE to the raw binary[] storage (zero copy — the buffer keeps ownership), which is exactly the handle the bulk primitives need. So this now simply delegates to hashSlice, and the ByteBuffer path gets System->memoryWord + HOTLOOP for free. One implementation of SipHash over bytes, not two.

METHOD hashWord(uint64 m) RETURNS uint64

SipHash-64 over a single 8-byte word (primitive keys). No byte loop, so none of the bulk-memory levers apply here — this path is pure round arithmetic, and the only lever on it is the round SCHEDULE (SipVariant).

METHOD hash(REFERENCE K key) RETURNS uint64

Hasher OF K — the 64-bit SipHash-2-4 digest.

CLASS SipState

The SipHash-2-4 compression/finalization state: four 64-bit words mixed by the SipRound. INTERNAL engine driven by SipHasher; one transient instance per hash call.

A VALUE CLASS (§I.J.vi): value identity + inline storage, so a SipState st := CREATE SipState(...) local lives on the stack with no _ev_unique heap handle — no per-hash malloc/free. (It was formerly an INTERNAL heap class, which cost a heap allocation on every hash call — the dominant hasher overhead; see benchmarks/s04_dict/envzn_siphash_opt.)

Runs in 64-bit-output mode: SipHash-2-4-64 (the digest a Hasher.hash() needs). The 128-bit second-half machinery was removed — nothing consumed it (ProHashDictionary stores and keys on the low 64 bits), so computing it was pure waste.

Reference: Aumasson & Bernstein, "SipHash: a fast short-input PRF" (2012), SipHash-2-4 (c = 2 compression rounds, d = 4 finalization rounds).

_{kernel/src/SipState.ev:29}

Fields

• uint64 v0
• uint64 v1
• uint64 v2
• uint64 v3

Constructors

INIT(uint64 k0, uint64 k1)

Methods

METHOD rotl(uint64 x, int32 b) RETURNS uint64

MODIFY METHOD round() RETURNS void

One SipRound.

MODIFY METHOD absorb(uint64 m) RETURNS void

Absorb one 64-bit message word (c = 2 compression rounds).

MODIFY METHOD finalize64() RETURNS uint64

The 64-bit digest (d = 4 finalization rounds), canonical SipHash-2-4-64.

MODIFY METHOD absorbFast(uint64 m) RETURNS void

Absorb one message word with c = 1 (SipHash-1-3).

MODIFY METHOD finalizeFast64() RETURNS uint64

The 64-bit digest with d = 3 (SipHash-1-3).

CLASS FastIntHasher

IMPLEMENTS Hasher, Cloneable

FastIntHasher implements Hasher OF K (Hasher.ev) with an IDENTITY hash: the key widened into a uint64, no mixing. For integer keys this maps the benchmark's sequential keys (0..N-1) to sequential slots under the pow2 & mask index, so every probe is a cache-friendly prefetch — the ~1.5 ns/lookup path that C and C++ take (their std::hash<int> is also identity). char widens its code point. The WordKey qualifier admits no float, so nothing is reinterpreted here; a 128-bit key keeps its low half, which collides only above bit 63 and is separated on lookup by Equatable.

The tradeoff is adversarial weakness: an attacker who controls the keys can force collisions (which is why Rust/Swift default to a slow keyed SipHash). FastIntHasher is therefore OPT-IN — the default stays DefaultHasher (FNV), and untrusted keys use SipHasher / ProHashDictionary. It slots into the existing H type parameter, so it is zero dictionary-API change: a caller writes Dictionary[int32, V, FastIntHasher[int32]] when the keys are trusted integers.

Constrained to WordKey — the primitives whose value IS an integer bit pattern (identity on a class key is meaningless, and a float's bits are not its value): a primitive is Hashable at the type level, so it satisfies the Hasher OF K bound without the IMPLEMENTS Hashable class path that DefaultHasher needs.

See: Hasher.ev (the interface), DefaultHasher.ev (the FNV default), SipHasher.ev (the keyed DoS-resistant hasher). FastIntHasher OF K — identity hasher (widened key) for trusted primitive keys. The ~1.5 ns C-class path; opt in via the dictionary's H slot.

_{kernel/src/FastIntHasher.ev:38}

Constructors

INIT()

Methods

METHOD hash(REFERENCE K key) RETURNS uint64

METHOD clone() RETURNS FastIntHasher[K]

Stateless — a fresh instance behaves identically. Cloneable so a dictionary that stores the hasher CONCRETELY (H hasher, monomorphised) can deep-copy itself (clone()) by cloning its hasher.

CLASS InlineIntHasher

IMPLEMENTS Hasher

Identical hash to FastIntHasher (the key widened into uint64, no mixing), but a VALUE CLASS rather than a regular CLASS. That single difference is the s04 speed lever: a regular-class hasher field lowers to _ev_unique<H> (a HEAP handle), so .hasher->hash(key) compiles to a real, non-inlined call through the pointer — the exact overhead the dict-perf handoff measured. A VALUE CLASS stored as the concrete type parameter H hasher lives INLINE in the dictionary, so -O3 inlines the identity hash and the whole lookup chain collapses to C-class code.

Because a value class cannot be boxed behind a Hasher OF K interface handle in V1 (E1133), InlineIntHasher is used ONLY where the hasher is stored concretely (the H type parameter) — i.e. IntKeyedDictionary. The interface-handle dictionaries (ChainedHashDictionary / ProHashDictionary) keep using the regular-class FastIntHasher.

See: FastIntHasher.ev (the regular-class identity hasher), Hasher.ev (the interface), benchmarks/s04_dict/DICT_PERF_KERNEL_HANDOFF.md (recipe #1: store the hasher concretely).

InlineIntHasher OF K — VALUE-CLASS identity hasher (widened key). Stored inline as a concrete H, so the hash inlines. The monomorphised C-class path for trusted integer keys; opt in via IntKeyedDictionary's H slot. The K IS BLITTABLE qualifier forces every instantiation blittable, so the value class earns its ev_is_blittable partial-spec and lowers to inline (value-array) storage — the blittable-qualifier rule (ENVZN_CONSTITUTION I.J: a generic value class whose TEMPLATE qualifier forces every type param blittable earns the trait).

_{kernel/src/InlineIntHasher.ev:36}

Constructors

INIT()

Methods

METHOD hash(REFERENCE K key) RETURNS uint64

CLASS HashConstants

A stateless utility namespace (like Math) holding the FNV-1a magic numbers that the Hashable kernel types reach into when building their hash() implementations.

Lives in its own file because interfaces.ev may only hold INTERFACE / GROUP / STRUCT declarations (E9003), and a SINGLETON CLASS is neither — so it cannot be co-located with the Hashable / Hasher contracts it serves.

CONSUMERS String, ByteBuffer, DynamicString, DynamicByteBuffer, DateTime, TimeDuration — all reference these from their own hash() / the 32-bit hash bodies that use them.

The 32-bit offset basis is stored in signed form because Envzn int64 cannot hold the unsigned 0x811C9DC5. Callers BXOR with byte values, so the bit pattern is what matters; the signed interpretation is incidental.

See: http://www.isthe.com/chongo/tech/comp/fnv/

HashConstants — a NAMESPACE holding the FNV-1a hash-algorithm constants (offset basis + prime, in 64-bit and 32-bit forms) and the prime bucket-count ladder the chained hash dictionary grows through. Merged from the former HashConstants (FNV) + HashPrimes (ladder).

_{kernel/src/HashConstants.ev:39}

Fields

• uint64 FNV_OFFSET_BASIS_64
• uint64 FNV_PRIME_64
• int32 FNV_OFFSET_BASIS_32
• int32 FNV_PRIME_32
• int64 SIZES_LEN
• int64 SIZES
• int64 POW2_MAX_LEVEL
• int64 SHALLOW_PRIMES_LEN
• int64 SHALLOW_PRIMES

Methods

METHOD initialBucketCount() RETURNS int64

Bucket count for growth level 0 (the initial table size).

METHOD bucketCountAtLevel(int64 level) RETURNS int64

Bucket count at level, clamped to the ends of the ladder. Past the top prime the table stops growing (V1 cap ~196k buckets).

METHOD canGrow(int64 level) RETURNS boolean

TRUE while there is a larger prime to grow into.

METHOD pow2CountAtLevel(int64 level) RETURNS int64

Power-of-two bucket count at level — 16 << level, clamped to the cap.

METHOD indexForHash(uint64 hash, int64 count) RETURNS int64

Bucket index for hash given a power-of-two count: hash & (count - 1). The low bits carry the masked index, so truncating the uint64 hash to int64 first (the mask < 2^31 keeps the result in [0, count)) avoids an int→uint sign-cross while preserving every bit the mask reads.

METHOD mulShiftIndex(uint64 hash, uint64 mult, int64 shift) RETURNS int64

(mult * hash) >> shift — the top 64-shift bits of the product mix ALL input bits (unlike the low-bit mask above), so it distributes a well-mixed hash without a mod. mult is an odd 64-bit constant chosen key-set-aware; shift = 64 - log2(capacity).

METHOD primeAtLeast(int64 target) RETURNS int64

Smallest ladder prime >= target (clamped to the top prime).

METHOD primeModIndex(uint64 hash, uint64 mult, uint64 p) RETURNS int64

(mult * hash) % p — the prime-mode index (fallback tier).

ENUM SipVariant

SipVariant — which SipHash round schedule a SipHasher runs.

STRONG_2_4 (the DEFAULT) is canonical SipHash-2-4: two compression rounds per message word, four finalization rounds. It is the conservative choice and what SipHash's authors specify for general keyed hashing.

FAST_1_3 is SipHash-1-3: one compression round, three finalization — a third fewer rounds, and the schedule Rust ships in its default HashMap. It is still considered adequate against hash-flooding, but it IS a weaker PRF than 2-4, so it is opt-in and never the default: choosing it is a security decision, not a performance one.

_{kernel/src/enums.ev:224}