hashmap

import std::collections::hashmap; · source

HashMap<K, V, A>#

type struct HashMap<K, V, A = GlobalAlloc> {
    buckets:      Entry<K, V>**;
    bucket_count: u64;
    length:       u64;
    alloc:        A;
    seed:         u64;

    static new() -> HashMap<K, V, GlobalAlloc>;
    static new_in(alloc: A) -> HashMap<K, V, A>;
    static with_seed(seed: u64) -> HashMap<K, V, GlobalAlloc>;
    static with_seed_in(seed: u64, alloc: A) -> HashMap<K, V, A>;
    static with_capacity(capacity: u64) -> HashMap<K, V, GlobalAlloc>;
    length(&this) -> u64;
    is_empty(&this) -> boolean;
    bucket_count(&this) -> u64;
    get_bucket(&this, index: u64) -> Entry<K, V>*;
    iter(&this) -> implement Iterator<Pair<K, V>>
    where K: Copy, V: Copy;
    keys(&this) -> implement Iterator<K>
    where K: Copy;
    values(&this) -> implement Iterator<V>
    where V: Copy;
    entries(&this) -> implement Iterator<Pair<K*, V*>>;
    keys_ref(&this) -> implement Iterator<K*>;
    values_ref(&this) -> implement Iterator<V*>;
    contains_key(&this, key: &K) -> boolean
    where K: Hash + Eq;
    get(&this, key: &K) -> Option<V>
    where K: Hash + Eq, V: Copy;
    get_ref(&this, key: &K) -> Option<V*>
    where K: Hash + Eq;
    insert(mut &this, key: K, value: V) -> Option<V>
    where K: Hash + Eq;
    try_insert(mut &this, key: K, value: V) -> Result<Option<V>, AllocError>
    where K: Hash + Eq;
    get_or_insert(mut &this, key: K, default: V) -> V*
    where K: Hash + Eq;
    try_get_or_insert(mut &this, key: K, default: V) -> Result<V*, AllocError>
    where K: Hash + Eq;
    remove(mut &this, key: &K) -> Option<V>
    where K: Hash + Eq + Drop;
    clear(mut &this) -> void
    where K: Drop, V: Drop;
    resize_buckets(mut &this, new_count: u64) -> Result<(), AllocError>;
}

Separate chaining over a bucket array: each bucket holds a linked list of Entry nodes. Keys must implement Hash + Eq; the bound sits on each method rather than the type, so a map of un-hashable keys is spellable but unusable.

import std::collections::hashmap;

mut counts: HashMap<Str, u64> = HashMap<Str, u64>::new();
mut slot: u64* = counts.get_or_insert(word, 0);
*slot = *slot + 1;

Method	Returns	Notes
insert(key, value)	Option<V> — the replaced value	try_insert is the fallible form.
get(key) (where V: Copy)	Option<V>
get_ref(key)	Option<V*>	Sound for owning values.
get_or_insert(key, default)	V*	try_get_or_insert is the fallible form.
remove(key)	Option<V>	The key is dropped; the value is returned.
contains_key(key)	boolean
clear()		Drops every key and value. Keeps the bucket array.
with_capacity(n)		Sizes the bucket array to the smallest power of two that keeps the load factor below 1.0 for n entries.
bucket_count()	u64	Buckets allocated, not capacity — chaining means a bucket holds many entries.
get_bucket(index)	Entry<K, V>*	Head of a chain, for manual traversal. Null when empty or out of range.

Entry<K, V>#

type struct Entry<K, V> {
    hash:  u64;
    key:   K;
    value: V;
    next:  Entry<K, V>*;
}

One node of a bucket's chain. get_bucket hands back the head of a chain as an Entry*, and next walks it; the cached hash is what lets a resize redistribute entries without re-hashing the keys. You only touch it for manual traversal.

Iterating#

iter(), keys(), and values() yield by value and carry Copy bounds. entries(), keys_ref(), and values_ref() yield Pair<K*, V*>, K*, and V* respectively, and are sound for any key and value type — so they are what you want for a HashMap<String, Foo>. Order is bucket-major and unstable across resizes; every borrow is invalidated by any insert, remove, or resize.

Hash seeding#

The hasher is FNV-1a, seeded per map from a per-process random value drawn from the kernel CSPRNG. Bucket placement therefore varies between runs, so adversarial keys cannot be precomputed to flood a single bucket. FNV-1a is not collision-resistant, so treat this as hardening rather than a cryptographic guarantee — supply a custom hasher where it matters.

with_seed(seed) and with_seed_in(seed, alloc) fix the seed for tests that need reproducible layout or iteration order. Production code should use new.

Chaining was chosen over open addressing because it sidesteps storing uninitialized key/value slots. The cost is one heap allocation per entry.

Trait implementations#

implement<K, V, A> trait Drop for struct HashMap<K, V, A>
where K: Drop, V: Drop, A: Allocator

implement<K, V> trait Clone for struct HashMap<K, V, GlobalAlloc>
where K: Hash + Eq + Clone, V: Clone

implement<K, V> trait Default for struct HashMap<K, V, GlobalAlloc>

implement<K, V, A> trait Display for struct HashMap<K, V, A>
where K: Display, V: Display, A: Allocator   // std::fmt::display

implement<K, V, A> trait Debug for struct HashMap<K, V, A>
where K: Debug, V: Debug, A: Allocator   // std::fmt::display

Clone re-inserts every entry into a fresh map, so the clone's bucket layout may differ. Default is a fresh empty map that allocates no buckets until the first insert. Display renders {k: v, ...}.