HashMap

HashMap<K, V> is a key-value map that owns the memory it lives in. It is a SwissTable, the design behind Abseil’s flat_hash_map, Go 1.24’s built-in map and Rust’s hashbrown, and it is the map to reach for unless one of the other two has a property you specifically need.

The map owns a reservation, so when it grows it hands the old table’s memory back to the operating system. A map that grows to a million entries does not leave a dead half-million-entry table behind.

Its sibling DenseHashMap<K, V> is the same table with the values stored elsewhere; everything on this page about the model, the reservation, hashing and probing applies to it unchanged. HashTrie<K, V> is the arena-resident map, and it is a different structure entirely. Choosing a container puts the three side by side.

The model: a byte of metadata per slot

A classic open-addressed table stores keys in an array and probes it one slot at a time, comparing a whole key at each step. A SwissTable adds a second, much smaller array: one byte per slot.

That byte says	Value
The slot holds an entry, and here are 7 bits of its hash	0hhhhhhh
The slot has never held an entry	0x80
The slot held one and it was erased	0xFE

Sixteen of those bytes fit in one SIMD register, so a single instruction compares a key’s 7-bit fingerprint against sixteen slots at once and returns a bitmask of the candidates. A lookup usually reads one 16-byte block of metadata, finds a single candidate, and compares exactly one key.

  hash ──┬── low bits  ─────────► which group of 16 to look at
         └── top 7 bits ────────► the fingerprint to match inside it

  metadata  [ 0x80 | 0x2A | 0x91 | 0xFE | 0x2A | 0x80 | ... ]   16 bytes
  compare against 0x2A, all sixteen at once  ──►  bitmask 0b...010010
                                                          │      └─ slot 1: compare the key
                                                          └──────── slot 4: compare if the first missed

The 7 bits come from the top of the hash and the group index from the bottom, which is why the hash has to be well distributed across the whole word — Hash is, and the map mixes whatever else you give it before using it, so a hand-written Hash that only fills the low bits does not quietly destroy the filter.

Two consequences of the layout are worth holding on to. A miss usually costs no key comparison at all: no fingerprint matched, so there was nothing to compare. And the whole probe touches one cache line of metadata for sixteen candidate slots, which is why the table stays fast at high load factors where a classic open-addressed table degrades.

Growing gives the memory back

This is the part that is different from every arena-backed collection in Basalt, and it is why these maps own their memory instead of borrowing an arena.

Every flat hash table eventually outgrows itself. The standard answer is a rehash: allocate a table twice the size, re-insert everything, abandon the old one. On an arena, “abandon” is permanent — an arena frees by rewinding, so a map grown to a million entries leaves roughly a million entries’ worth of dead table resident for as long as that arena lives.

A map that owns a reservation does something an arena cannot.

// On an arena: the old table is
// unreachable but still resident.
//
//   grow -> new table
//        -> old table leaks
//
// Total waste after N doublings:
// about one whole table.

// Owning a reservation:
//
//   Commit(new range)
//   re-insert
//   Decommit(old range)
//
// Physical pages return to the OS.
// Permanent waste: zero.

What is consumed instead is address space — the reservation holds two table-sized regions and the map alternates between them. On a 64-bit process that is not a scarce resource. See VirtualArray for why reserving addresses is not the same as using memory.

Using one

Creation is two steps, like every owning type in Basalt: a constructor that cannot fail, then the one call that can.

HashMap<String8, u32> counts;
if (const auto reserved = counts.Reserve(); !reserved.ok)
{
    return Err(reserved.error);
}

counts.Set(Str("frames"), 60);

if (const u32* frames = counts.Find(Str("frames")); frames != nullptr)
{
    Log("%u", *frames);
}

Reserve() takes a maximum entry count, defaulting to 16 million. It costs address space, not memory — nothing is committed until the first insert. It is a hard ceiling: an insert past it returns failure rather than reserving more.

GetMaxEntryCount() is the number to check against, not the one you passed — the table rounds a request up to a power-of-two capacity.

Size the reservation above the working set, not at it

A map held exactly at its ceiling by an erase/insert cycle — an LRU, a bounded cache — cannot double, so every insert falls back to rebuilding the table at the same size to purge tombstones: an O(capacity) rehash per insert. Measured on 229 376 entries, that is 2.1 ms per erase/insert round trip against 28 ns with a reservation twice the size. Reserve for the peak and then some; the reservation is address space, and address space is not the scarce resource.

A lookup returns a nullable pointer, never a Result. A key that is not in a map is a normal outcome, not an error, and the pointer hands you a writable alias so updating needs no second lookup.

if (u32* count = counts.Find(key); count != nullptr)
{
    *count += 1;                 // no second probe
}

Use GetOr(key, fallback) when you only want to read, and TryGetOrInsert(key, value) when absent means “start at this value”.

A pointer from Find is a borrow

This is the one contract on this page you cannot skip.

A pointer from Find is invalidated by the next insert. Any insert may rehash, and a rehash moves every entry. Use the pointer before you mutate the map, or copy the value out.

A stale pointer here is not a use-after-free

After a rehash the old table’s pages are handed back to the operating system, so a stale pointer may fault rather than return wrong data. That is the better failure, but it is still a failure — treat every pointer from this map as valid only until the next insert.

When a V* has to survive inserts, the two other maps both give you that: DenseHashMap<K, V> keeps its values in a VirtualArray<V> that a rehash does not touch, and HashTrie<K, V> never moves an entry at all.

Erasing, and what a tombstone costs

Erasing from a SwissTable usually leaves a tombstone — the 0xFE byte above, saying “something was here” — because a probe that once passed through this slot must keep going to find what lies beyond it.

The map cleans them up on its own: when tombstones rather than entries are what filled the table, it rebuilds at the same size instead of doubling. So a map that is filled and emptied repeatedly does not grow forever, and an erase never has to be followed by a compaction call of your own.

Erase(key) costs 24 to 29 ns on a 262 144-entry table with a 32-byte value, and nothing else in the map moves.

Iteration order is unspecified

HashMap<K, V> promises nothing about it. Its order is the table’s, and a rehash changes it. Two maps holding the same entries may iterate them differently. Do not build anything on it — when you need an order, DenseHashMap<K, V> gives you insertion order, and sorting a flattened copy gives you any other.

Iteration is a scan of the metadata array, sixteen slots at a time, which is why it is cheap despite the empty slots.

Any mutation invalidates every iterator

And the failure is harder than a wrong answer: an iterator kept across an insert that rehashed points into pages the map has already handed back to the operating system. Re-obtain it from begin() after every mutation.

Supplying Hash and KeyEquals

Both come from free-function overload sets, the same mechanism ErrorToString uses. Declare them next to your key type and the map finds them:

struct EntityId { u64 value; };

u64  Hash(EntityId id)                     { return bs::Hash(id.value); }
bool KeyEquals(EntityId a, EntityId b)     { return a.value == b.value; }

HashMap<EntityId, Transform> transforms;   // no trailing template arguments

Integers, enums, bool, pointers and String8 are covered already. String8 keys compare by content, so a lookup with a string built somewhere else finds the entry.

Hash and KeyEquals must agree

Two keys that compare equal must hash equally. Nothing checks this. A violation inserts an entry the map can never find again, and it looks exactly like an ordinary miss.

Telling the map your hash is already good

The map mixes the hash it is given before using it, because it reads a group index from one end of the word and a 7-bit fingerprint from the other — and return id.value; puts everything in one end. That mix is a multiply on the critical path of every lookup, and it buys nothing when the hash was already well spread.

Basalt’s own Hash overloads are already well spread, so the map skips the mix for them. If your own Hash is too — a real mixer, not a field read — say so:

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

A hasher you pass as a template argument says it directly instead:

struct MyHash
{
    static constexpr bool is_avalanching = true;

    u64 operator()(const EntityId id) const { return SomeRealMixer(id.value); }
};

Only say it if it is true

Declaring a hash avalanching when it is not is neither a compile error nor a crash. It is longer and longer probe chains as the map fills, showing up as a map that is mysteriously slow under load and fine in every test. It is worth about 1.5 ns of 24 on string keys — never worth a wrong answer.

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

Find hashes the key it is given, with the map’s own hasher. When you already hold the hash, or when your probe key is not the stored key type, FindBy takes both from you:

// A view over bytes somebody else owns, probing a map keyed by String8.
struct PathView { const u8* data; usize size; };

const auto matches = [](const String8 stored, const PathView probe)
{
    return stored.size == probe.size && Str8Equal(stored, Str8(probe.data, probe.size));
};

const PathView probe{ bytes, length };
u32* const handle = assets.FindBy(probe, Hash(Str8(probe.data, probe.size)), matches);

The hash you pass is the plain one, as Hash(key) returns it — the map applies its own mixing policy to it, exactly as it does to a key of its own type.

You own the correspondence

A probe key that compares equal to a stored key must hash to the same word. Nothing can check it, and getting it wrong is a silent miss, not an error. This is why FindBy is its own name and not an overload of Find: an overload would let HashMap<u64, V>::Find(some_i32) compile and hash through the wrong overload, producing a different word for the same number.

What this map is not

It owns an OS reservation, which places it beside Arena rather than among the arena-resident containers.

• It cannot live inside arena data. A map has a destructor, and an arena never runs one. The same applies to any struct with a map as a member. Use HashTrie<K, V> there.
• It costs a reservation per instance — around 3 µs on Windows. Fine for a handful of long-lived maps; wrong for thousands of small ones.
• It is not synchronised. A lookup that finds nothing has mutated nothing and is still unsafe against a concurrent insert, because that insert may rehash and move everything.
• It is move-only. A move transfers the reservation and empties the source. To release early, assign a fresh one: map = HashMap<K, V>{};

Element requirements

Keys and values must be trivially copyable — a rehash relocates entries by plain assignment and runs no constructor or destructor. HashMap<const K, V> does not compile.

API summary

Parameters, assertions and invalidation rules are documented in basalt/core/HashMap.h.

Lifecycle

Signature	Purpose
HashMap<K, V>()	An empty map holding no reservation. Cannot fail.
Reserve(max_entry_count)	Acquires the reservation. Defaults to 16 M entries. Returns a Result.
TryReserveCapacity(count)	Grows the table now, so a fill does not rehash.

Reading

Signature	Purpose
Find(key)	The value, or nullptr. Writable alias.
FindBy(key, hash, equal)	The same, by a precomputed hash and/or a probe key of another type.
GetOr(key, fallback)	The value by copy, or fallback.
Contains(key)	Whether the key is present.
GetCount() / IsEmpty()	Live entries.
GetCapacity()	Slots in the current table.
GetMaxEntryCount()	The reservation’s hard ceiling.
begin() / end()	Range-for over { key, value } entries.

Writing

Signature	Purpose
Set(key, value)	Inserts or overwrites. Asserts when it cannot grow.
TrySet(key, value)	The same, returning the slot or nullptr.
TryGetOrInsert(key, value)	The existing value, or the one just inserted.
Erase(key)	Removes a key. Leaves a tombstone the map reclaims on its own.
Clear()	Empties the map. Keeps the table and its committed pages.

Customisation points

Name	Purpose
Hash(K)	Required for your key type. See Hash.
KeyEquals(K, K)	Defaults to operator==; overload it if your key has none.
HashIsAvalanching<K>	Specialise to true when your Hash already mixes.