Module

std::collections::hash_set

HashSet

Deterministic hash set built on top of HashMap<T, HashSetMarker>.

Overview

HashSet<T> stores only keys. Internally it delegates storage, probing, resizing, and drop behavior to HashMap<T, HashSetMarker>.

This means the set inherits the same deterministic hashing behavior as HashMap while exposing a simpler presence/absence API.

Marker Payload

HashSetMarker is a zero-sized marker payload used internally so the set can be implemented on top of HashMap without storing a meaningful value.

How It Works

HashSet<T> is intentionally thin. It does not reimplement probing, resizing, tombstones, or raw storage management.

Instead, it delegates to HashMap<T, HashSetMarker> and translates the map API into set semantics:

  HashSet::insert(value)
    -> HashMap::insert(value, HashSetMarker {})
    -> returns true only when the key was absent

  HashSet::contains(value)
    -> HashMap::get(value)
    -> presence/absence only

  HashSet::remove(value)
    -> HashMap::remove(value)
    -> returns true only when the key existed

This keeps the public API simple while reusing the proven HashMap implementation for all hash-table mechanics.

Key Requirements

Elements must satisfy Hash & Eq.

Example

import Eq from "std::collections";
import Hash from "std::collections";
import HashSet from "std::collections";
import Hasher from "std::hash";

@implements(Hash, Eq)
record Key {
  id: i32;

  hash(&self, hasher: &mut Hasher): void {
    let mut state: &mut Hasher = hasher;
    state.writeI32(self.id);
  }

  equals(&self, other: &Key): boolean {
    return self.id == other.id;
  }
}

function main(): i32 {
  let mut set: HashSet<Key> = HashSet::new<Key>();
  set.insert(Key { id: 1 });

  let lookup: Key = Key { id: 1 };
  return set.contains(&lookup) ? 0 : 1;
}

Records

record HashSet<T>

Deterministic set of unique values of type T.

Members

map: HashMap<T, HashSetMarker>

static init(capacity: u64): HashSet<T>

Compatibility alias for HashSet::new(capacity).

static init(capacity: u64): HashSet<T>

Compatibility alias for HashSet::new(capacity).

static new(capacity: u64): HashSet<T>

Creates an empty set with enough buckets for at least capacity logical elements under the current load-factor policy.

Example

import HashSet from "std::collections";

let set: HashSet<i32> = HashSet::new<i32>(64);

static new(capacity: u64): HashSet<T>

Creates an empty set with enough buckets for at least capacity logical elements under the current load-factor policy.

Example

import HashSet from "std::collections";

let set: HashSet<i32> = HashSet::new<i32>(64);

capacity(&self): u64

Returns the number of buckets currently allocated by the backing map.

clear(&mut self): void

Removes all values while preserving the current bucket allocation.

Example

import HashSet from "std::collections";

let mut set: HashSet<i32> = HashSet::new<i32>();
set.insert(1);
set.clear();

contains(&self, value: &T): boolean

Returns true if value is already present.

Example

import HashSet from "std::collections";

let mut set: HashSet<i32> = HashSet::new<i32>();
set.insert(7);
let found: boolean = set.contains(&7);

drop(&mut self): void

Drops all values and releases backing storage.

insert(&mut self, value: T): boolean

Inserts value if absent.

Returns true when the value was newly inserted and false when it was already present.

Example

import HashSet from "std::collections";

let mut set: HashSet<i32> = HashSet::new<i32>();
let first: boolean = set.insert(7);  // true
let second: boolean = set.insert(7); // false

isEmpty(&self): boolean

Returns true when the set contains no elements.

length(&self): u64

Returns the number of stored elements.

remove(&mut self, value: &T): boolean

Removes value from the set.

Returns true when the value existed and false otherwise.

Example

import HashSet from "std::collections";

let mut set: HashSet<i32> = HashSet::new<i32>();
set.insert(7);
let removed: boolean = set.remove(&7);

reserve(&mut self, additional: u64): void

Ensures the set can accommodate additional more elements without immediate growth.

Example

import HashSet from "std::collections";

let mut set: HashSet<i32> = HashSet::new<i32>();
set.reserve(32);

record HashSetMarker

Zero-sized marker stored as the internal value payload of HashSet.

This is exported so low-level tests and examples can inspect its layout, but normal code should treat it as an implementation detail.