silk.collections.hash_set.

When to use#

Use HashSet to test membership fast, or to keep one copy of each value. The element type must implement silk.collections.hash.HashKey. Use silk.collections.list.List when order or duplicate values matter.

Details#

HashSet.make does not allocate. The first insert allocates eight buckets. HashSet.makeWithCapacity and HashSet.reserve allocate room for a known number of elements in one step. HashSet.clear drops the elements and keeps the buckets for reuse, and HashSet.clearAndFree also releases them. The set 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 elements fill more than half of them. Otherwise it keeps the number and only clears the removed buckets, so a set that inserts and removes forever keeps a bucket count in proportion to its largest length. A failed growth leaves the elements, 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 element, scan the buckets from 0 to HashSet.bucketCount, test HashSet.occupiedAt, and read HashSet.elementAt. This order is the bucket order, not the order of insertion.

Gotchas#

Each lookup consumes its probe value. If an equal element is already in the set, an insert keeps the old element and drops the new one. HashSet.elementAt copies, so the element type must be Copy. HashSet.contains and HashSet.indexOf work for elements that are not Copy.

Examples#

Count the different values in a list#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.hash { Hash, Word }
import silk.collections.hash_set { HashSet }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut seen = HashSet<Word>.make(Hash.seed(17))
  let values: [u64; 5] = [3, 1, 3, 2, 1]
  let mut index: usize = 0
  while index < 5 {
    let duplicate = run HashSet<Word>.insert(&mut seen, Hash.word(values[index]))
      |> Effect.provideMut<Allocator>(&mut allocator)
    index = index + 1
  }
  if HashSet<Word>.length(&seen) != 3 {
    return 1
  }
  return 0
}

Import as HashSet with import silk.collections.hash_set { HashSet }.

Public declarations: 4.

Member#

pub struct Member<T>

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

Implementation Copy for Member<T>#

impl<T: Copy> Copy for Member<T>

Unseeded#

pub struct Unseeded<T>

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

Slots#

pub struct Slots<T>

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

HashSet#

pub struct HashSet<T>

A hash set that owns unique elements, with deterministic seeded hashing.

When to use#

Use it to test membership fast, or to keep one copy of each value. The element type must implement silk.collections.hash.HashKey. Use silk.collections.list.List when order or duplicate values matter.

Details#

HashSet.make does not allocate. The first insert allocates eight buckets. HashSet.makeWithCapacity and HashSet.reserve allocate room for a known number of elements in one step. HashSet.clear drops the elements and keeps the buckets for reuse, and HashSet.clearAndFree also releases them. The set 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 elements fill more than half of them. Otherwise it keeps the number and only clears the removed buckets, so a set that inserts and removes forever keeps a bucket count in proportion to its largest length. A failed growth leaves the elements, the length, and the bucket count unchanged.

To visit each element, scan the buckets from 0 to HashSet.bucketCount, test HashSet.occupiedAt, and read HashSet.elementAt. 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 element is unique under HashKey.equals. An insert of an element that is already present keeps the old element. The set uses one seed for all of its hashes. Dropping the set drops each element and then releases the storage.

Gotchas#

Each lookup consumes its probe value. HashSet.elementAt copies, so the element type must be Copy. HashSet.contains and HashSet.indexOf work for elements that are not Copy.

Implementation HashSet<T>#

impl<T> HashSet<T>

Associated function make#

pub fn make(seed: HashSeed) -> HashSet<T>

Returns an empty set 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) -> HashSet<T>
  ! OutOfMemoryError
  ? &mut Allocator

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

When to use#

Use makeWithCapacity when the number of elements 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 elements do not allocate. The bucket count is the smallest of 8, 16, 32, and so on that keeps capacity elements under three quarters of the buckets. A capacity of 0 does not allocate and gives the same set as HashSet.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 elements in the set.

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

Method occupiedAt#

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

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

Method insert#

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

Adds value to the set. Returns true if the set already held an equal element, or false if value is new.

Details#

If an equal element is already present, the set does not change and drops value. The set keeps the element that it already held.

Errors#

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

Method contains#

pub fn contains<T: HashKey>(self: &Self, value: T) -> bool

Returns true if the set holds an element equal to value.

Details#

This function consumes value. It does not change the set.

Method indexOf#

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

Returns the bucket index of the element equal to value, or None if there is no such element.

When to use#

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

Details#

This function consumes value. It does not change the set.

Method remove#

pub fn remove<T: HashKey>(self: &mut Self, value: T) -> Option<T>

Removes the element equal to value and returns the stored element. Returns None if there is no such element.

Details#

The caller owns the returned element. This function consumes value. It does not allocate.

Method elementAt#

pub fn elementAt<T: Copy>(self: &Self, index: usize) -> T

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

When to use#

Use elementAt with HashSet.occupiedAt to visit each element in bucket order.

Gotchas#

The element type 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 elements 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 elements 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 elements. The rebuild also reclaims the buckets of removed elements. 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 set does not change.

Method clear#

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

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

When to use#

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

Details#

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

Method clearAndFree#

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

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

When to use#

Use clearAndFree when the set stays alive but its storage is no longer needed. Use HashSet.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 set from HashSet.make. The seed does not change.

Implementation Drop for HashSet<T>#

impl<T> Drop for HashSet<T>

Operation drop#

fn drop(self: &mut HashSet<T>) -> ()

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.