Module collections/hash_set
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/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
High-performance hash set, backed by HashMap(T, unit) (D16).
Elements must implement Eq and Hash. O(1) average lookup and insert.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
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
try_insert : (fn(self : 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 : 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 : 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. Internal — exposed so the key-survival tests can 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. Internal — exposed for the reclamation tests, which now verify that the delegation is real.
Returns: usize
is_empty : (fn(self : Self) -> bool)True when the set holds no elements.
Returns: bool
clear : (fn(self : 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 : TIntoIter : 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 iteration, yielding a *(T) into the backing storage.
Returns: HashSetIterPtr(T)
impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSet(T), FromIterator(...))
Elem : Tfrom_iter_new : (fn() -> Self)The empty collection collect starts from.
Returns: Self
from_iter_add : (fn(acc : Self, item : T) -> Self)Add one element to a partially-built collection and return it.
Parameters
| Name | Type | Notes |
|---|---|---|
acc | Self | |
item | T |
Returns: Self
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 : Tfrom_iter_new : (fn() -> Self)The empty collection collect starts from.
Returns: Self
from_iter_add : (fn(acc : Self, item : T) -> Self)Add one element to a partially-built collection and return it.
Parameters
| Name | Type | Notes |
|---|---|---|
acc | Self | |
item | T |
Returns: Self
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
| Variant | Fields | Description |
|---|---|---|
AllocError | error: AllocError | Memory allocation failed. |
CapacityOverflow | Capacity calculation overflowed. |
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
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSetIter(T), Iterator(...))
Item : Tnext : (fn(inout(self) : Self) -> Option(T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(T)
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.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: (Eq(T), Hash)), HashSetIterPtr(T), Iterator(...))
Item : *(T)next : (fn(inout(self) : Self) -> Option(*(T)))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(*(T))
Functions
hash_set macro — construct a HashSet(T) literal.
T is inferred from the first element via typeof, so at least one
element is required.
Example
s := hash_set(i32(1), i32(2), i32(3));
Returns: unquote(Expr)