Module collections/hash_map

collections/hash_map
Stability: unstable — may still change; see below.

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

HashMap type-function
fn(K : Type, V : Type) -> Type

High-performance hash map using SwissTable algorithm. Keys must implement Eq and Hash. Provides O(1) average lookup, insert, and delete.

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
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

_alloc_of : (fn(self : &Self) -> Option(Allocator))

Returns: Option(Allocator)

_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))

The allocator the map's buffers live in: the one given to new / with_capacity as alloc : .Some(a), or .None for a map on the global allocator.

Returns: 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.

Returns: Option(*MapEntry(K, V))

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)))

The stored KEY alongside its value — Rust's get_key_value.

Distinct from get whenever the key type has equal-but-distinguishable values (a case-insensitive string key, say): this returns the key the map actually holds, not the one used to look it up.

Returns: Option(MapEntry(K, V))

remove_entry : (fn(self : &mut Self, key : &K) -> Option(MapEntry(K, V)))

Remove key and return the entry that was stored — Rust's remove_entry.

The entry moves out of its bucket, so nothing is copied: a move-only key or value works.

Returns: 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), ...)
get_key_value_cloned : (fn(self : &Self, key : &K) -> Option(MapEntry(K, V)))

A clone of the stored key and value — get_key_value for a key or value that is not copied implicitly.

Returns: Option(MapEntry(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 : V
index : (fn(self : &Self, idx : K, where(K <: (Eq(K), Hash))) -> &Self.Output)

Parameters

NameTypeNotes
idxK

Returns: &Self.Output

impl(generic(K : Type, V : Type), HashMap(K, V), IndexMut(K)(...))
Output : V
index_mut : (fn(self : &mut Self, idx : K, where(K <: (Eq(K), Hash))) -> &mut Self.Output)

Parameters

NameTypeNotes
idxK

Returns: &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

NameTypeNotes
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)

HashMapEntry type-function
fn(K : Type, V : Type) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
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)

BucketProbe

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

VariantFieldsDescription
Occupiedindex: usize

The key is present, in this bucket.

Vacantindex: 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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

Methods
clone : (BucketProbe) fn(self : &BucketProbe) -> BucketProbe

Parameters

NameTypeNotes
selfBucketProbe

Returns: BucketProbe

HashMapError

Error variants for HashMap operations.

Variants

VariantFieldsDescription
AllocErrorerror: 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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

Methods
clone : (HashMapError) fn(self : &HashMapError) -> HashMapError

Parameters

NameTypeNotes
selfHashMapError

Returns: HashMapError

MapEntry type-function
fn(K : Type, V : Type) -> Type

A single key/value entry in a map.

Type Parameters

NameTypeNotes
KTypecomptime
VTypecomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

HashMapIter type-function
fn(K : Type, V : Type) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMapIter(K, V), Iterator(...))
Item : MapEntry(K, V)
next : (fn(self : &mut Self) -> Option(MapEntry(K, V)))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(MapEntry(K, V))

HashMapIterPtr type-function
fn(K : Type, V : Type) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMapIterPtr(K, V), Iterator(...))
Item : *MapEntry(K, V)
next : (fn(self : &mut Self) -> Option(*MapEntry(K, V)))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(*MapEntry(K, V))

HashMapKeys type-function
fn(K : Type, V : Type) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMapKeys(K, V), Iterator(...))
Item : K
next : (fn(self : &mut Self) -> Option(K))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(K)

HashMapValues type-function
fn(K : Type, V : Type) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash)), HashMapValues(K, V), Iterator(...))
Item : V
next : (fn(self : &mut Self) -> Option(V))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(V)

HashMapCursor type-function
fn(K : Type, V : Type, p : Origin) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime
pOrigincomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
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)))

HashMapCursorMut type-function
fn(K : Type, V : Type, p : Origin) -> Type

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

NameTypeNotes
KTypecomptime
VTypecomptime
pOrigincomptime

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)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
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)))