Module collections/hash_map

Allocate memory for HashMap with given capacity Initializes all control bytes to EMPTY

The bucket hash of key under this map's keys.

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. Unlike Rust's HashMap::new, this ALLOCATES eagerly, and PANICS if that allocation fails.

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.

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. PANICS on allocation failure.

Get ctrl pointer (unwrapped for internal use)

Get data pointer (unwrapped for internal use)

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.

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.

First reusable bucket (EMPTY or DELETED) on hash's LINEAR probe sequence. Panics on a full table — the caller resizes first.

Check if HashMap needs resizing based on load factor

Resize and rehash the HashMap to a new capacity

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.

Write key/value into index, a slot _probe reported VACANT, and return the value written.

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

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.

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

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.

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

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.

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.

Number of live entries — O(1). Not the bucket count; that is capacity.

True when the map holds no entries. A map with only tombstones left is empty by this test.

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.

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

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.

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.

The slot for key, resolved in one probe — Rust's entry.

counts.entry(word).and_modify((n) => (n + i32(1))).or_insert(i32(1));

See HashMapEntry for the invalidation rule.

The value for key, inserting default first when absent.

The value for key, inserting make()'s result first when absent — use over get_or_insert when constructing the default is costly.

Update the value for key through f when present; no-op when absent. Returns true when an update happened.

Drops every live entry and frees the control and bucket arrays. Runs when the last reference to the map goes away.

Borrowing 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 — yields entries by value instead.

Order follows the bucket array, so it is arbitrary but reproducible for a map built with new()'s fixed keys. Do not insert or remove during the walk: a rehash invalidates every pointer already yielded.

Walk the keys, in bucket order — Rust's keys. Yields them by value; iter() is the way to see keys without dup'ing them.

Walk the values, in bucket order — Rust's values. Yields them by value; iter() hands out entry pointers instead, which is the cheaper way to read a refcounted V.

Create an independent clone of self.

Cycle-GC tracing. Buckets live in a malloc'd open-addressing buffer the compiler's auto-derived field walk cannot reach, so trace each FULL slot (its control byte is neither EMPTY nor DELETED). tracer.visit takes the MapEntry(K, V) slot POINTER; the per-value traversal descends inline through the value struct, tracing BOTH the key and the value, WITHOUT touching any reference count (a by-value managed handle would be dup'd then dropped, freeing a live element mid-collection). Mirrors the ArrayList Trace impl + the SwissTable slot scan.

The empty collection collect starts from.

Add one element to a partially-built collection and return it.

The default value of the type.

The key this entry was looked up with.

True when the key is already in the map.

True when the key is absent.

The stored value, or .None when the entry is vacant.

The value for this key, inserting default first when vacant.

The value for this key, inserting make()'s result first when vacant — use over or_insert when constructing the default is costly.

Replace the stored value with f(value) when occupied; a no-op when vacant. Returns the entry, so it chains ahead of or_insert:

counts.entry(word).and_modify((n) => (n + i32(1))).or_insert(i32(1));

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.

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

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

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

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