HashTrie

HashTrie<K, V> is a hash map that lives in an arena you supply, and that never moves an entry. Insert a million more keys and every pointer you took out of it still points at the same value.

HashTrie<String8, u64> offsets = {};                    // a zeroed struct is an empty map

HashTrieSet(arena, offsets, Str("entry"), 0x1000);

u64* offset = HashTrieGet(offsets, Str("entry"));       // nullable: absence is not a failure
if (offset != nullptr)
{
    *offset += 8;                                       // a writable alias — no second lookup
}

There is no bucket array. The map grows by allocating one node and linking it into a four-way branch chosen by the hash — so it never rehashes, never copies, and never abandons memory.

The problem it solves

Most readers arrive with std::unordered_map, or with a flat open-addressed table. Both keep a bucket array, and both eventually outgrow it: they allocate a bigger one, re-insert every entry into it, and release the old one.

On an arena, nothing is released. The old table stays resident for the arena’s whole lifetime, and the entries have all moved, so every pointer you were holding is now aimed at a dead table that still reads back plausible values.

A hash trie has no table to outgrow.

	Flat table	HashTrie<K, V>
Growth	Allocate a bigger table, re-insert everything	Allocate one node
Entries move	On every rehash	Never
Memory abandoned	The whole previous table	None
Lookup	One or two loads	One dependent load per five bits of hash

The last row is the price, and it is a real one. Read What it costs before choosing this over a flat map for a long-lived, lookup-heavy table — on u64 keys the measured gap against HashMap<K, V> is 4x to 5x.

The model: five bits of hash per level

A node holds one entry and up to 32 child slots. A lookup takes the top five bits of the hash to pick a slot, shifts the hash left by five, and repeats — so a key stored at depth 3 was placed by the first fifteen bits of its hash.

hash = 0b11010 01100 10001 ...
          │     │     └── level 2 → slot 17
          │     └──────── level 1 → slot 12
          └────────────── level 0 → slot 26

Only the slots that exist are allocated. A node carries a 32-bit occupancy bitmap and an array of exactly its children; the slot’s place in that array is the population count of the bits below it. So a node with two children costs two pointers, not thirty-two — the trick is Bagwell’s, from the hash array mapped trie.

An insert walks the same path until it reaches an empty slot, and puts its node there. That is the entire structure. Nothing is reserved in advance, no size is estimated, and no load factor is tracked.

This shape was not invented for Basalt. RAD Debugger ships it as its general-purpose map, and Chris Wellons published the same trie independently, both at a fan-out of four. Two arena-school authors converging is a stronger argument than either alone; the wider fan-out here is Bagwell’s, and it halved the depth.

Pointers stay valid

This is the property you choose the type for.

u64* counter = HashTrieGet(counters, key);
// ... thousands of further inserts, from anywhere ...
*counter += 1;                                  // still the same object

A lookup hands back a writable alias of the value in the map, so *slot = x stores without a second descent. That alias stays valid for as long as the arena does. Only erasing that entry, or clearing the map, invalidates it.

Which map to reach for

Basalt ships three, because one layout cannot serve every job, and their contracts differ rather than just their speed. HashTrie<K, V> is the arena-resident one: it promises stability and takes an arena. HashMap<K, V> is the opposite on every axis — lookup latency above all, and your entries moved when it grows. A pointer from this one is a handle that outlives any number of inserts; a pointer from that one is a borrow that dies at the next one. DenseHashMap<K, V> sits between them: values that survive inserts, in a contiguous array, but still an owning map that cannot live in arena data. Choosing a container puts the three in one table.

A zeroed struct is an empty map

There is no Create, no Reserve, no init call.

HashTrie<u64, Handle> map = {};                     // ready to use

struct Node
{
    HashTrie<u64, Handle> children;                 // a map inside arena-resident data
    u32                   flags;
};
Node* node = arena.Push<Node>().data;               // Arena::Push zeroes → `children` is usable

That is the whole reason this type is worth having next to a flat map at all. A map that owns an OS reservation costs microseconds per instance and cannot sit inside arena data at all; this one is 32 bytes and costs nothing until its first insert.

Deletion, and what a tombstone costs

Erasing has two outcomes, and which one you get depends on whether the node has children.

The erased node	What happens
Has no children	It is unlinked and put on the map’s free list — the next insert reuses it before touching the arena
Has children	It becomes a tombstone: it keeps its place and its subtree, but holds no entry

A tombstone is not garbage to be collected later. The next insert whose path walks over it revives it in place, storing the new key in the node that is already there. So there is no compaction pass, no rebuild threshold, and an erase allocates nothing.

A churning map grows even at a constant size

A tombstone is free at the moment you erase, and it is not free in aggregate. Nothing ever revisits one: it is reclaimed only if some later key’s path happens to cross it, so a tombstone whose last live descendant is erased afterwards stays in the trie for good. If you evict keys and insert keys the map has never held — an eviction cache, a sliding window — the node count climbs past the live count and does not come back, while count never moves.

Measured (basalt_bench_hash_trie, 64 rounds of evicting half of 65 536 entries): count stays at 65 536, nodes go 65 536 → 105 678 (1.61x), and 34.1 % of the final nodes sit in subtrees holding no live entry. A cache that re-inserts recently evicted keys reclaims far more than that; a map that only grows pays none of it.

The reclaiming forms are HashTrieClear, which puts every node on the map’s free list so a refill allocates nothing, and rewinding the arena — an ArenaScope around the whole map.

HashTrieErase(map, key);          // returns true if something was there
HashTrieSet(arena, map, other, v);  // may well reuse the node that was just freed

Iteration is a walk

There is no contiguous storage, so there is no Span over the entries and none is promised. Range-for walks the trie.

for (const HashTrieEntry<String8, u64>& entry : offsets)
{
    ConsoleWriteLine(ConsoleStream::Out, entry.key);
}

The order is unspecified

Iteration order is a function of the keys’ hashes and of the sequence of inserts and erases that built the map. It is not insertion order, and a map rebuilt with the same entries in a different order iterates differently. It is stable only for as long as you do not mutate the map.

When you want a flat array, copy one out — into a different arena than the nodes live in, usually — and sort it:

const Span<HashTrieEntry<String8, u64>> flat = HashTrieFlatten(arena, offsets);
SortBy(flat, [](const auto& l, const auto& r) { return l.value < r.value; });

Never write entry.key

The entry is a plain struct, so assigning its key compiles. It corrupts the map: the node’s position was decided by the old key’s hash, so the entry becomes unreachable under either key. Nothing detects it, and nothing crashes. Write value; to change a key, erase and insert.

Clearing does not give memory back

HashTrieClear empties the map and recycles every node onto the map’s own free list, so refilling to the size you just cleared allocates nothing.

It does not return anything to the arena — an arena has no per-object release. A map that has once held a million entries keeps a million nodes’ worth of arena resident until the arena itself is rewound.

Fill-and-clear in a loop still grows the arena

Only if each cycle grows past the previous peak. If it does, rewind the arena instead: wrap the work in an ArenaScope, or build the map on a scratch arena.

This covers fill-and-clear only. The other way a map grows while its size stays constant is eviction churn — a pattern that never reaches a clear at all — see Deletion, and what a tombstone costs.

What it costs

Two things, and both are structural rather than tunable.

A dependent load per five bits of hash. Each step of the descent must complete before the next address is known, so the loads cannot overlap. At a million entries that is roughly ten serially dependent cache misses, against one or two for a flat table. At a few hundred entries — a job’s working set, a node’s children — the whole map is in cache and the chase is cheap. That is the size this type is for.

A node per entry. 48 bytes for a {u64, u64} map, 64 for {String8, u64}, plus the child pointers a node actually has — an occupancy bitmap, a child array, a parent link, the entry, and a cached hash when the key type wants one.

The two node sizes are pinned by static_asserts in the unit suite and re-derived from arena positions by basalt_bench_hash_trie. The dependent-load claim above it is mechanism, not measurement: there is no flat map to measure it against.

Colliding keys, and the bottom of the hash

A 64-bit hash carries twelve whole levels of five bits. Past that there is no hash left, and every further step takes slot 0.

Only keys whose hashes are exactly equal ever get below that point — going deeper than the hash is long would need an ancestor sharing more bits than the word has. Two distinct hashes differ in one of the five-bit chunks, so they part company at depth 13 at the latest. Equal-hashing keys chain one node per key and cost one key comparison per level — correct, terminating, and no worse than any bucket chain.

Re-hashing at that point would not help, and the map does not try: every key placed below the exhaustion point shares all 64 bits with its ancestor’s hash, so any further function of the hash gives them identical results again. Only ordering the keys could separate them, and this map never compares keys for order.

Hash is unseeded, so collisions can be searched for

An attacker who chooses your keys can find colliding hashes offline and turn every lookup into a walk of a long chain. If your keys are attacker-controlled, write your own Hash overload that seeds however you need.

Supplying Hash and equality

Your key type needs a Hash overload; declare one next to the type and overload resolution finds it. Equality goes through operator== by default, and String8 keys use Str8Equal.

namespace app
{
    struct Identifier { u32 value; };

    inline bool operator==(Identifier a, Identifier b) { return a.value == b.value; }
    inline u64  Hash(Identifier id)                    { return bs::Hash(id.value); }
}

Hash and equality must agree

Two keys that compare equal must hash equally. If they do not, the map holds two entries for one key and which one a lookup finds is unspecified. Nothing checks this.

The map re-mixes whatever your Hash returns before using it, because it reads the hash from the top down: a Hash that returned a small id unchanged would send every id into slot 0 and turn the map into a linked list. The mix costs about a nanosecond per operation and removes a failure that is silent and catastrophic.

If your key’s equality walks memory — a path, an interned buffer — specialize HashTrieStoresHash<K> to true and each node will cache its hash, so a failed comparison on the way down costs one integer compare instead of a memory walk. String8 already does.

Looking up by a precomputed hash, or by another key type

HashTrieGetBy is the trie’s version of the flat map’s FindBy: you bring the hash and the comparison, so a key you already hashed is not hashed twice, and a probe type that is not the stored key type can still find its entry.

u32* const handle = HashTrieGetBy(assets, probe, Hash(spelled_out), matches);

The hash you pass is the plain one — the trie applies its own mixing to it, so this entry point and HashTrieGet always agree about where a key lives. The same warning applies as for the flat map: a probe key that compares equal to a stored one must hash to the same word, nothing checks it, and getting it wrong is a silent miss.

Telling the trie your hash is already good

The trie reads the hash from the top, five bits at a time, so it mixes what it is given before descending — a Hash that returns a small id unchanged would send every id down the same child and turn the map into a linked list. Basalt’s own overloads do not need that, and the trie skips it for them. Your own key type opts in the same way it does for HashMap, by specialising bs::HashIsAvalanching, and with the same warning: say it only if it is true. Here a wrong answer costs a linked list rather than a longer probe.

Not synchronised

Nothing here takes a lock.

A lookup that finds nothing is still not a reader

A concurrent insert publishes a child pointer with a plain store, so a “read-only” lookup racing against it can observe a half-linked node. And two threads inserting into two different maps that share one arena race on that arena’s position.

What the trie does give — and a flat map cannot — is that an insert never moves an existing entry, so a concurrent reader’s pointers stay valid. That is a precondition for a future lock-free design, not thread safety today.

Element requirements

K and V must be trivially copyable and trivially constructible, because the nodes come from Arena::Push, which calls no constructor. HashTrie<const K, V> does not compile: take a const reference to the map instead.

API summary

Parameters, assertions and invariants are documented in basalt/core/HashTrie.h.

Looking up

Signature	Purpose
HashTrieGet(map, key)	The stored value as a writable alias, or nullptr.
HashTrieGetBy(map, key, hash, equal)	The same, by a precomputed hash and/or a probe key of another type.
HashTrieGetOr(map, key, fallback)	The stored value by copy, or fallback.
HashTrieContains(map, key)	Whether the key is present.

Inserting

Signature	Purpose
HashTrieSet(arena, map, key, value)	Stores value under key, replacing what was there.
HashTrieGetOrInsert(arena, map, key, value)	Returns what is there, inserting value first if nothing is.

Removing

Signature	Purpose
HashTrieErase(map, key)	Removes one entry. Returns whether there was one.
HashTrieClear(map)	Empties the map, recycling its nodes. Returns nothing to the arena.

Whole map

Signature	Purpose
HashTrieFlatten(arena, map)	Copies every entry into one contiguous span in arena.
begin() / end()	Range-for support over every live entry.

Fields

Field	Purpose
root	The trie. Null when the map has never held an entry.
free_list	Nodes an erase or a clear reclaimed. Reused before the arena is touched.
count	Live entries. What iteration visits and a flatten allocates.
tombstone_count	Erased nodes still in the trie because they have children.

Customisation points

Name	Purpose
Hash(K)	Required for your key type. See Hash.
HashTrieKeyEqual(K, K)	Defaults to operator==; overload it if your key has none.
HashTrieStoresHash<K>	Specialize to true when your key’s equality walks memory.