Status: Accepted. Which hasher each shape gets stays open until it is measured (D5).
Date: October 4, 2026
Answers: the owner’s question, while #419
weighed three candidates for the Trusted hash, whether one hasher can be the
best for every map. It cannot: if there were a best hasher, everyone would use it.
Related: ADR-010 D5 (trust chooses the hasher), D6 (iteration
order is unspecified), D7 (--trust reports the choice); ADR-296
D14 (keys are compared in full); ADR-314 D1 (what a grammar
matched is a fact, its length included); ADR-005 D8 (the ledger
is deterministic); ADR-311 (a table’s lookup is the compiler’s
choice, not a type of the program’s).
ADR-010 splits hashing on one axis: who chose the keys. A
Trusted map gets a fast hash with a fixed seed, and an Untrusted one gets a
keyed hash with a random seed. Within Trusted, one function serves every map:
nikaia_std::hash::FxHasher.
1BRC shows what one function costs. A station name’s length changes from row to
row, and the three branches that finish Fx’s tail (>= 4, >= 2, >= 1) are
mispredicted 0.79 times a row more than tuned’s loop, which copies the tail
into a word (benches/brc/README.md). For k-nucleotide, every key in a table
has the same length. There the same branches are always predicted, and a
function that does extra work to avoid them would only add instructions.
Integer keys never reach the tail at all.
Which function is best depends on what the keys look like. Measuring which candidate is best in general asks a question that has no answer.
| Language | Its answer | What it costs there |
|---|---|---|
Rust std |
one keyed SipHash for every map; the program names another hasher in the map’s type | every compute workload pays for an adversary it does not have; a fast map is a different type in every signature |
| Go runtime | the map picks its access path by key type (mapaccess1_fast32, _fast64, _faststr) and one AES-based hash behind them |
the specialisation is by type only; a string’s length is never known |
C++ std::hash |
one function per key type, chosen by the type | no trust axis; quality is up to each implementation |
| Swift | per-process seeded SipHash for every Hashable |
as Rust, without the escape hatch in the type |
What transfers: the key’s type is the first and most reliable thing to choose by (Go). What does not: putting the hasher into the map’s type (Rust). It freezes one implementation into every interface that mentions the map, which ADR-311 already refused for a perfect-hash table.
The compiler decides a map’s hasher in two steps. Trust (ADR-010)
decides the class: a fast hash with a fixed seed, or a keyed hash with a random
seed. The keys’ shape (D2) then chooses a function within that class. An
Untrusted map keeps its keyed hash whatever its keys look like. A key whose
shape is known does not become less attacker-chosen.
| Shape | How the compiler knows it |
|---|---|
a fixed-width value: an integer, a char, a bool, a struct or tuple of those |
the key’s type |
| text or bytes of a known length | a fact of the walk: a grammar binding of a fixed count, a slice of a constant length (ADR-314 D1) |
| text or bytes of unknown length | the default for text |
The shape is never guessed from a sample of the input or from a profile. A build whose result depends on the data it was profiled with breaks ADR-005 D8. A length the compiler cannot show is an unknown length.
Nothing in a program mentions hashing unless the program wants to (D4).
--trust (ADR-010 D7) prints, for every map, its trust, its
key shape and the hasher the two chose. The ledger records the same thing, so a
changed choice shows up in a diff.
let mut seen = collections::HashMap(; hasher: hash::Sip)hasher: takes any hasher std::hash offers, or a type of the program that
implements hash::Hasher. It follows the named-option convention
ADR-010 D3 uses for trusted:, and it is written where the map
is made, not in its type, so nothing else that mentions the map changes.
An override is not refused for any trust. A fixed-seed or home-made hasher on
untrusted keys is the program’s call, as trusted: true is. It is recorded in
the ledger as an override with its source location, and --trust lists it
under the map with the trust it overrides. The security review stays a read of
one generated file.
Until then every Trusted shape keeps today’s FxHasher, so this record
changes no generated code by itself. A candidate for a shape is measured in a
Nikaia program that has that shape, built by the compiler, never in a harness
that hashes outside a program. A harness hashes another type (&[u8] with a
length prefix, not str with its 0xff) and measures a different call.
| Shape | Reference program |
|---|---|
| text of unknown length | examples/1brc.nika, 1 M rows |
| text of a known length | k-nucleotide |
| identifiers in the toolchain’s own maps | nikaia lower crates/nikaia-std/src/tools/ty.nika |
The output is compared first, then instructions and --branch-sim
mispredictions with callgrind, and the clock only where it moves by more than
this box’s 10 % (benches/brc/README.md). A candidate is taken for its shape
when its program gets better, and every other shape keeps its hasher, so no
other program is touched by the change.
A different function iterates a Trusted map in a different order. That order
was never promised (ADR-010 D6), and a compiler release may now
change it for one shape and not another. A program that needs an order asks for
one.
Keys are compared in full whatever hashed them (ADR-296 D14). A hasher chosen by shape may read only part of a key to hash it. It never decides that two keys are equal.
Trusted hasher, chosen by measuring candidates against each
other. Fx’s branches cost 1BRC mispredictions and cost k-nucleotide
nothing. A function that avoids them adds work where they were free. “Better
in general” means “worse somewhere else”.HashMap[K, V, H]). Every signature that
carries the map carries the choice, and a better function for a shape becomes
an interface change. D4’s option at construction gives the same freedom
without that.--trust already make every such choice
auditable, as they do for trusted: true.The first shape. Trusted text, of any length the compiler does not know, is
folded into one word by the byte hash of rustc-hash 2 before the Fx step, and
numbers keep the Fx step alone (crates/nikaia-std/src/hash.rs). The two
shapes are told apart by the path the key arrives on, write or
write_u64, so the compiler has nothing to classify for them yet. Measured
with callgrind, output equal: 1BRC 364.9 → 344.1 instructions and 3.42 → 1.58
mispredictions a row; k-nucleotide 1292 M → 1204 M instructions and
3.26 M → 1.29 M mispredictions; nikaia lower ty.nika unchanged at 383 M
(benches/brc/README.md, #419).
k-nucleotide’s keys of one length per table did not need a shape of their
own: the function that helps 1BRC helps them too.
Untrusted maps use std’s SipHash. D2’s text of a known length, D3’s
report lines, D4’s hasher: option and hash::Hasher are open.