HashMap

Module std.collections

import std.collections;

Public declaration contracts and authored examples. A page can document several related symbols. Implementation bodies are excluded.

pub final class HashMap<K, V, P = HashPolicy<K>, A = DefaultAllocator>
    where K: Movable where V: Movable
    where P: HashKeyPolicy<K>, Movable
    where A: Allocator, Defaultable, Movable

Owns an allocator-aware, bounded linear-probed key/value table.

Keys are never exposed writable while stored. Lookup is expected O(1) with suitable hashes and O(capacity) in the worst case. Maximum live load is 3/4; tombstones preserve probe chains and are compacted by fallible growth paths. Structural mutation, move or destruction invalidates all borrowed views. External synchronization is required. Allocation failure preserves logical contents and returns both uninserted inputs; lifecycle/policy traps have no rollback. Moved-from policy reuse follows the policy's own invocation contract. K: Movable owned key type. V: Movable owned value type. P: Movable safe readonly HashKeyPolicy, defaulting to stored functions. A: Movable Defaultable allocator owner.

Example

module example.hash_map;
from std.collections import HashMap, HashPolicy, HashMapEntry;
fn Hash(Key: readonly u64&) -> u64 { return Key; }
fn Equals(Left: readonly u64&, Right: readonly u64&) -> bool { return Left == Right; }
fn Main() -> i32 {
    var Values = HashMap<u64, i32>(HashPolicy<u64>(Hash, Equals));
    if Values.TryReserve(4) is .Err { Error = _ } { return 1; }
    switch Values.TryInsert(7, 20) {
        case .Ok { Value = Previous } => { if Previous is .Some { Value = _ } { return 2; } }
        case .Err { Error = _ } => return 3;
    }
    {
        // Retain writable wrapper storage through the selected payload move.
        var Replacement = Values.TryInsert(7, 42);
        switch Replacement {
            case .Ok { Value = Previous: mut HashMapEntry<u64, i32>?& } => {
                if (Previous is .None) { return 4; }
                var Entry = move(Previous).Unwrap();
                if Entry.Key != 7 || Entry.Value != 20 { return 5; }
            }
            case .Err { Error = _ } => return 6;
        }
    }
    {
        let Readonly: readonly HashMap<u64, i32>& = Values;
        if !Readonly.ContainsKey(7) || Readonly.Find(7).Unwrap() != 42 { return 7; }
    }
    {
        let Found = Values.Find(7);
        if (Found is .None) { return 8; }
        Found.Unwrap() += 1;
    }
    var Removed = Values.Remove(7);
    if (Removed is .None) { return 9; }
    var RemovedEntry = move(Removed).Unwrap();
    if RemovedEntry.Key != 7 || RemovedEntry.Value != 43 { return 9; }
    if !Values.IsEmpty || Values.ContainsKey(7) { return 10; }
    if Values.TryCompact() is .Err { Error = _ } { return 11; }
    if Values.TryShrinkToFit() is .Err { Error = _ } { return 12; }
    var Moved = move(Values);
    Values = move(Moved);
    Values.Clear();
    return 0;
}

HashMap.init

pub init(mut Policy: P)

Creates an allocation-free table with an owned key policy. Policy: Concrete safe hash/equality policy transferred into the result.

HashMap.init

pub init(mut Policy: P, mut AllocatorValue: A)

Creates an allocation-free table with policy and allocator owners. Policy: Concrete safe key policy transferred into the result. AllocatorValue: Allocator transferred into the result.

HashMap.init

pub init(Source: readonly Self&) = delete;

Rejects copying table ownership. Source: Noncopy owner.

HashMap.init

pub init(Source: mut Self&&)

Transfers both allocations, policy and allocator to a new owner. Source: Writable owner left empty and destructible.

HashMap.operator

pub fn operator =(Source: readonly Self&) -> void = delete;

Rejects copying into live ownership. Source: Noncopy owner. Return: No value; deleted.

HashMap.operator

pub fn operator =(Source: mut Self&&) -> void

Releases previous ownership and transfers both allocations and policies. Source: Writable owner left empty; exact self-assignment is unchanged. Return: No value; old entries are destroyed before allocator replacement.

HashMap.Length

pub Length: usize;

Observes occupied entry count in O(1).

HashMap.Capacity

pub Capacity: usize;

Observes raw bucket count in O(1).

HashMap.IsEmpty

pub IsEmpty: bool;

Observes logical emptiness in O(1).

HashMap.TryInsert

pub fn TryInsert(mut Key: K, mut Value: V)
        -> Result<HashMapEntry<K, V>?, HashMapInsertionError<K, V>>

Inserts owned inputs or replaces an equivalent key/value pair. Key: Owned key adopted on success and returned in the error on failure. Value: Owned value adopted on success and returned in the error on failure. Return: Ok(none) for insertion, Ok(Some(old owned pair)) for replacement, or allocation failure owning both unchanged inputs. Warning: May allocate/rehash; invalidates views. Replacement adopts the new equivalent key.

HashMap.Find

pub readonly fn Find(Key: readonly K&) -> V&?

Searches for a value and borrows it readonly. Key: Readonly lookup key, retained only during the call. Return: Optional readonly value reference, invalidated by structural mutation.

HashMap.Find

pub fn Find(Key: readonly K&) -> mut V&?

Searches for a value and borrows it writable without exposing the key. Key: Readonly lookup key, retained only during the call. Return: Optional writable value reference, invalidated by structural mutation.

HashMap.ContainsKey

pub readonly fn ContainsKey(Key: readonly K&) -> bool

Searches for an equivalent stored key without allocating. Key: Readonly lookup key, not retained. Return: Whether an equivalent key is present; expected O(1), worst O(capacity).

HashMap.Remove

pub fn Remove(Key: readonly K&) -> HashMapEntry<K, V>?

Transfers and removes one owned entry without allocating. Key: Readonly lookup key, not retained. Return: Optional owned pair, or none if no equivalent key exists. Warning: Invalidates borrowed views; leaves a reusable probe-chain tombstone.

HashMap.TryReserve

pub fn TryReserve(MinimumEntries: usize) -> Result<void, AllocationError>

Reserves enough buckets for a total logical entry count. MinimumEntries: Minimum desired total live entry capacity at the selected load limit. Return: Ok or AllocationError; failure preserves contents. Warning: May allocate/rehash O(capacity) storage; tombstone cleanup can allocate on later insertion.

HashMap.TryCompact

pub fn TryCompact() -> Result<void, AllocationError>

Rebuilds existing capacity to remove tombstones. Return: Ok or AllocationError; failure preserves logical contents. Warning: May allocate/rehash O(capacity) storage; success invalidates views.

HashMap.TryShrinkToFit

pub fn TryShrinkToFit() -> Result<void, AllocationError>

Shrinks bucket storage to the smallest selected load-compatible capacity. Return: Ok or AllocationError; failure preserves contents. Warning: May allocate/rehash; success invalidates views.

HashMap.Clear

pub fn Clear() -> void

Destroys all live entries and clears probe state, retaining capacity. Return: No value; O(capacity) cleanup without allocation; invalidates all views.

HashMap.CreateIterator

pub readonly fn CreateIterator() -> HashMapIterator<K, V>

Borrows a readonly cursor in unspecified bucket order. Return: Allocation-free entry cursor; full traversal costs O(capacity). Warning: Structural mutation/move/destruction invalidates every cursor/view.

Example

module example.hash_map_iteration;
from std.collections import HashMap, HashPolicy;
fn Hash(Key: readonly u64&) -> u64 { return Key; }
fn Equals(Left: readonly u64&, Right: readonly u64&) -> bool { return Left == Right; }
fn Main() -> i32 {
    var Values = HashMap<u64, i32>(HashPolicy<u64>(Hash, Equals));
    if Values.TryInsert(1, 19) is .Err { Error = _ } { return 1; }
    if Values.TryInsert(2, 20) is .Err { Error = _ } { return 2; }
    {
        var WritableCursor = Values.CreateIterator();
        while WritableCursor.Next() is .Some { Value = Entry } { Entry.Value += 1; }
    }
    {
        var ExplicitWritableCursor = Values.CreateWritableIterator();
        while ExplicitWritableCursor.Next() is .Some { Value = Entry } {
            if Entry.Key == 1 { Entry.Value = 21; }
        }
    }
    let Readonly: readonly HashMap<u64, i32>& = Values;
    var ReadonlyCursor = Readonly.CreateIterator();
    var Sum: i32 = 0;
    while ReadonlyCursor.Next() is .Some { Value = Entry } { Sum += Entry.Value; }
    return Sum - 42;
}

HashMap.CreateIterator

pub fn CreateIterator() -> WritableHashMapIterator<K, V>

Borrows a writable-value cursor while keeping keys readonly. Return: Allocation-free entry cursor in unspecified bucket order. Warning: Structural mutation/move/destruction invalidates every cursor/view.

HashMap.CreateWritableIterator

pub fn CreateWritableIterator() -> WritableHashMapIterator<K, V>

Explicitly borrows writable values with readonly keys. Return: Allocation-free entry cursor in unspecified bucket order. Warning: Structural mutation/move/destruction invalidates every cursor/view.