silk.collections.hash_map.

When to use#

Use HashMap to find a value by a key. The key type must implement silk.collections.hash.HashKey. Use silk.collections.list.List when the order of insertion matters, or when the code finds values by position.

Details#

HashMap.make does not allocate. The first insert allocates eight buckets. HashMap.makeWithCapacity and HashMap.reserve allocate room for a known number of entries in one step. HashMap.clear drops the entries and keeps the buckets for reuse, and HashMap.clearAndFree also releases them. The map rebuilds its table before more than three quarters of the buckets are in use. A bucket stays in use after a removal, until the next rebuild. The rebuild doubles the number of buckets if the entries fill more than half of them. Otherwise it keeps the number and only clears the removed buckets, so a map that inserts and removes forever keeps a bucket count in proportion to its largest length. A failed growth leaves the entries, the length, and the bucket count unchanged.

The same seed and the same operations give the same bucket order on each target. To visit each entry, scan the buckets from 0 to HashMap.bucketCount, test HashMap.occupiedAt, and read HashMap.keyAt and HashMap.valueAt. This order is the bucket order, not the order of insertion.

Gotchas#

Each lookup and removal consumes its probe key. HashMap.get, HashMap.keyAt, and HashMap.valueAt copy, so the key and value types must be Copy. For a value that is not Copy, use HashMap.withMut to change it in place, or HashMap.remove to move it out.

Examples#

Insert, read, and remove one value#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.hash { Hash, Word }
import silk.collections.hash_map { HashMap }
import silk.core.option { Option }

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

Import as HashMap with import silk.collections.hash_map { HashMap }.

Public declarations: 4.

Entry#

pub struct Entry<K, V>

An internal part of the storage of HashMap. User code does not use it.

Implementation Copy for Entry<K, V>#

impl<K: Copy, V: Copy> Copy for Entry<K, V>

Unallocated#

pub struct Unallocated<K, V>

An internal part of the storage of HashMap. User code does not use it.

Table#

pub struct Table<K, V>

An internal part of the storage of HashMap. User code does not use it.

HashMap#

pub struct HashMap<K, V>

A hash map that owns unique keys and their values, with deterministic seeded hashing.

When to use#

Use it to find a value by a key. The key type must implement silk.collections.hash.HashKey. Use silk.collections.list.List when the order of insertion matters, or when the code finds values by position.

Details#

HashMap.make does not allocate. The first insert allocates eight buckets. HashMap.makeWithCapacity and HashMap.reserve allocate room for a known number of entries in one step. HashMap.clear drops the entries and keeps the buckets for reuse, and HashMap.clearAndFree also releases them. The map rebuilds its table before more than three quarters of the buckets are in use. A bucket stays in use after a removal, until the next rebuild. The rebuild doubles the number of buckets if the entries fill more than half of them. Otherwise it keeps the number and only clears the removed buckets, so a map that inserts and removes forever keeps a bucket count in proportion to its largest length. A failed growth leaves the entries, the length, and the bucket count unchanged.

To visit each entry, scan the buckets from 0 to HashMap.bucketCount, test HashMap.occupiedAt, and read HashMap.keyAt and HashMap.valueAt. This order is the bucket order, not the order of insertion. The same seed and the same operations give the same bucket order on each target.

Each key is unique under HashKey.equals. An insert with a key that is already present replaces the value. The map uses one seed for all of its hashes. Dropping the map drops each key and value and then releases the storage.

Gotchas#

Each lookup and removal consumes its probe key. HashMap.get, HashMap.keyAt, and HashMap.valueAt copy, so the key and value types must be Copy. For a value that is not Copy, use HashMap.withMut to change it in place, or HashMap.remove to move it out.

Implementation HashMap<K, V>#

impl<K, V> HashMap<K, V>

Associated function make#

pub fn make(seed: HashSeed) -> HashMap<K, V>

Returns an empty map that uses seed for each hash. This function does not allocate.

Details#

The seed and the sequence of operations decide the bucket order.

Associated function makeWithCapacity#

pub effect fn makeWithCapacity(seed: HashSeed, capacity: usize) -> HashMap<K, V>
  ! OutOfMemoryError
  ? &mut Allocator

Returns an empty map that uses seed for each hash, with buckets for at least capacity entries before the first rebuild.

When to use#

Use makeWithCapacity when the number of entries is known or can be estimated before the inserts, so that the table allocates once instead of growing step by step.

Details#

The length is 0. Inserts of up to capacity entries do not allocate. The bucket count is the smallest of 8, 16, 32, and so on that keeps capacity entries under three quarters of the buckets. A capacity of 0 does not allocate and gives the same map as HashMap.make. The seed and the sequence of operations decide the bucket order.

Errors#

• OutOfMemoryError if the bucket count overflows usize, or the Allocator cannot supply the storage.

Method length#

pub fn length(self: &Self) -> usize

Returns the number of entries in the map.

Method bucketCount#

pub fn bucketCount(self: &Self) -> usize

Returns the number of buckets. Each bucket index from 0 to this value minus 1 is valid for HashMap.occupiedAt.

Method occupiedAt#

pub fn occupiedAt(self: &Self, index: usize) -> bool

Returns true if the bucket at index holds an entry. Returns false for an index out of range.

Method insert#

pub effect<'env> fn insert<K: HashKey + 'env, 'env>(
    self: &mut Self,
    key: K,
    value: V
  ) -> Option<V> ! OutOfMemoryError ? &mut Allocator

Inserts key with value. Returns the old value if the map already held an equal key, or None.

Details#

The map takes ownership of key and value. If an equal key is already present, the length does not change: the map keeps the new key and value, drops the old key, and returns the old value.

Errors#

• OutOfMemoryError if the table must grow and the Allocator cannot supply the storage. The map does not change.

Method contains#

pub fn contains<K: HashKey>(self: &Self, key: K) -> bool

Returns true if the map holds a key equal to key.

Details#

This function consumes key. It does not change the map.

Method indexOf#

pub fn indexOf<K: HashKey>(self: &Self, key: K) -> Option<usize>

Returns the bucket index of the entry with a key equal to key, or None if there is no such entry.

When to use#

Use indexOf to find a key without a copy or a move, for example when the value type is not Copy.

Details#

This function consumes key. It does not change the map.

Method get#

pub fn get<K: HashKey + Copy, V: Copy>(self: &Self, key: K) -> Option<V>

Returns a copy of the value for the key equal to key, or None if there is no such key.

When to use#

Use get when the key and value types are Copy. Use HashMap.withMut or HashMap.remove for a value that is not Copy.

Details#

This function consumes key. It does not change the map.

Method withMut#

pub fn withMut<K: HashKey, F: once fn(&mut V) -> () + Intrinsic.NonParking
  >(self: &mut Self, key: K, use: F) -> bool

Calls use one time with an exclusive borrow of the value for the key equal to key. Returns false and does not call use if there is no such key.

When to use#

Use withMut to change a value in place, such as to increment a counter, when the value type is not Copy.

Details#

This function does not allocate and does not grow the map. It consumes key. The stored key, the length, and the bucket count do not change. use returns (), so it cannot keep the borrow.

Gotchas#

use must be Intrinsic.NonParking. It cannot suspend.

Method remove#

pub fn remove<K: HashKey>(self: &mut Self, key: K) -> Option<V>

Removes the entry with a key equal to key and returns its value. Returns None if there is no such entry.

Details#

The caller owns the returned value. The stored key is dropped. This function consumes key. It does not allocate.

Method keyAt#

pub fn keyAt<K: Copy, V: Copy>(self: &Self, index: usize) -> K

Returns a copy of the key in the bucket at index.

When to use#

Use keyAt with HashMap.occupiedAt to visit each entry in bucket order.

Gotchas#

The key and value types must be Copy. If index is out of range or the bucket is empty, the program traps.

Method valueAt#

pub fn valueAt<K: Copy, V: Copy>(self: &Self, index: usize) -> V

Returns a copy of the value in the bucket at index.

When to use#

Use valueAt with HashMap.occupiedAt to visit each entry in bucket order.

Gotchas#

The key and value types must be Copy. If index is out of range or the bucket is empty, the program traps.

Method reserve#

pub effect fn reserve(self: &mut Self, additional: usize) -> () ! OutOfMemoryError ? &mut Allocator

Makes sure that at least additional more entries fit before the next rebuild.

When to use#

Use reserve before a run of inserts whose count is known, so that the table grows at most once.

Details#

If the buckets already hold additional more entries under three quarters of the bucket count, this function does nothing. Otherwise, it rebuilds the table once, with the smallest bucket count, doubling from the current one or from 8, that holds the length plus additional entries. The rebuild also reclaims the buckets of removed entries. The length does not change. An additional of 0 does nothing.

Errors#

• OutOfMemoryError if the length plus additional overflows usize, the bucket count overflows usize, or the Allocator cannot supply the storage. The map does not change.

Method clear#

pub fn clear(self: &mut Self) -> ()

Drops every entry and sets the length to 0. The bucket count does not change.

When to use#

Use clear to reuse a map, such as one filled again on each pass of a loop: later inserts up to the old size do not allocate. Use HashMap.clearAndFree to also release the storage.

Details#

The buckets of removed entries are reclaimed too. This function does not allocate.

Method clearAndFree#

pub fn clearAndFree(self: &mut Self) -> ()

Drops every entry and releases the storage. The length and the bucket count become 0.

When to use#

Use clearAndFree when the map stays alive but its storage is no longer needed. Use HashMap.clear to keep the buckets for reuse.

Details#

This function does not allocate and does not need an Allocator. The next insert allocates eight buckets again, as on a map from HashMap.make. The seed does not change.

Implementation Drop for HashMap<K, V>#

impl<K, V> Drop for HashMap<K, V>

Operation drop#

fn drop(self: &mut HashMap<K, V>) -> ()

Category: Collections.

Profiles: aarch64-apple-darwin, aarch64-unknown-linux-gnu, aarch64-unknown-linux-gnu-no-libc, x86_64-unknown-linux-gnu, x86_64-unknown-linux-gnu-no-libc, wasm32-unknown-unknown, wasm32-wasip1, wasm32-wasip2.