Module collections/hash_map
Hash map with a SwissTable-style control-byte layout.
Each bucket has a one-byte control value — CTRL_EMPTY, CTRL_DELETED,
or the low 7 bits of the key's hash — held in an array beside the entries,
so a probe rejects a bucket after one byte compare and only touches the
entry when those 7 bits match. The probe sequence itself is LINEAR
((h1 + i) % capacity) and the control bytes are compared ONE AT A TIME:
this is hashbrown's memory layout, not its SIMD group scan.
get/insert/remove are O(1) average; the table doubles at a 7/8 load
factor, and a table over that threshold because of tombstones rather than
live entries is rehashed in place instead of doubled.
Stability
unstable — the shape is settled (D9's infallible insert + try_insert,
D14's pointer iter(), the single-probe entry API), but four fields of
the backing struct — ctrl, data, capacity, size — are still PUBLIC,
and plans/archive/STD_API_STABILIZATION.md §4 lists making them private as open
work in this group: HashSet already took that change (capacity() and
friends became accessors) and this map has not. §5 also has one undecided
question here: new() stays deterministically keyed because the bootstrap
fixpoint gate needs byte-identical emitted C, so a with_random_keys()
convenience over with_keys may still be added. Freezing follows the field
privatization; everything else about this module is additive already.
Types
High-performance hash map using SwissTable algorithm.
Keys must implement Eq and Hash. Provides O(1) average lookup, insert, and delete.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(K : Type, V : Type), where(K <: Send, V <: Send), HashMap(K, V), Send())
impl(generic(K : Type, V : Type), where(K <: Sync, V <: Sync), HashMap(K, V), Sync())
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), ...)
_alloc_buf : (fn(alloc : Option(Allocator), bytes : usize, align : usize) -> ?*void)Returns: ?*void
_free_buf : (fn(owned : bool, p : *void, bytes : usize, align : usize) -> unit)Returns: unit
_owned : (fn(self : &Self) -> bool)Returns: bool
tombstones : (fn(self : &Self) -> usize)Slots holding a tombstone (CTRL_DELETED) — a read-only diagnostic.
Returns: usize
_set_tombstones : (fn(self : &mut Self, n : usize) -> unit)Returns: unit
allocator : (fn(self : &Self) -> Option(Allocator))_alloc_with_capacity : (fn(capacity : usize, alloc : Option(Allocator)) -> Result(Self, HashMapError))Returns: Result(Self, HashMapError)
_hash : (fn(self : &Self, key : &K) -> u64)The bucket hash of key under this map's keys.
Returns: u64
new : (fn((alloc : Option(Allocator)) ?= .None) -> Self)Empty map with room for DEFAULT_CAPACITY (16) buckets, hashed with
the FIXED SipHash keys.
Fixed keys mean iteration order is reproducible run to run — the
compiler's own fixpoint gate depends on it — and therefore that a map
fed untrusted keys is open to collision flooding; with_keys is the
answer there. Like Rust's HashMap::new, it allocates NOTHING until the
first insert (capacity 0, no bucket arrays): most maps a program makes
stay empty or tiny, and an eager 16-bucket table cost the compiler
~270 B per empty map, one per scope frame
(plans/backlog/CODEGEN_MEMORY_REDUCTION.md §0.4). The first insert grows it to
DEFAULT_CAPACITY on the global allocator.
alloc : .Some(a) places both buffers in a instead, and every resize
and the final release go through a. A placed map allocates its 16
buckets right away, because its buffers are how it remembers a, and
PANICS when that allocation fails.
Returns: Self
with_keys : (fn(k0 : u64, k1 : u64) -> Self)Empty map whose hashes are keyed by k0, k1 (SipHash-1-3 keys).
Two maps with different keys place the same key in different buckets, so
a map fed by untrusted input can be given per-process random keys
(std/crypto/random) to defeat collision flooding. new() uses fixed
keys so iteration order is reproducible.
Returns: Self
_bucket_count : (fn(requested_capacity : usize) -> usize)Returns: usize
with_capacity : (fn(requested_capacity : usize, (alloc : Option(Allocator)) ?= .None) -> Self)Empty map sized for requested_capacity buckets, rounded UP to a power
of two (never below the 16-bucket default) because bucket selection
masks the hash.
Note this is a BUCKET count, not the entry count Rust's
with_capacity promises: the 7/8 load factor means the map still
resizes after about capacity * 7 / 8 insertions. alloc : .Some(a)
places both buffers in a, as for new. PANICS on allocation failure.
Returns: Self
from : (fn(generic(N : usize), sink(pairs) : Array(Tuple(K, V), N)) -> Self)Consuming constructor from a fixed-size array of (key, value) pairs —
Rust's HashMap::from([(k, v); N]):
HashMap(String, i32).from([(a, i32(1)), (b, i32(2))]).
The array is taken by sink, so the caller's binding ends at the call,
and every pair moves into the map: nothing is copied. A repeated key
keeps the LAST pair's value, as a run of inserts does.
Returns: Self
_ctrl_ptr : (fn(self : &Self) -> *u8)Get ctrl pointer (unwrapped for internal use)
Returns: *u8
_data_ptr : (fn(self : &Self) -> *MapEntry(K, V))Get data pointer (unwrapped for internal use)
Returns: *MapEntry(K, V)
_find_bucket : (fn(self : &Self, key : &K, hash : u64) -> Option(usize))Bucket holding key, or .None. Walks the LINEAR probe sequence and
stops at the first CTRL_EMPTY, which is what makes remove able to
turn a slot back into EMPTY only when its successor already is.
Returns: Option(usize)
_probe : (fn(self : &Self, key : &K, hash : u64) -> BucketProbe)Walk the probe sequence for key ONCE, reporting either the bucket that
holds it or the bucket it would be inserted into.
The vacant answer prefers the first TOMBSTONE on the chain over the
terminating empty slot, so insert/remove churn reuses slots instead of
lengthening every chain — the same choice _find_insert_bucket makes.
Returns: BucketProbe
_find_insert_bucket : (fn(self : &Self, hash : u64) -> usize)First reusable bucket (EMPTY or DELETED) on hash's LINEAR probe
sequence. Panics on a full table — the caller resizes first.
Returns: usize
_grown_capacity : (fn(self : &Self) -> usize)Check if HashMap needs resizing based on load factor
The capacity the next resize targets: DEFAULT_CAPACITY for an
unallocated map, the same capacity when a rehash alone (dropping
tombstones) makes room, and double otherwise.
Returns: usize
_needs_resize : (fn(self : &Self) -> bool)Returns: bool
_resize : (fn(self : &mut Self, new_capacity : usize) -> Result(unit, HashMapError))Resize and rehash the HashMap to a new capacity
Returns: Result(unit, HashMapError)
try_insert : (fn(self : &mut Self, key : K, value : V) -> Result(Option(V), HashMapError))Insert or overwrite, reporting allocation failure instead of panicking:
.Ok(.Some(old)) when the key was present, .Ok(.None) when it is new.
The allocator-aware form (D9); insert is the one to reach for. An
insertion that crosses the load factor rehashes the table first, which
INVALIDATES every entry pointer previously handed out.
Returns: Result(Option(V), HashMapError)
_insert_at : (fn(self : &mut Self, index : usize, hash : u64, sink(key) : K, sink(value) : V) -> usize)Write key/value into index, a slot _probe reported VACANT, and
return the slot the pair landed in — the resize path re-finds it, so the
caller cannot assume it is the index it passed.
Resizes first when the new entry would cross the load factor — and in
that case re-finds the slot, because the rehash moved everything. This is
the half of try_insert that runs after the probe; entry reuses it so
that a miss costs one probe rather than two.
PANICS on allocation failure, like insert (D9). The key and value are
moved in.
Returns: usize
get : (fn(self : &Self, key : &K) -> Option(V))Copy of the value stored under key, or .None — O(1) average.
The value is dup'd for a refcounted V; get_entry_ptr borrows the
entry instead, and self(key) (the Index impl) panics on a missing
key rather than answering .None.
Returns: Option(V)
get_entry_ptr : (fn(self : &mut Self, key : &K) -> Option(*MapEntry(K, V)))Pointer to the LIVE entry for key, or .None when the key is absent.
The pointer aliases the map's own bucket array — the same storage
iter() hands out (D14) — so writing p.*.value updates the map in
place, and any operation that REHASHES the table (an insert that grows
it, remove, clear) invalidates it.
insert : (fn(self : &mut Self, key : K, value : V) -> Option(V))Insert a key/value pair, returning the PREVIOUS value for that key —
Rust's insert.
PANICS on allocation failure (D9): HashMap.new already does, and so
does ArrayList.push. Before D9 this returned a Result that
essentially every caller discarded through a throwaway _x := binding.
Use try_insert when the caller genuinely handles OOM.
The .Some(old) result is a trap worth knowing: map.insert(k, v) .unwrap() used to unwrap a Result and now unwraps the OPTION, so it
panics on a FRESH key.
Returns: Option(V)
get_key_value : (fn(self : &Self, key : &K) -> Option(MapEntry(K, V)))remove_entry : (fn(self : &mut Self, key : &K) -> Option(MapEntry(K, V)))contains_key : (fn(self : &Self, key : &K) -> bool)Whether key is in the map — O(1) average, and it does not touch the
value, so nothing is dup'd for a refcounted V.
Returns: bool
remove : (fn(self : &mut Self, key : &K) -> Option(V))Remove key, returning the value it held, or .None — O(1) average.
The freed bucket goes back to EMPTY when the next bucket is already
EMPTY, and becomes a TOMBSTONE otherwise, because a key inserted later
may have probed past it. Tombstones cost a full bucket compare on every
miss, which is why they are counted and why a table that is mostly
tombstones is rehashed in place (_needs_resize). Entry pointers into
the removed bucket are invalid afterwards.
Returns: Option(V)
_vacate : (fn(self : &mut Self, index : usize) -> unit)Mark the live bucket index free, once its entry has been moved out or
dropped.
Linear probing stops at the first EMPTY slot, so if the NEXT slot is EMPTY no live key's probe chain passes through this one and it can go straight back to EMPTY. Otherwise it must stay a tombstone: a key inserted later may have probed past it.
Returns: unit
len : (fn(self : &Self) -> usize)Number of live entries — O(1). Not the bucket count; that is
capacity.
Returns: usize
is_empty : (fn(self : &Self) -> bool)True when the map holds no entries. A map with only tombstones left is empty by this test.
Returns: bool
retain : (fn(self : &mut Self, keep : &mut Impl(FnMut(k : &K, v : &V) -> bool)) -> unit)Drop every entry for which keep(key, value) is false — Rust's retain.
Scans the bucket array directly rather than probing per key. Removal only rewrites the removed bucket's control byte and never moves another entry, so the scan stays valid across the removals it performs.
Returns: unit
extend : (
fn(
generic(I : Type),
self : &mut Self,
sink(iterable) : I,
where(I <: IntoIterator(Item := MapEntry(K, V)))
) -> unit
)Insert every entry of iterable, overwriting on duplicate keys — Rust's
Extend.
Takes anything that implements IntoIterator over map entries, so a map,
an OrderedMap, a BTreeMap or an ArrayList(MapEntry(K, V)) all work:
defaults.extend(overrides);
The source is moved in, as into_iter consumes it: extend from
src.clone() to keep the source.
An ITERATOR is not accepted, only something that yields one. The prelude's
blanket into_iter on Iterator is a bare METHOD, not an IntoIterator
impl, so an iterator does not satisfy this bound however much its doc
comment says every iterator is its own IntoIterator — see
issues/blanket-into-iter-is-not-an-intoiterator-impl.md. Feed a chain
through collect first.
Returns: unit
clear : (fn(self : &mut Self) -> unit)Drop every entry and reset every control byte to EMPTY, KEEPING the
bucket array — Rust's clear. O(capacity), and it clears the tombstone
count too.
Returns: unit
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash), V <: Clone), HashMap(K, V), ...)
get_cloned : (fn(self : &Self, key : &K) -> Option(V))A clone of the value stored under key, or .None — O(1) average.
{ HashMap } :: import("std/collections/hash_map");
{ String } :: import("std/string");
(mut(m) : HashMap(i32, String)) = HashMap(i32, String).new();
m.insert(i32(1), `one`);
assert(m.get_cloned(&i32(1)) == .Some(`one`), "a clone of the value");
Returns: Option(V)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Clone), V <: Clone), HashMap(K, V), ...)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), ...)
entry : (fn(generic(R : Type), self : &mut Self, key : &K, sink(body) : Impl(FnOnce(e : &mut HashMapEntry(K, V)) -> R), where(K <: Clone)) -> R)The slot for key, resolved in one probe and lent to body — Rust's
entry in a with-shape (decision 22): Yo has no borrow object, so the
entry lives only as the body's parameter and cannot be stored past a
rehash. The body runs exactly once, so it is an FnOnce moved in
(decision 37): it may move what it captured into the map
({ v }(e) => e.or_insert(v)) instead of copying each capture.
counts.entry(word, e => {
e.and_modify(n => (n + i32(1)));
e.or_insert(i32(1));
});
The body must not touch the map through another handle: anything that
rehashes the table moves the key out of the slot the entry pinned. See
HashMapEntry for the full invalidation rule.
The entry holds its own clone of the key (K <: Clone): a vacant insert
moves it into the map, which owns its keys (B8).
Returns: R
_value_at_mut : (fn(self : &mut Self, index : usize) -> &mut V)The stored value at index, a bucket a probe found occupied, as a
&mut place into the map (get_or_insert's and
get_or_insert_with's results).
Returns: &mut V
get_or_insert : (fn(self : &mut Self, key : &K, default : V, where(K <: Clone)) -> &mut(V, self))The value for key as a &mut place into the map, inserting
default first when absent — one probe. The key is cloned only on
the vacant path.
Returns: &mut(V, self)
get_or_insert_with : (fn(self : &mut Self, key : &K, make : &mut Impl(FnMut() -> V), where(K <: Clone)) -> &mut(V, self))The value for key, inserting make()'s result first when absent —
use over get_or_insert when constructing the default is costly.
One probe over _probe/_insert_at, the way
HashMapEntry.or_insert_with spells it.
Returns: &mut(V, self)
update_with : (fn(self : &mut Self, key : &K, f : &mut Impl(FnMut(v : &V) -> V)) -> bool)Update the value for key through f when present; no-op when absent.
Returns true when an update happened. One probe, no entry: a closure
holding f would borrow it exclusively and could not be moved into
entry's by-value body.
Returns: bool
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), Drop(...))
drop : (fn(self : &mut Self) -> unit)Drops every live entry and frees the control and bucket arrays. Runs when the last reference to the map goes away.
Returns: unit
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), IntoIterator(...))
Item : MapEntry(K, V)IntoIter : HashMapIter(K, V)into_iter : (fn(self : Self) -> HashMapIter(K, V))Returns: HashMapIter(K, V)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), ...)
iter : (fn(self : &Self) -> HashMapIterPtr(K, V))Raw walk over the occupied buckets: yields a *(MapEntry(K, V)) into
the map's own bucket array (D14), so nothing is dup'd and p.*.value
can be written in place. into_iter() — what for(map, ...) uses —
consumes the map and yields entries by value instead; safe code reads
entries in place with for(&map, (k, v) => ...).
Order follows the bucket array, so it is arbitrary but reproducible for
a map built with new()'s fixed keys. The iterator holds the bucket
arrays, not the map (decision 39, B7b), so the map must outlive the
walk. Do not insert or remove during it: a rehash invalidates every
pointer already yielded.
Returns: HashMapIterPtr(K, V)
_walk_from : (fn(self : &Self, i : usize) -> usize)The first occupied bucket at or after i, or capacity when there is
none: the borrowed for's cursor step.
Returns: usize
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), ...)
keys : (fn(self : Self) -> HashMapKeys(K, V))Walk the keys, in bucket order — Rust's into_keys. Each key moves out
of the map and each value is dropped.
Consumes the map (lookahead D20): m.clone().keys() walks a map that is
read again later. keys_cloned() lists the keys of a borrowed map,
cloning only the keys.
Returns: HashMapKeys(K, V)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), ...)
values : (fn(self : Self) -> HashMapValues(K, V))Walk the values, in bucket order — Rust's into_values. Each value
moves out of the map and each key is dropped.
Consumes the map (lookahead D20). values_cloned() lists the values of
a borrowed map.
Returns: HashMapValues(K, V)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Clone)), HashMap(K, V), ...)
keys_cloned : (fn(self : &Self) -> ArrayList(K))A clone of every key, in bucket order (the order keys() yields) —
the get_cloned family's walk of a borrowed map. Only the keys are
cloned, so a loop can walk them while it reads and writes the map.
{ HashMap } :: import("std/collections/hash_map");
(mut(m) : HashMap(i32, i32)) = HashMap(i32, i32).new();
m.insert(i32(1), i32(10));
ks := m.keys_cloned();
m.insert(i32(2), i32(20));
assert((ks.len() == usize(1)) && (m.len() == usize(2)), "a snapshot");
Returns: ArrayList(K)
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash), V <: Clone), HashMap(K, V), ...)
values_cloned : (fn(self : &Self) -> ArrayList(V))A clone of every value, in bucket order (the order values() yields)
— the get_cloned family's walk of a borrowed map.
{ HashMap } :: import("std/collections/hash_map");
(mut(m) : HashMap(i32, i32)) = HashMap(i32, i32).new();
m.insert(i32(1), i32(10));
assert(m.values_cloned().len() == usize(1), "one value");
Returns: ArrayList(V)
impl(generic(K : Type, V : Type), HashMap(K, V), Index(K)(...))
Output : Vindex : (fn(self : &Self, idx : K, where(K <: (Eq(K), Hash))) -> &Self.Output)impl(generic(K : Type, V : Type), HashMap(K, V), IndexMut(K)(...))
Output : Vindex_mut : (fn(self : &mut Self, idx : K, where(K <: (Eq(K), Hash))) -> &mut Self.Output)impl(generic(K : Type, V : Type), where(K <: (Clone, Eq(K), Hash), V <: Clone), HashMap(K, V), ...)
clone_in : (fn(self : &Self, a : Allocator) -> Self)A deep copy of the map with both buffers in a, whichever allocator the
source lives in (clone() keeps the copy where the source lives). Keys,
values and the hash keys are cloned; the copy's own entries go wherever
their clone puts them. PANICS on allocation failure.
Returns: Self
_clone_placed : (fn(self : &Self, alloc : Option(Allocator)) -> Self)Returns: Self
impl(generic(K : Type, V : Type), where(K <: (Clone, Eq(K), Hash), V <: Clone), HashMap(K, V), Clone(...))
clone : (fn(self : &Self) -> Self)Create an independent clone of self.
Returns: Self
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), FromIterator(...))
Elem : MapEntry(K, V)from_iter_new : (fn() -> Self)The empty collection collect starts from.
Returns: Self
from_iter_add : (fn(sink(acc) : Self, item : &MapEntry(K, V)) -> Self)Add one element to a partially-built collection and return it.
Parameters
| Name | Type | Notes |
|---|---|---|
item | &MapEntry(K, V) |
Returns: Self
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMap(K, V), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
impl(generic(K : Type, V : Type, p : Origin), where(K <: (Eq(K), Hash)), &(HashMap(K, V), p), IntoIterator(...))
Item : Tuple(&(K, p), &(V, p))IntoIter : HashMapCursor(K, V, p)into_iter : (fn(self : Self) -> HashMapIter(K, V))Returns: HashMapIter(K, V)
impl(generic(K : Type, V : Type, p : Origin), where(K <: (Eq(K), Hash)), &mut(HashMap(K, V), p), IntoIterator(...))
Item : Tuple(&(K, p), &mut(V, p))IntoIter : HashMapCursorMut(K, V, p)into_iter : (fn(self : Self) -> HashMapIter(K, V))Returns: HashMapIter(K, V)
One key's slot in a HashMap, resolved by a SINGLE probe — Rust's Entry.
Yo has no borrow object, so this is a plain struct that pins the map, the
key, its hash, and the bucket the probe landed on. That last field is what
makes the entry worth having over get + insert: the miss path already
knows where to write.
The entry lives only as HashMap.entry's body parameter (decision 22): it
cannot be returned or stored, so it cannot go stale across a rehash the
way a stored one would. Inside the body it is invalidated by anything that
rehashes the table — an insert that grows it, remove, clear —
exactly like the pointer get_entry_ptr hands out; a body that mutates
the map through a captured handle must finish doing so before it uses the
entry again.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMapEntry(K, V), ...)
key : (fn(self : &Self, where(K <: Clone)) -> K)A clone of the key this entry was looked up with.
Returns: K
is_occupied : (fn(self : &Self) -> bool)True when the key is already in the map.
Returns: bool
is_vacant : (fn(self : &Self) -> bool)True when the key is absent.
Returns: bool
value : (fn(self : &Self, where(V <: Clone)) -> Option(V))A clone of the stored value, or .None when the entry is vacant.
Returns: Option(V)
or_insert : (fn(self : &mut Self, default : &V, where(K <: Clone, V <: Clone)) -> V)The value for this key, inserting default first when vacant. The
vacant insert also flips the entry's own slot to .Occupied, so a body
may keep using the entry afterwards (is_occupied, and_modify).
The decision-22 sketch returns &mut V here; a generic impl method
returning a borrow gets pointer-flavored &T parameters that do not
deref, which is invalid C
(issues/2026-10-25-a-borrow-returning-generic-method-breaks-its-own-typed-parameters.md),
so the value comes back as a clone (V <: Clone); the vacant insert
stores a clone of default and of the entry's key.
Returns: V
or_insert_with : (fn(self : &mut Self, make : &mut Impl(FnMut() -> V), where(K <: Clone, V <: Clone)) -> V)The value for this key, inserting make()'s result first when vacant —
use over or_insert when constructing the default is costly. As
or_insert: the slot flips to .Occupied, and the value comes back as
a clone (see the &mut V note there); make()'s result moves in.
Returns: V
and_modify : (fn(self : &Self, f : &mut Impl(FnMut(v : &V) -> V)) -> unit)Replace the stored value with f(value) when occupied; a no-op when
vacant. Returns unit, so it does not chain: write the two steps out
inside the entry body:
counts.entry(word, e => {
e.and_modify(n => (n + i32(1)));
e.or_insert(i32(1));
});
Returns: unit
remove : (fn(self : &mut Self) -> Option(V))Remove this key from the map, returning the value it held.
Re-probes rather than using the pinned slot: removal has to decide
between an empty slot and a tombstone from the chain that follows it, and
that logic lives in remove.
Returns: Option(V)
The outcome of ONE walk of a key's probe sequence — "where does this key live, or where would it go?".
_find_bucket answers only the first half and _find_insert_bucket only
the second, so every get-then-insert accessor walked the sequence TWICE.
_probe answers both at once (hashbrown's find_or_find_insert_slot).
Variants
| Variant | Fields | Description |
|---|---|---|
Occupied | index: usize | The key is present, in this bucket. |
Vacant | index: usize | The key is absent; this is the bucket it would be written to — PROVIDED the table is not resized first, since a rehash moves everything. |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
Methods
clone : (BucketProbe) fn(self : &BucketProbe) -> BucketProbeError variants for HashMap operations.
Variants
| Variant | Fields | Description |
|---|---|---|
AllocError | error: AllocError | Memory allocation failed. |
CapacityOverflow | Capacity calculation overflowed. |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
Methods
clone : (HashMapError) fn(self : &HashMapError) -> HashMapErrorA single key/value entry in a map.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
Value iterator over a HashMap — yields each MapEntry(K, V) BY VALUE.
This is what into_iter(), and therefore for(map, ...), returns;
iter() yields pointers.
It owns the map. When it holds the map's only handle, each entry MOVES
out of its bucket (the bucket is vacated, so dropping the iterator drops
only the entries it has not yielded) and nothing is copied. While
HashMap is still a shared handle (until plans/VALUES_BY_DEFAULT.md's
B9) another handle may share the map; the entries are then copied, so the
other handle keeps them (lookahead D21, the rule ArrayList.extend
follows).
It walks the control-byte array from bucket 0, so the order is arbitrary
but reproducible for a map keyed by new()'s fixed keys.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
Pointer iterator over a HashMap — yields *(MapEntry(K, V)) into the
map's own bucket array. This is what iter() returns (D14).
A raw view (decision 39, B7b): it holds the control and bucket arrays and
the capacity iter() saw, NOT the map, so it keeps nothing alive and is
meant for pragma(Pragma.AllowUnsafe) code. The map must outlive the
walk, and a yielded pointer stays valid only while the table is not
rehashed: an insert that grows the map, a remove or a clear during
the walk leaves it dangling.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
Iterator over a map's keys, in bucket order — what keys() returns. The
iterator owns the map (keys() consumes it), so each key moves out of its
bucket and the bucket's value is dropped: nothing is cloned, and a
move-only key works.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMapKeys(K, V), Iterator(...))
Item : Knext : (fn(self : &mut Self) -> Option(K))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(K)
Iterator over a map's values, in bucket order — what values() returns.
Each value moves out of its bucket, as HashMapKeys moves its keys.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMapValues(K, V), Iterator(...))
Item : Vnext : (fn(self : &mut Self) -> Option(V))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(V)
The shared walk over a HashMap (Rust's hash_map::Iter<'a, K, V>): a &(HashMap(K, V), p) lend and a
position, yielding each entry as (&(K, p), &(V, p)). Binding the cursor
freezes the map for its life (E0911 on a write), which is what makes the
borrowed for(&map, (k, v) => body) lower to the value form over
(&map).into_iter().
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
p | Origin | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(K : Type, V : Type, p : Origin), where(K <: (Eq(K), Hash)), HashMapCursor(K, V, p), Iterator(...))
Item : Tuple(&(K, p), &(V, p))next : (fn(self : &mut Self) -> Option(Tuple(&(K, p), &(V, p))))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(Tuple(&(K, p), &(V, p)))
The write walk over a HashMap (Rust's hash_map::IterMut<'a, K, V>): a &mut(HashMap(K, V), p) lend and a
position, yielding each entry as (&(K, p), &mut(V, p)): the key is read-only
(a written key would break the map's order), the value is writable. The map is
frozen exclusively while the cursor lives.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
p | Origin | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(K : Type, V : Type, p : Origin), where(K <: (Eq(K), Hash)), HashMapCursorMut(K, V, p), Iterator(...))
Item : Tuple(&(K, p), &mut(V, p))next : (fn(self : &mut Self) -> Option(Tuple(&(K, p), &mut(V, p))))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(Tuple(&(K, p), &mut(V, p)))