Hash

Hash turns a key into a 64-bit number. It is what Basalt’s tables key on, and it is the one function you extend when your own type becomes a key.

const u64 a = Hash(Str("position"));   // a byte string
const u64 b = Hash(node_index);        // any fixed-width integer
const u64 c = Hash(&node);             // a pointer, by address

Basalt does not claim its hash is good. It claims its hash is rapidhash V3 — reimplemented in Basalt’s own types, then proved bit-identical to the reference on 325 frozen vectors. The quality is inherited, not asserted.

Why that claim is the whole design

A hash function is the rare piece of code you cannot check by reading it. Two implementations can look equally sensible and differ enormously in the only property that matters: how evenly they spread keys across a table. The ways a hash fails — poor bit independence, correlation between similar keys, invariance under appended zero bytes — do not look like bugs. Nothing crashes. Lookups just get slower, quietly, forever.

The field’s answer is SMHasher, a battery of around forty statistical tests. Running it is not something a framework does casually, and writing your own small avalanche test mostly proves that your test is small.

So Basalt sidesteps the question. It reimplements a named, already-measured algorithm — rapidhash V3 by Nicolas De Carli, the successor to wyhash, used by Chromium, Node.js and Meta’s Folly — and then proves the reimplementation produces the same bits as the original on a corpus that crosses every branch inside the algorithm. If the outputs are identical, the function is rapidhash, and it has rapidhash’s published results.

The reference implementation is not in this repository. It was compiled once, outside the tree, to print a table of expected values. Only that table was kept.

Three things it does not promise

These are the properties a caller cannot see and would otherwise assume.

The hash is unseeded — it is not HashDoS-resistant

The same key hashes to the same value in every run of every build. If your keys come from an untrusted source, an attacker who knows the algorithm can pick keys that all land in one bucket and turn your table into a linked list.

Basalt is not a web server, and seeding costs real time on every lookup, so the framework does not pay for it. If your keys are attacker-controlled, write your own overload that seeds however you need.

The value is not stable — never store it

Do not persist a hash, do not transmit it, do not compare one produced by two different builds. The algorithm is pinned to rapidhash V3 by choice, not by contract, and a hash whose output is frozen by promise can never be improved.

If you need a stable digest — a cache key on disk, a value in a file format, a checksum over the wire — you need a specified hash function, not this one.

It is not cryptographic

Collisions can be constructed on purpose. Nothing here resists an adversary who wants two keys with the same hash.

What it hashes

Call	Hashes
Hash(String8)	The bytes. Length, content, nothing else.
Hash(u8/u16/u32/u64)	The value, zero-extended to 64 bits.
Hash(i8/i16/i32/i64)	The value, sign-extended to 64 bits.
Hash(char), Hash(bool)	The value.
Hash(const void*)	The address. Any object pointer converts, so one overload covers them all.
Hash(AnyEnum)	The enumerator’s numeric value, scoped or unscoped.

The byte-string hash depends on the bytes and nothing else. Not on where they sit in memory, not on their alignment, not on the machine’s byte order — the same bytes give the same number on x86-64 and on ARM64.

Hashing a const char* is a compile error, on purpose

Hash("mesh.bin");                         // does not compile
Hash(Str("mesh.bin"));                    // the content
Hash(static_cast<const void*>(pointer));  // the address, deliberately

A C string would otherwise convert to const void* and hash its address. Two equal strings at two addresses would land in different buckets and your lookup would simply never hit — at run time, silently, with nothing wrong to see at the call site. The overload is deleted so the compiler says so instead.

Extending Hash to your own types

There is no trait to specialise, no base class, no registration. Declare a function next to your type and overload resolution finds it — the same mechanism ErrorToString uses.

struct AssetId
{
    String8 path;
    u32     generation;
};

[[nodiscard]] u64 Hash(const AssetId id)
{
    // Fold one field into the next: each bs::Hash call spreads its whole input across all 64 bits.
    return bs::Hash(bs::Hash(id.path) ^ id.generation);
}

Three rules for writing one:

• Hash exactly the fields that operator== compares. Two keys that compare equal must hash equal, always. Hashing a field that equality ignores — a cached pointer, a scratch flag — breaks lookups in a way that is very hard to see.
• Fold each field through bs::Hash, do not combine them raw. A table takes its bucket index from one end of the hash and a fingerprint from the other, so a combination that varies only in its low bits degrades both ends at once. Each bs::Hash call already spreads its input across the whole word, so folding one result into the next input keeps that property.
• Qualify the nested calls. Inside your own Hash, the framework’s is hidden — see below.

Inside your own Hash, spell the nested calls bs::Hash

Basalt finds your overload by argument-dependent lookup — that is why nothing has to be registered. The reverse does not hold. Inside the body of your own Hash, ordinary lookup finds the name you are declaring and stops there, and a u64 is a fundamental type that brings no namespace of its own for lookup to recover Basalt’s overload from. So this does not compile:

namespace game
{
    [[nodiscard]] u64 Hash(const AssetId id)
    {
        return Hash(Hash(id.path) ^ id.generation);   // does not compile
    }
}

error C2664: 'u64 game::Hash(const game::AssetId)': cannot convert argument 1 from 'u64' to 'const game::AssetId'

Two details make this easy to get wrong:

• The inner call is fine on its own — id.path is a String8, so argument-dependent lookup does reach bs. Only the outer call, on a u64, fails. An overload that folds one String8 field and nothing else compiles, and the next field you add breaks it.
• It does compile if your Hash sits in the global namespace and you have a using namespace bs; in scope, because then Basalt’s overloads are what ordinary lookup finds too. That is a property of where you happened to put the function, not of the mechanism — move it into a namespace of its own, which is what real code does, and it stops compiling.

Qualify both calls, or hoist the overload set once:

[[nodiscard]] u64 Hash(const AssetId id)
{
    using bs::Hash;
    return Hash(Hash(id.path) ^ id.generation);   // fine, in any namespace
}

Do not hash a struct as raw bytes

Hash(Str8(reinterpret_cast<const u8*>(&id), sizeof(id)));   // wrong

AssetId has four bytes of padding after generation, and padding bytes are indeterminate. Two keys that compare equal can carry different garbage there, hash differently, and never find each other. Hash fields, not memory.

Your overload also overrides the built-in one for that type, which is the escape hatch for everything in Three things it does not promise.

If your hash is genuinely good, say so

The associative containers do not use a hash as one number. HashMap takes a slot index from the low bits and a 7-bit fingerprint from the top; HashTrie reads the top two bits at a time. So they mix whatever they are given first, because the u64 Hash(MyKey) { return key.id; } everyone writes first would otherwise silently degrade them.

Basalt’s own overloads do not need that mix — that is what the avalanche audit measures — so the containers skip it for them, worth about 1.5 ns of 24 on a string-keyed lookup. Your own overload can opt in:

namespace bs
{
    template <>
    struct HashIsAvalanching<EntityId> { static constexpr bool value = true; };
}

The default is the safe one, and it is the right one for most hashes

false is what you get by saying nothing, and it is correct for anything that reads a field, adds, or XORs. Only a real mixer — the kind of thing Hash(u64) is — should claim otherwise. A wrong claim is not a compile error and not a crash: it is a container that grows mysteriously slow under load.

Fixed-size keys use the same algorithm, not a second one

A key that is eight bytes or fewer — an integer, a pointer, an enum — goes through Hash(u64), and every other fixed-width overload funnels into it. That function is the byte-string algorithm with its length known to be eight: at that length its two overlapping word reads land on the same word, so both collapse onto the register your value is already in and no byte buffer is ever built. Same computation, same value as Hash(Str8(bytes, 8)) over the value’s little-endian bytes, same reference vectors.

There is no second entry point to choose between, and that is the result of a measurement rather than a shortcut. Basalt implemented the obvious alternative — a single folded multiply, which is what abseil ships for absl::Hash<uint64_t> — measured it inside a real open-addressed lookup, and deleted it although it was faster: on a Ryzen 9 5950X, 0.54 ns against 0.76 ns per hash built with cl 19.4x and 0.43 ns against 1.20 ns built with clang-cl 19.1.1. Either way that is 10–20 % of a lookup in an L1-resident table and nothing at all in a table large enough to miss cache.

It was deleted because it fails the strict avalanche criterion, and not narrowly. Flipping input bit 63 flips output bit 63 every single time. A table that takes its bucket index from one end of the hash and its fingerprint from the other cannot use a word whose top bit is a copy of an input bit, and no throughput number buys that back. Both the audit that measured it and the benchmark that priced it are still in tests/benchmarks/, so the rejection can be re-run rather than believed.

The primitive underneath

The mixing step is one 64×64→128 multiply with its two halves folded together — the operation every modern non-cryptographic hash is built from. It is exposed on its own, because it is ordinary arithmetic that fixed-point scaling and 128-bit accumulation want too.

const Product128 product = Multiply64To128(left, right);
// product.low is what a plain `left * right` would give you.
// product.high is the half that would otherwise be lost.

It is a single instruction on x86-64 and two on ARM64, and it lives in basalt/core/Intrinsics.h next to PopCount64 and CountTrailingZeros64. It is also constexpr, which is not decoration: MSVC does not constant fold _umul128, so a wide product of two literals that ought to vanish at compile time otherwise emits a real multiply on every call — worth 30 % of Hash(u64) when it happens inside a hash, measured with cl 19.4x at /O2. That one is MSVC’s alone: Clang and GCC compile the same call through __uint128_t, which they fold themselves.

API summary

Parameters, assertions and the full contract are documented in basalt/core/Hash.h.

Signature	Purpose
Hash(String8 key)	Hashes bytes. rapidhash V3, Nano variant, unseeded.
Hash(integer) / Hash(bool) / Hash(char)	Hashes a fixed-width value.
Hash(const void* address)	Hashes a pointer by identity.
Hash(enumerator)	Hashes any enumeration by its numeric value.
Multiply64To128(u64 left, u64 right)	Both halves of the exact 128-bit product. constexpr.