DenseHashMap

DenseHashMap<K, V> is HashMap<K, V> with the values moved out of the table. The slots hold the keys and a 4-byte index; the values live side by side in a separate array, in insertion order, and GetValues() hands you that array whole as a Span<V>.

One difference — where the value lives — and it changes four separate promises: iteration order, pointer stability, insert cost at a large V, and whether the values can be walked as a plain array.

Everything else is identical. Same SwissTable, same sixteen-slots-per-instruction probe, same reservation model, same hashing rules. Read HashMap first; this page covers only what differs.

The layout

// HashMap: the value is in the slot.
//
//   metadata [ 0x2A | 0x80 | 0x91 | ... ]
//   slots    [ {key, value} ]
//                     ▲
//            one load gets you both

// DenseHashMap: the slot points at it.
//
//   metadata [ 0x2A | 0x80 | 0x91 | ... ]
//   slots    [ {key, u32 index} ]
//                      │
//   values   [ v0 | v1 | v2 | ... ]  ◄─┘
//              packed, insertion order

The values array is a VirtualArray<V>, which is where three of the four differences come from: it is contiguous, it appends in order, and it never moves what it already holds.

What it buys

The values as a contiguous Span<V>. This is the reason the type exists. A system that updates every value without caring which key it belongs to gets a flat array to walk, which vectorises and prefetches like any other array:

UpdateAll(transforms.GetValues());          // one contiguous pass, no map involved

Insertion order. Iteration, and GetValues(), visit entries in the order they were inserted — for as long as no EraseSwap has run on the map. HashMap<K, V> promises nothing here.

A V* that survives inserts. A rehash relocates slots, and the values are not in the slots, so a pointer from Find stays valid across any number of later inserts.

What invalidates it here is an erase

EraseSwap moves the last value into the hole, EraseOrdered shifts everything after it, and Clear drops the lot. Each of those moves values, so each invalidates pointers into them — and so does a FindValueIndex result, which stays in range while pointing at a different entry, which is the quieter of the two failures.

A cheaper insert, and less memory, when V is large. An insert writes a 4-byte index into the slot instead of the whole value, and a rehash relocates 4-byte indices instead of whole values.

What it costs

One dependent load per lookup. The slot has to arrive before the value’s address is even known, and dependent loads do not pipeline. This is not a fixed few nanoseconds you can amortise; it is a second trip that cannot start early.

More memory when V is small. The separate value array plus the reverse index that maps a value back to its slot are pure overhead when the value would have fitted in the slot anyway.

Measured at the 7/8 ceiling of a 262 144-slot table — 229 376 entries, u64 keys, queries drawn at random:

sizeof(V)	ns/hit		ns/insert		bytes/entry
	HashMap	DenseHashMap	HashMap	DenseHashMap	HashMap	DenseHashMap
8 bytes	7.6	10.3	15.0	15.9	19.4	32.0
32 bytes	8.5	11.8	14.7	16.2	46.9	56.0
256 bytes	10.6	23.4	53.6	27.4	302.9	280.0

MSVC release build, x86_64, minimum of 11 runs after 3 warm-ups, pinned to one core. The same directions hold under clang-cl. Misses cost about 13 ns on both types at every value size — a miss reads no value at all, so sizeof(V) barely touches it. Read the 256-byte row for its ordering, not its digits: its spread has read as high as 100 % on the inline hit column, and the ordering is what is stable.

HashMap wins the lookup at every value size, including the ones where you might expect the dense layout to pull ahead. Walking the same queries in insertion order halves the dense map’s 256-byte hit (23.4 → 11.6 ns) and leaves the two level or the dense one ahead — but that is the prefetcher streaming the value array, not a property of the map, and it is exactly the order a table has no say over. There is no lookup crossover. At random, the inline map wins every row on both toolchains.

What the dense map wins is the insert at a large V — 2.0x at 256 bytes, because it moves 4 bytes into the slot instead of 256 — and the memory there, 280 bytes per entry against 303. At a small V it costs 65 % more memory.

Which one to use

Choose DenseHashMap<K, V> for a property, not for speed. Four of them, any one of which is enough:

• the values have to be walkable as a contiguous Span<V>;
• iteration must follow insertion order;
• a V* must stay valid across inserts;
• V is large and the workload inserts far more than it looks up.

Otherwise choose HashMap<K, V>. It is faster at lookups at every value size, and lookups are what maps mostly do.

Basalt does not choose for you based on sizeof(V). Folly’s F14 does, and the result is that the type’s own API changes with its element type — a values-as-span accessor that compiles for some V and not others. Two names keep the trade where you make it.

Two erases, and why the name is the warning

HashMap<K, V> has one Erase, because nothing else moves when a slot is vacated. Here the values are packed, so removing one leaves a hole in an array that has to be closed — and there are two ways to close it.

	Cost	The value array afterwards
EraseSwap(key)	O(1)	The last entry lands in the hole. Order destroyed, permanently.
EraseOrdered(key)	O(N)	Everything after the hole shifts down. Order kept.

Measured on 262 144 entries with a 32-byte value: EraseSwap tens of nanoseconds — 38 to 45 ns across invocations of the same binary, so read the magnitude and not the digits; EraseOrdered 262 µs at a random position and 548 µs at the front, both of which repeat within a few percent.

The 2x between those last two is the useful part: the cost is the entries after the hole, so it depends on where the hole is, and quoting only the front quotes the worst case as if it were the price. (HashMap::Erase is 24 to 29 ns on the same rows.)

Neither is chosen for you, the same way Array<T> ships RemoveSwap under a name that says what it does.

One EraseSwap ends the insertion-order guarantee for good

Not just for the entry it moved. The map has no record of what the order used to be, so it cannot restore it, and GetValues() from then on is in an order rather than the order. If you need the ordering to hold, use EraseOrdered — or accept the O(N) once at the end rather than per erase, by rebuilding.

Iterating

for (const auto entry : transforms)          // key and value, in insertion order
{
    Update(entry.key, entry.value);
}

UpdateAll(transforms.GetValues());           // the same values, contiguous

Any mutation invalidates every iterator

An iterator kept across an erase addresses past the live values, and its own bounds check passes because it captured the entry count when it was made. Re-obtain it from begin() after every mutation — the loop above is safe only because it mutates nothing.

Sizing the reservation

Reserve() and GetMaxEntryCount() work as they do on HashMap<K, V>, with one addition worth knowing: GetMaxEntryCount() is the smaller of what the table can hold and what the value array can hold, and for a large V it is the value array that binds first. Check the number the map reports rather than the one you passed.

The same erase/insert-at-the-ceiling trap applies here as well — see Size the reservation above the working set.

Element requirements

As HashMap<K, V>, plus one ceiling of its own: 2³² − 1 entries, because the slot addresses its value with a 4-byte index.

API summary

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

The lifecycle, reading and writing surfaces match HashMap<K, V> name for name — Reserve, TryReserveCapacity, Find, FindBy, GetOr, Contains, Set, TrySet, TryGetOrInsert, Clear, GetCount, GetCapacity, GetMaxEntryCount, begin / end. What follows is what only this map has, and what it does not have.

Only on DenseHashMap

Signature	Purpose
GetValues()	Every value, contiguous, in insertion order.
FindValueIndex(key)	The key’s position in GetValues(), or nullptr.
FindValueIndexBy(key, hash, equal)	The same, by a precomputed hash and/or a probe key of another type.
EraseSwap(key)	Removes in constant time. Does not preserve order.
EraseOrdered(key)	Removes and preserves order. O(N).

Not on DenseHashMap

Signature	Why
Erase(key)	Ambiguous here. The two named forms above say which cost you are paying.