Module: collections.hashset

Source: ./collections/hashset.reef

Overview

collections/hashset - Generic Hash Set implementation

Provides a type-safe generic HashSet with string elements. Uses open addressing with linear probing for collision handling. Grows and rehashes automatically when an insert would push load past 70% (double capacity, min 1). Membership hits (already present) never rehash, even when load is already ≥ 70%. add returns false only if the element already existed (or on hard failure) — not because the set was "full".

NOTE: Due to language limitations with runtime array allocation of generic types, this implementation uses string elements only. For other types, convert to string first.

Usage: import collections.hashset let s = hashset.create() // Create empty set s.add("apple") s.add("banana") if s.contains("apple") println("found!") end if s.remove("apple")

Available factory functions: create() -> HashSet - 256 slot capacity create_with_capacity(cap) -> HashSet - Custom capacity

Methods: add(element) -> bool - Add element, returns true if added (false if existed) try_add(element) -> Result[bool, Error] Ok(true) = newly added; Ok(false) = already present; Err = hard failure after grow/retry (not "full" under normal use) contains(element) -> bool - Check if element exists remove(element) -> bool - Remove element, returns true if existed len() -> int - Number of elements clear() - Remove all elements elements() -> [string] - Get array of all elements capacity() -> int - Get total capacity is_empty() -> bool - Check if set is empty

Set Operations: union(other) -> HashSet - Return new set with elements from both intersection(other) -> HashSet - Return new set with common elements difference(other) -> HashSet - Return new set with elements not in other is_subset(other) -> bool - Check if this is subset of other is_superset(other) -> bool - Check if this is superset of other

Performance:

• O(1) average for add/contains/remove
• O(n) for elements() iteration / rehash
• O(n) for set operations (union, intersection, difference)
• Auto-rehash keeps load factor under 70%

Types

HashSet

Entry states: 0=empty, 1=occupied, 2=deleted (tombstone)

Fields:

Functions

fn hash_string(s: string): int

DJB2 hash function for strings - fast and good distribution

fn create(): HashSet

Create HashSet with 256-slot default capacity

fn create_with_capacity(cap: int): HashSet

Create HashSet with custom capacity

fn set_contains(s: HashSet, element: string): bool

Check if element exists in a HashSet (standalone function version)

Generated by reefc doc