std/collections/hashmap
std/collections/hashmap — generic HashMap<K, V>, a pure-Axle
open-addressing SwissTable. Resolves by bare name throughuse std::collections::HashMap; (the file it lives in does not
affect the import path).
C class HashMap<K, V>
get(K) : V | null returns null on a miss — null is a distinct
type, so V | null is a sound union over any V (a value-primitiveV carries a present flag alongside the payload, so 0 is never
confused with absence). Reach the value with get(k) ?? fallback or
an if (get(k) != null) guard. remove returns bool (whether a
binding was present) rather than the prior value.K = f64 is unsupported: NaN-keys and float-precision-as-equality
are common footguns. Use i64 or string instead.
Pure-Axle SwissTable. Mirrors abseil flathashmap / hashbrown :
meta : i8[cap + 16] — meta byte per slot + 16-byte trailing
mirror so a wrap-around SIMD load
never reads past the buffer end.
keys : K[cap] — parallel key array
values : V[cap] — parallel value array
Meta encoding (low 7 bits = h2 hash; MSB = "control"):
0x00..0x7F occupied — low 7 bits are h2(key)
0x80 empty
0xFE tombstone (removed; probing must walk over it)
Hashing dispatches statically per K via the hash_key compiler
builtin — i32/i64 and user classes inline a double-keyed SplitMix64;
string routes to a keyed mix (hashStringSeeded). Both pull the
128-bit OS-CSPRNG @axle_hash_seed_lo/_hi key (HashDoS-safe).
Load factor target 7/8 (hashbrown convention) ; the sum of len andtombstones counts toward the trigger so a churning workload
doesn't degrade to O(n) probe chains. Rehash grows the capacity
(unless live keys fill at most half of it, then it keeps it) and
re-inserts every live entry (tombstones are dropped).
Bit-twiddling on the SIMD match mask goes through cttz_i32 andctlz_i32 (compiler builtins → @llvm.cttz.i32 / @llvm.ctlz.i32).
Constructors
| Type | Method and description |
|---|---|
| constructor() Build an empty map sized to one 16-slot SIMD group, its meta array (plus 16-byte mirror) splatted to the empty sentinel. |
Method detail
#constructor
Build an empty map sized to one 16-slot SIMD group, its meta
array (plus 16-byte mirror) splatted to the empty sentinel.
Methods
| Type | Method and description |
|---|---|
| size(self) : i64 The number of live entries stored. |
| isEmpty(self) : bool True when no live entries are stored. |
| nextSlot(self, start : i64) : i64 The first occupied slot at or after start, or -1 when none remains.A slot is occupied when its control byte has the high bit clear (an empty or tombstoned slot has it set). One half of the pair for (key of map) walks by, with elementAt; the order is the table's,not insertion order. The scan is HashSet.nextSlot's, written out in each class over its owncontrol array: the two tables share the occupancy rule, not the storage. |
| elementAt(self, slot : i64) : K The key in slot, an occupied slot nextSlot returned. This is theiteration protocol's read: it cannot raise, and a slot nextSlot did not return abortsthe process with a message instead of reading a released key. Use elementAtChecked forany other slot. |
| elementAtChecked(self, slot : i64) : K The key in slot, refusing a position that is out of range or holds nolive entry. A removed slot is a tombstone whose key was released. |
| clear(mut self) : void Reset every slot to empty and drop all entries and tombstones. |
| put(mut self, key : K, value : V) : void Insert or overwrite. Grows past the 7/8 load factor first, then SIMD-probes for an existing key (overwrite) or the first hole (insert), reclaiming a tombstone slot when one is chosen. |
| containsKey(self, key : K) : bool Membership probe — stops on the first empty (the probe chain cannot continue past it), walking tombstones along the way. |
| get(self, key : K) : V | null Lookup — returns the bound value, or null when key is absent.The probe stops on the first empty slot (the chain cannot continue past it), walking tombstones along the way. get(k) ?? fallbackis the idiomatic miss-with-default. |
| getOrDefault(self, key : K, defaultValue : V) : V Single-probe variant of get — returns defaultValue on a miss. Bothanswer a miss without raising ( get returns null), and both are oneprobe, so this is the shape a hot lookup loop writes: it avoids a second walk for the default. Algorithm body is identical to get;the only difference is the miss branch. |
| remove(mut self, key : K) : bool Delete by key. Marks the slot as a tombstone (0xFE) when a probe chain may run through it, and as empty otherwise (no group window around it was full); only a tombstone feeds the rehash trigger. |
Method detail
#size
The number of live entries stored.
#isEmpty
True when no live entries are stored.
#nextSlot
The first occupied slot at or after start, or -1 when none remains.
A slot is occupied when its control byte has the high bit clear (an
empty or tombstoned slot has it set). One half of the pairfor (key of map) walks by, with elementAt; the order is the table's,
not insertion order.
The scan is HashSet.nextSlot's, written out in each class over its own
control array: the two tables share the occupancy rule, not the storage.
start slot to resume the search from; the loop passes theslot after the one it just read
#elementAt
The key in slot, an occupied slot nextSlot returned. This is the
iteration protocol's read: it cannot raise, and a slot nextSlot did not return aborts
the process with a message instead of reading a released key. Use elementAtChecked for
any other slot.
slot an occupied position nextSlot returned#elementAtChecked
The key in slot, refusing a position that is out of range or holds no
live entry. A removed slot is a tombstone whose key was released.
slot position to readIndexOutOfBoundsException when slot is out of range or not occupied.#clear
Reset every slot to empty and drop all entries and tombstones.
#put
Insert or overwrite. Grows past the 7/8 load factor first, then
SIMD-probes for an existing key (overwrite) or the first hole
(insert), reclaiming a tombstone slot when one is chosen.
key lookup key; == equality decides the target slotvalue value bound to key, overwriting any prior binding#containsKey
Membership probe — stops on the first empty (the probe chain
cannot continue past it), walking tombstones along the way.
key key whose presence is tested; matched by ==#get
Lookup — returns the bound value, or null when key is absent.
The probe stops on the first empty slot (the chain cannot continue
past it), walking tombstones along the way. get(k) ?? fallback
is the idiomatic miss-with-default.
key key to look up; matched by ==#getOrDefault
Single-probe variant of get — returns defaultValue on a miss. Both
answer a miss without raising (get returns null), and both are one
probe, so this is the shape a hot lookup loop writes: it avoids a
second walk for the default. Algorithm body is identical to get;
the only difference is the miss branch.
key key to look up; matched by ==defaultValue value returned unchanged when key is absent#remove
Delete by key. Marks the slot as a tombstone (0xFE) when a probe
chain may run through it, and as empty otherwise (no group window
around it was full); only a tombstone feeds the rehash trigger.
key key to delete; matched by ==, no-op when absent