silk/hash_map

Owned key-value storage with deterministic seeded hashing and open-addressed lookup.

When to use

Use HashMap for key-based lookup when a key has a HashKey witness. Use silk.vector.Vector when presentation order should follow insertion, or when indexing rather than equivalence is the primary operation.

Details

The map starts allocation-free, first allocates eight buckets, and grows before used buckets exceed three quarters of the table. Linear probing crosses removal markers; growth doubles the table, moves every live entry, and discards those markers. Allocation completes before the map commits, so failed growth leaves existing entries, length, and bucket count unchanged.

One HashSeed plus the same operation sequence fixes bucket presentation order across the evaluator, native code, and WebAssembly. Iterate deterministically by scanning 0..bucketCount, testing occupiedAt, then reading keyAt and valueAt. This is bucket order, not insertion order.

Gotchas

Lookup and removal consume the probe key. get, keyAt, and valueAt copy a complete stored entry and therefore require both stored key and value to be Copy; use withMut to update a move-only value in place or remove to transfer it out. Equivalent keys must also obey the HashKey hash contract.

Examples

Insert, read, and remove one value

import silk.allocator { Allocator }

import silk.effect { Effect }

import silk.hash as Hash

import silk.hash_map as HashMap

import silk.option as Option

effect fn build() -> i32
! Allocator.OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut map = HashMap.make<Hash.Word, i32>(Hash.seed(17))
  let inserting = HashMap.insert<Hash.Word, i32>(&mut map, Hash.word(7), 42)
    |> Effect.provideMut<Allocator>(&mut allocator)
  let previous = run inserting
  drop previous
  let found = HashMap.get<Hash.Word, i32>(&map, Hash.word(7))
    |> Option.unwrapOr<i32>(0)
  let removed = HashMap.remove<Hash.Word, i32>(&mut map, Hash.word(7))
  drop removed
  if HashMap.contains<Hash.Word, i32>(&map, Hash.word(7)) {
    return 0
  }
  return found
}

effect fn recover(error: Allocator.OutOfMemoryError) -> i32 {
  return 0
}

pub fn main() -> i32 {
  return run Effect.catchAll(build(), recover)
}

Import as HashMap with import silk.hash_map.

Public declarations: 16.

Entry

pub struct Entry<K, V>

Internal key-value record exposed by the current table representation.

Implementation Copy for silk/hash_map.Entry<K, V>

impl Copy for silk/hash_map.Entry<K, V>

Unallocated

pub struct Unallocated<K, V>

Allocation-free storage state used before the map creates its first table.

Table

pub struct Table<K, V>

Allocated entry and occupancy buffers used by HashMap.

HashMap

pub struct HashMap<K, V>

Owns unique keys and their values under one equivalence, hash witness, and seed.

Details

An equivalent insertion replaces the stored value instead of adding another entry. The seed and operation sequence determine bucket presentation order, which is not insertion order.

make

pub fn make<K, V>(seed: HashSeed) -> silk/hash_map.HashMap<K, V>

Constructs an empty map whose every hash is computed under one seed.

Details

An empty map allocates nothing. The seed fixes the order the map will present its entries in, and is the only thing besides the sequence of operations that decides it.

length

pub fn length<K, V>(self: &silk/hash_map.HashMap<K, V>) -> usize

Returns the number of entries the map holds.

bucketCount

pub fn bucketCount<K, V>(self: &silk/hash_map.HashMap<K, V>) -> usize

Returns the number of buckets the map presents, which is the range occupiedAt accepts.

occupiedAt

pub fn occupiedAt<K, V>(self: &silk/hash_map.HashMap<K, V>, index: usize) -> bool

Reports whether one bucket holds an entry. Out-of-range buckets hold nothing.

Implementation Drop for silk/hash_map.HashMap<K, V>

impl Drop for silk/hash_map.HashMap<K, V>

insert

pub effect fn insert<K, V>(self: &mut silk/hash_map.HashMap<K, V>, key: K, value: V) -> Option<V> ! OutOfMemoryError ? &mut Allocator

Inserts one owned key and value, answering with the value an equivalent key already held.

Details

The map takes ownership of both. When an equivalent key is already present the map's length does not change, the replaced value travels to the caller, and the key the map held is released.

Fails only with OutOfMemoryError, and only from the growth this insert needed. A failed insert leaves every prior entry at its own key, and leaves the length and the bucket count unchanged.

contains

pub fn contains<K, V>(self: &silk/hash_map.HashMap<K, V>, key: K) -> bool

Reports whether the map holds an entry under a key equivalent to one probe key.

Details

This function consumes the probe key. It does not change the map or move a stored entry.

indexOf

pub fn indexOf<K, V>(self: &silk/hash_map.HashMap<K, V>, key: K) -> Option<usize>

Returns the bucket holding an entry under a key equivalent to one probe key, or an absent value.

Details

This is the lookup a map with move-only values answers: the bucket names the entry without moving anything out of the map. A move-only value can then be transferred with remove. This function consumes the probe key.

get

pub fn get<K, V>(self: &silk/hash_map.HashMap<K, V>, key: K) -> Option<V>

Returns the value held under a key equivalent to one probe key, or an absent value.

Details

Reads a complete entry copy, so it answers only when both stored key and value types are Copy. Use indexOf for a non-moving presence check and remove to transfer a move-only value. This function consumes the probe key and does not change the map.

withMut

pub fn withMut<K, V, F>(self: &mut silk/hash_map.HashMap<K, V>, key: K, use: F) -> bool

Runs one take-once callback with exclusive access to an existing value.

Details

Lookup and mutation allocate nothing and never grow the map. Returns true after running the callback exactly once for an equivalent key, or false without running it when the key is absent. The unit callback cannot return its value borrow, and a callback that may park is rejected.

This function consumes the probe key but leaves the stored key, length, used count, and bucket count unchanged.

remove

pub fn remove<K, V>(self: &mut silk/hash_map.HashMap<K, V>, key: K) -> Option<V>

Removes the entry under a key equivalent to one probe key and answers with its value.

Details

Ownership of the value passes to the caller; the map does not also release it. The key the map held is released, and the probe key is released as well.

keyAt

pub fn keyAt<K, V>(self: &silk/hash_map.HashMap<K, V>, index: usize) -> K

Returns the key held in one bucket. Traps on a bucket that holds no entry.

Details

Reads a complete entry copy, so both stored key and value types must be Copy.

Gotchas

If index is out of range or occupiedAt returns false, the program traps.

valueAt

pub fn valueAt<K, V>(self: &silk/hash_map.HashMap<K, V>, index: usize) -> V

Returns the value held in one bucket. Traps on a bucket that holds no entry.

Details

Reads a complete entry copy, so both stored key and value types must be Copy.

Gotchas

If index is out of range or occupiedAt returns false, the program traps.