Documentation
¶
Overview ¶
Package hashset implements an unordered set data structure based on hash tables.
HashSet is a collection type that stores unique elements in a hash table. It achieves average O(1) time complexity for insertion, deletion, and lookup. Unlike ordered sets (BTreeSet, SkipSet), iteration order is not guaranteed. Internally, HashSet is implemented using HashMap with empty structs as values.
Time Complexity ¶
- Insert: O(1) average, O(n) worst case (hash collisions)
- Delete: O(1) average, O(n) worst case
- Contains: O(1) average, O(n) worst case
- Union/Intersection/Difference: O(m + n) where m, n are set sizes
- Traversal: O(n)
Features ¶
- Fast membership testing with average O(1) time complexity
- Generic type support with custom hashers
- Standard set operations: Union, Intersection, Difference, SymmetricDifference
- Subset/superset checks: IsSubsetOf, IsSupersetOf
- Batch operations
Usage ¶
HashSet requires a hasher implementation for element types:
// For string elements, use the provided StringHasher
set := hashset.New[string](hashutil.StringHasher)
set.Insert("apple")
set.Insert("banana")
// Check existence
if set.Contains("apple") {
fmt.Println("Found apple")
}
Differences from Ordered Sets ¶
HashSet provides faster average-case performance but lacks ordering:
// BTreeSet/SkipSet: sorted iteration, range queries // HashSet: faster operations, no ordering guarantee
When to use HashSet:
- Fast membership testing is the primary concern
- Iteration order doesn't matter
- Elements are not naturally ordered
Index ¶
- type HashSet
- func (hs *HashSet[E, H]) Clear()
- func (hs *HashSet[E, H]) Clone() *HashSet[E, H]
- func (hs *HashSet[E, H]) Compact()
- func (hs *HashSet[E, H]) Contains(value E) bool
- func (hs *HashSet[E, H]) Difference(other *HashSet[E, H]) *HashSet[E, H]
- func (hs *HashSet[E, H]) Entry(value E) hashmap.Entry[E, struct{}, H]
- func (hs *HashSet[E, H]) Equal(other *HashSet[E, H]) bool
- func (hs *HashSet[E, H]) Extend(it iter.Seq[E])
- func (hs *HashSet[E, H]) Insert(value E) bool
- func (hs *HashSet[E, H]) Intersection(other *HashSet[E, H]) *HashSet[E, H]
- func (hs *HashSet[E, H]) IsDisjoint(other *HashSet[E, H]) bool
- func (hs *HashSet[E, H]) IsEmpty() bool
- func (hs *HashSet[E, H]) IsSubset(other *HashSet[E, H]) bool
- func (hs *HashSet[E, H]) IsSuperset(other *HashSet[E, H]) bool
- func (hs *HashSet[E, H]) Iter() iter.Seq[E]
- func (hs *HashSet[E, H]) Len() int
- func (hs *HashSet[E, H]) Remove(value E) bool
- func (hs *HashSet[E, H]) SymmetricDifference(other *HashSet[E, H]) *HashSet[E, H]
- func (hs *HashSet[E, H]) Union(other *HashSet[E, H]) *HashSet[E, H]
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HashSet ¶
func New ¶
New creates a new HashSet instance.
Parameters:
hasher: Concrete implementation instance for element hash computation and equality comparison
Return value:
Pointer to the newly created HashSet
Time complexity: O(1)
func NewComparable ¶
func NewComparable[E comparable]() *HashSet[E, hashutil.Default[E]]
NewComparable creates a new HashSet instance with a default hasher for comparable key types.
Type Parameters:
- E: Element type, must be comparable
Returns:
- Pointer to the newly created HashSet
Example:
set := hashset.NewComparable[string]()
func (*HashSet[E, H]) Clear ¶
func (hs *HashSet[E, H]) Clear()
Clear empties the set, removing all elements.
After this operation, Len() will return 0.
Time complexity: O(n), where n is the number of elements in the set
func (*HashSet[E, H]) Clone ¶
Clone creates a deep copy of the set.
Return value:
New HashSet instance containing all elements of the original set
Note: This method performs a deep copy of the set structure, but elements themselves are copied by value (if elements are pointers, the pointers are copied).
Time complexity: O(n), where n is the number of elements in the set
func (*HashSet[E, H]) Compact ¶
func (hs *HashSet[E, H]) Compact()
Compact compacts the set, removing all deleted nodes.
This operation frees memory and improves iteration and lookup efficiency, especially after numerous deletion operations.
Time complexity: O(n), where n is the number of buckets in the set
func (*HashSet[E, H]) Contains ¶
Contains checks if the set contains the specified element.
Parameters:
value: The element value to check
Return value:
true if the set contains the element; false otherwise
Time complexity: Average O(1), worst O(n)
func (*HashSet[E, H]) Difference ¶
Difference creates a new set containing elements that exist in the current set but not in another set (difference).
Parameters:
other: Another set to compute difference with the current set
Return value:
New set containing elements belonging to the current set but not to the other set
Mathematical definition: A \ B = {x | x ∈ A and x ∉ B}
Time complexity: Average O(n), where n is the size of the current set
func (*HashSet[E, H]) Entry ¶
Entry retrieves the Entry state for an element, for flexible handling of insertion operations.
Parameters:
value: The element value to retrieve the Entry state for
Return value:
The Entry state for the corresponding element, which can be used for more complex insertion logic
This method is similar to Rust's HashSet::entry method, allowing conditional insertion in a single lookup.
Time complexity: Average O(1), worst O(n)
func (*HashSet[E, H]) Extend ¶
Extend inserts all elements from the iterator into the set.
Parameters:
- it: An iterator yielding elements to insert.
Behavior:
- Elements are only added if they don't already exist in the set.
func (*HashSet[E, H]) Insert ¶
Insert adds an element to the set.
Parameters:
value: The element value to insert
Return value:
true if the element does not exist and was successfully inserted; false if the element already exists
Time complexity: Average O(1), worst O(n)
func (*HashSet[E, H]) Intersection ¶
Intersection creates a new set containing elements that exist in both the current set and another set (intersection).
Parameters:
other: Another set to intersect with the current set
Return value:
New set containing elements that exist in both sets
Mathematical definition: A ∩ B = {x | x ∈ A and x ∈ B}
Time complexity: Average O(min(n, m)), where n and m are the sizes of the two sets
func (*HashSet[E, H]) IsDisjoint ¶
IsDisjoint checks if the current set and another set are disjoint (have no common elements).
Parameters:
other: Another set to check against
Return value:
true if the two sets have no common elements; false otherwise
Mathematical definition: A and B are disjoint ⇨ A ∩ B = ∅
Time complexity: Average O(min(n, m)), where n and m are the sizes of the two sets
func (*HashSet[E, H]) IsEmpty ¶
IsEmpty checks if the set is empty.
Return value:
true if the set is empty (contains no elements); false otherwise
Time complexity: O(1)
func (*HashSet[E, H]) IsSubset ¶
IsSubset checks if the current set is a subset of another set.
Parameters:
other: Parent set to check against
Return value:
true if all elements of the current set exist in the other set; false otherwise
Mathematical definition: A ⊆ B ⇨ for all x ∈ A, x ∈ B
Time complexity: Average O(n), where n is the size of the current set
func (*HashSet[E, H]) IsSuperset ¶
IsSuperset checks if the current set is a superset of another set.
Parameters:
other: Subset to check against
Return value:
true if all elements of the other set exist in the current set; false otherwise
Mathematical definition: A ⊇ B ⇨ for all x ∈ B, x ∈ A
Time complexity: Average O(m), where m is the size of the other set
func (*HashSet[E, H]) Iter ¶
Iter returns an iterator over all elements in the set.
Returns:
- An iter.Seq[E] that yields all elements.
- Order is non-deterministic (hash order).
Time Complexity: O(n)
func (*HashSet[E, H]) Len ¶
Len returns the number of elements in the set.
Return value:
The count of elements in the set
Time complexity: O(1)
func (*HashSet[E, H]) Remove ¶
Remove removes the specified element from the set.
Parameters:
value: The element value to remove
Return value:
true if the element exists and was successfully removed; false if the element does not exist
Time complexity: Average O(1), worst O(n)
func (*HashSet[E, H]) SymmetricDifference ¶
SymmetricDifference creates a new set containing elements that exist only in the current set or only in another set (symmetric difference).
Parameters:
other: Another set to compute symmetric difference with the current set
Return value:
New set containing elements that belong only to the current set or only to the other set
Mathematical definition: A △ B = (A \ B) ∪ (B \ A) = {x | x ∈ A XOR x ∈ B}
Time complexity: Average O(n + m), where n and m are the sizes of the two sets
func (*HashSet[E, H]) Union ¶
Union creates a new set containing all elements from the current set and another set (union).
Parameters:
other: Another set to union with the current set
Return value:
New set containing all distinct elements from both sets
Mathematical definition: A ∪ B = {x | x ∈ A or x ∈ B}
Time complexity: Average O(n + m), where n and m are the sizes of the two sets
Source Files