silk/hash_set

Owned unique elements with deterministic seeded hashing and open-addressed membership lookup.

When to use

Use HashSet when equivalence and fast membership are central and an element has a HashKey witness. Use silk.vector.Vector when order or duplicate values are part of the data.

Details

The set 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 element, and discards those markers. Allocation completes before commit, so failed growth leaves prior membership, length, and bucket count unchanged.

One HashSeed plus the same operation sequence fixes bucket presentation order on every engine. Iterate deterministically by scanning 0..bucketCount, testing occupiedAt, and then calling elementAt. This is bucket order, not insertion order.

Gotchas

Probes are consumed. Inserting an equivalent element keeps the element already stored and drops the arrival; remove instead transfers the stored element to the caller. elementAt copies and therefore requires a Copy element; contains and indexOf can inspect membership for move-only elements without taking them out.

Examples

Insert one unique element and remove it

import silk.allocator { Allocator }

import silk.effect { Effect }

import silk.hash as Hash

import silk.hash_set as HashSet

import silk.option as Option

import silk.u64 as u64

effect fn build() -> i32
! Allocator.OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut set = HashSet.make<Hash.Word>(Hash.seed(17))
  let inserting = HashSet.insert<Hash.Word>(&mut set, Hash.word(42))
    |> Effect.provideMut<Allocator>(&mut allocator)
  let existed = run inserting
  if existed || !HashSet.contains<Hash.Word>(&set, Hash.word(42)) {
    return 0
  }
  let removed = HashSet.remove<Hash.Word>(&mut set, Hash.word(42))
    |> Option.unwrapOr<Hash.Word>(Hash.word(0))
  return u64.toI32(removed.value)
}

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

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

Import as HashSet with import silk.hash_set.

Public declarations: 13.

Member

pub struct Member<T>

Internal hashed element record exposed by the current table representation.

Implementation Copy for silk/hash_set.Member<T>

impl Copy for silk/hash_set.Member<T>

Unseeded

pub struct Unseeded<T>

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

Slots

pub struct Slots<T>

Allocated element and occupancy buffers used by HashSet.

HashSet

pub struct HashSet<T>

Owns one representative of each equivalence class under one hash witness and seed.

Details

An equivalent insertion keeps the representative already stored. The seed and operation sequence determine bucket presentation order, which is not insertion order.

make

pub fn make<T>(seed: HashSeed) -> silk/hash_set.HashSet<T>

Creates an empty set whose every hash is computed under one seed.

Details

An empty set allocates no storage. The seed fixes bucket order for the same operation sequence.

length

pub fn length<T>(self: &silk/hash_set.HashSet<T>) -> usize

Returns the number of elements the set holds.

bucketCount

pub fn bucketCount<T>(self: &silk/hash_set.HashSet<T>) -> usize

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

occupiedAt

pub fn occupiedAt<T>(self: &silk/hash_set.HashSet<T>, index: usize) -> bool

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

Implementation Drop for silk/hash_set.HashSet<T>

impl Drop for silk/hash_set.HashSet<T>

insert

pub effect fn insert<T>(self: &mut silk/hash_set.HashSet<T>, value: T) -> bool ! OutOfMemoryError ? &mut Allocator

Inserts one owned element, reporting whether an equivalent element was already held.

Details

A set never holds two equivalent elements. When one is already held the set is unchanged and the arriving element is released, so the element that survives is the one the set already had.

Fails only with OutOfMemoryError, and only from the growth this insert needed. A failed insert leaves every prior element present, and leaves the length and the bucket count unchanged.

contains

pub fn contains<T>(self: &silk/hash_set.HashSet<T>, value: T) -> bool

Reports whether the set holds an element equivalent to one probe element.

Details

This function consumes the probe element. It does not change the set or move a stored element.

indexOf

pub fn indexOf<T>(self: &silk/hash_set.HashSet<T>, value: T) -> Option<usize>

Returns the bucket holding an element equivalent to one probe element, or an absent value.

Details

This is the membership question a set of move-only elements answers without moving anything. This function consumes the probe element.

remove

pub fn remove<T>(self: &mut silk/hash_set.HashSet<T>, value: T) -> Option<T>

Removes the element equivalent to one probe element and answers with it.

Details

Ownership passes to the caller; the set does not also release it. The probe element is released.

elementAt

pub fn elementAt<T>(self: &silk/hash_set.HashSet<T>, index: usize) -> T

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

Details

Reads a copy out of the set, so it answers for a set whose element type is Copy.

Gotchas

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