Axle v0.22.0
Package

std/collections/hashmap

std/collections/hashmap — generic HashMap<K, V>, a pure-Axle
open-addressing SwissTable. Resolves by bare name through
use 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-primitive
V 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 and
tombstones 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 and
ctlz_i32 (compiler builtins → @llvm.cttz.i32 / @llvm.ctlz.i32).

Constructors

TypeMethod 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

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

TypeMethod and description
i64
size(self) : i64 The number of live entries stored.
bool
isEmpty(self) : bool True when no live entries are stored.
i64
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 own
control array: the two tables share the occupancy rule, not the storage.
K
elementAt(self, slot : i64) : K 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.
K
elementAtChecked(self, slot : i64) : K 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.
void
clear(mut self) : void Reset every slot to empty and drop all entries and tombstones.
void
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.
bool
containsKey(self, key : K) : bool Membership probe — stops on the first empty (the probe chain
cannot continue past it), walking tombstones along the way.
V | null
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) ?? fallback
is the idiomatic miss-with-default.
V
getOrDefault(self, key : K, defaultValue : V) : V 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.
bool
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

size(self) : i64

The number of live entries stored.

#isEmpty

isEmpty(self) : bool

True when no live entries are stored.

#nextSlot

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 own
control array: the two tables share the occupancy rule, not the storage.

Parameters
start slot to resume the search from; the loop passes the
slot after the one it just read

#elementAt

elementAt(self, slot : i64) : K

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.

Parameters
slot an occupied position nextSlot returned

#elementAtChecked

elementAtChecked(self, slot : i64) : K ! IndexOutOfBoundsException

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.

Parameters
slot position to read
Throws
IndexOutOfBoundsException when slot is out of range or not occupied.

#clear

clear(mut self) : void

Reset every slot to empty and drop all entries and tombstones.

#put

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.

Parameters
key lookup key; == equality decides the target slot
value value bound to key, overwriting any prior binding

#containsKey

containsKey(self, key : K) : bool

Membership probe — stops on the first empty (the probe chain
cannot continue past it), walking tombstones along the way.

Parameters
key key whose presence is tested; matched by ==

#get

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) ?? fallback
is the idiomatic miss-with-default.

Parameters
key key to look up; matched by ==

#getOrDefault

getOrDefault(self, key : K, defaultValue : V) : V

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.

Parameters
key key to look up; matched by ==
defaultValue value returned unchanged when key is absent

#remove

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.

Parameters
key key to delete; matched by ==, no-op when absent