Home › collections/hash_set

Module collections/hash_set

collections/hash_set
Stability: unstable — may still change; see below.

Hash set — a thin set-shaped view over HashMap(T, unit) (D16).

Before D16 this file carried its OWN copy of the SwissTable: the control bytes, the linear probe, the tombstone accounting, the resize. 525 of its lines were byte-identical to hash_map.yo, which meant every fix had to be made twice — the tombstone-reclamation fix genuinely was (issues/fixed/hash-tombstones-are-never-reclaimed.md).

unit is a true ZST as of v0.2.26, so MapEntry(T, unit) costs exactly what a bare T costs and the map's value slot is free.

Example

{ HashSet } :: import("std/collections/hash_set");

s := HashSet(i32).new();
s.insert(i32(1));
s.contains(i32(1)); // true

Stability

unstable — D16 has only just re-based this module on HashMap(T, unit), and it inherits that map's open item: the backing table's ctrl, data, capacity and size are still public fields there (plans/archive/STD_API_STABILIZATION.md §4). Two shapes of this file's own are also unsettled: the four set operations return Result(Self, HashSetError) while insert panics on the same allocation failure — D9 draws that line the other way round — and Rust returns lazy ITERATORS from union/intersection/difference rather than owned sets. Freezing follows those two decisions.

Types

HashSet type-function
fn(T : Type) -> Type

High-performance hash set, backed by HashMap(T, unit) (D16). Elements must implement Eq and Hash. O(1) average lookup and insert.

Type Parameters

NameTypeNotes
TTypecomptime

Trait Implementations

IntoIterator BorrowedWalk Default FromIterator
impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSet(T), ...)
new : (fn() -> Self)

Create an empty set.

Returns: Self

with_keys : (fn(k0 : u64, k1 : u64) -> Self)

Create an empty set with per-set SipHash keys.

Returns: Self

with_capacity : (fn(requested_capacity : usize) -> Self)

Create an empty set sized for at least requested_capacity elements.

Returns: Self

from : (fn(generic(N : usize), sink(elems) : Array(T, N)) -> Self)

Consuming constructor from a fixed-size array — Rust's HashSet::from([T; N]): HashSet(i32).from([i32(1), i32(2), i32(3)]).

The array is taken by sink, so the caller's binding ends at the call, and every element moves into the set: nothing is copied. Equal elements collapse, as with insert.

Returns: Self

new_in : (fn(alloc : Allocator) -> Self)

Empty set whose table lives in alloc (see HashMap.new_in).

Returns: Self

with_capacity_in : (fn(alloc : Allocator, requested_capacity : usize) -> Self)

with_capacity with the table in alloc.

Returns: Self

allocator : (fn(self : &Self) -> Option(Allocator))

The allocator the set's table lives in, or .None for the global one.

Returns: Option(Allocator)

try_insert : (fn(self : &mut Self, element : T) -> Result(bool, HashSetError))

Insert an element, reporting allocation failure.

The allocator-aware form (D9); insert is the one to reach for. .Ok(true) when the element was NOT already present.

Returns: Result(bool, HashSetError)

insert : (fn(self : &mut Self, element : T) -> bool)

Insert an element, returning true when it was NOT already present.

PANICS on allocation failure (D9); try_insert is the allocator-aware form.

Returns: bool

contains : (fn(self : &Self, element : &T) -> bool)

True when element is in the set.

Returns: bool

remove : (fn(self : &mut Self, element : &T) -> bool)

Remove element. Returns true when it WAS present.

Returns: bool

len : (fn(self : &Self) -> usize)

Number of elements.

Returns: usize

capacity : (fn(self : &Self) -> usize)

Slots currently allocated in the backing table.

A METHOD, not a public field: before D16 capacity was a bare struct field, which D2 flags as a naming violation.

Returns: usize

k0 : (fn(self : &Self) -> u64)

The backing table's SipHash keys — the set's twin of HashMap's public k0 / k1 fields (the key-survival tests assert the delegation is real).

Returns: u64

k1 : (fn(self : &Self) -> u64)

Returns: u64

tombstones : (fn(self : &Self) -> usize)

Tombstoned slots in the backing table — a read-only diagnostic, the set's twin of HashMap's public tombstones field (the reclamation tests assert the load invariant through it).

Returns: usize

is_empty : (fn(self : &Self) -> bool)

True when the set holds no elements.

Returns: bool

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

Remove every element, keeping the allocation.

Returns: unit

is_subset : (fn(self : &Self, other : &Self) -> bool)

True when every element of self is also in other — Rust's is_subset. O(len(self)) lookups, and a set larger than other is rejected without probing anything.

Returns: bool

is_superset : (fn(self : &Self, other : &Self) -> bool)

True when self contains every element of other — Rust's is_superset. Exactly other.is_subset(self), so the cost is O(len(other)).

Returns: bool

is_disjoint : (fn(self : &Self, other : &Self) -> bool)

True when the two sets share no element — Rust's is_disjoint.

Walks the SMALLER set and probes the larger, so the cost is O(min(len(self), len(other))) whichever way round it is called.

Returns: bool

union : (fn(self : &Self, other : &Self) -> Result(Self, HashSetError))

Every element of either set.

Returns: Result(Self, HashSetError)

intersection : (fn(self : &Self, other : &Self) -> Result(Self, HashSetError))

Elements present in BOTH sets.

Returns: Result(Self, HashSetError)

difference : (fn(self : &Self, other : &Self) -> Result(Self, HashSetError))

Elements in self that are NOT in other.

Returns: Result(Self, HashSetError)

symmetric_difference : (fn(self : &Self, other : &Self) -> Result(Self, HashSetError))

Elements in exactly one of the two sets.

Returns: Result(Self, HashSetError)

impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSet(T), IntoIterator(...))
Item : T
IntoIter : HashSetIter(T)
into_iter : (fn(self : Self) -> HashSetIter(T))

Returns: HashSetIter(T)

impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSet(T), ...)
iter : (fn(self : &Self) -> HashSetIterPtr(T))

Non-consuming raw iteration, yielding a *(T) into the backing storage — the pragma(Pragma.AllowUnsafe) form; safe code reads elements with for(&set, x => ...).

Returns: HashSetIterPtr(T)

impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSet(T), BorrowedWalk(...))
WalkCursor : usize
WalkElem : T
walk_start : (fn(self : &Self) -> usize)

The first position (equal to the end for an empty collection).

Returns: usize

walk_valid : (fn(self : &Self, cur : &usize) -> bool)

Whether cur names an element.

Parameters

NameTypeNotes
cur&usize

Returns: bool

walk_ref : (fn(self : &Self, cur : &usize) -> &T)

The element at cur, read in place (a read projection). Panics if cur names no element.

Parameters

NameTypeNotes
cur&usize

Returns: &T

walk_next : (fn(self : &Self, cur : &usize) -> usize)

The position after cur.

Parameters

NameTypeNotes
cur&usize

Returns: usize

impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSet(T), Default(...))
default : (fn() -> Self)

The default value of the type.

Returns: Self

impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSet(T), FromIterator(...))
Elem : T
from_iter_new : (fn() -> Self)

The empty collection collect starts from.

Returns: Self

from_iter_add : (fn(sink(acc) : Self, item : &T) -> Self)

Add one element to a partially-built collection and return it.

Parameters

NameTypeNotes
item&T

Returns: Self

HashSetError enum
HashSetError

Error variants for HashSet operations.

Kept as its own type rather than aliased to HashMapError so a caller matching on it does not silently start seeing map-shaped errors.

Variants

VariantFieldsDescription
AllocErrorerror: AllocError

Memory allocation failed.

CapacityOverflow

Capacity calculation overflowed.

Methods
clone : (HashSetError) fn(self : &HashSetError) -> HashSetError

Parameters

NameTypeNotes
selfHashSetError

Returns: HashSetError

HashSetIter type-function
fn(T : Type) -> Type

Value iterator over a HashSet — yields elements BY VALUE (dup'ing a refcounted T), in the backing map's bucket order. This is what into_iter(), and therefore for(set, ...), returns; iter() yields pointers.

The order is arbitrary but reproducible for a set built with new()'s fixed SipHash keys.

Type Parameters

NameTypeNotes
TTypecomptime

Trait Implementations

Iterator
impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSetIter(T), Iterator(...))
Item : T
next : (fn(self : &mut Self) -> Option(T))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(T)

HashSetIterPtr type-function
fn(T : Type) -> Type

Pointer iterator over a HashSet — yields *(T) INTO the backing map's bucket array, so elements are borrowed rather than dup'd. This is what iter() returns (D14).

The pointers alias the map's storage: any insert that rehashes, any remove, or clear invalidates pointers already yielded. The element is the entry's KEY, addressed rather than assumed to sit at offset 0. Like HashMapIterPtr, it holds the bucket arrays, not the set (decision 39, B7b): the set must outlive the walk.

Type Parameters

NameTypeNotes
TTypecomptime

Trait Implementations

Iterator
impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSetIterPtr(T), Iterator(...))
Item : *T
next : (fn(self : &mut Self) -> Option(*T))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(*T)