Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust HashSet<T> type

Reference for Rust HashSet<T>: inserting, membership tests, removing, iteration order, key requirements, deduplication and how it relates to HashMap.

HashSet<T> in std::collections stores each distinct value once and answers "is this value in the set?" in O(1) on average. It is implemented as a HashMap<T, ()>, so it has the same requirements: T must implement Eq and Hash, and the iteration order is unspecified.

Use it for deduplication, for fast membership tests, and for set algebra such as union and intersection (see HashSet union, intersection, difference).

Rust
use std::collections::HashSet;

let mut seen: HashSet<&str> = HashSet::new();
let first_time = seen.insert("rust"); // true

Try it

Rust Insert, contains, remove

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rust Deduplicating and detecting repeats

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Syntax

Rust
pub struct HashSet<T, S = RandomState> { /* private */ }

impl<T: Eq + Hash> HashSet<T, RandomState> {
    pub fn new() -> HashSet<T, RandomState>;
    pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState>;
}

impl<T: Eq + Hash, S: BuildHasher> HashSet<T, S> {
    pub fn insert(&mut self, value: T) -> bool;
    pub fn contains<Q>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: Hash + Eq + ?Sized;
    pub fn remove<Q>(&mut self, value: &Q) -> bool where T: Borrow<Q>, Q: Hash + Eq + ?Sized;
    pub fn take<Q>(&mut self, value: &Q) -> Option<T>;
    pub fn get<Q>(&self, value: &Q) -> Option<&T>;
    pub fn replace(&mut self, value: T) -> Option<T>;
    pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F);
}
Name Description
value The element. insert and replace take ownership; lookups take a reference to any borrowed form.
capacity Elements to make room for up front.
f Predicate for retain; return true to keep an element.

Returns: insert returns true if the value was new and false if an equal value was already present (the set is left unchanged). remove returns true if something was removed. take removes and returns the stored value; replace swaps in the new value and returns the old equal one.

Errors and panics: none besides allocation failure.

Usage notes

  • insert does not overwrite. An equal element already in the set stays; use replace if the new value should win.
  • Order is random. Sort the elements or use BTreeSet when you need a stable order.
  • Borrowed lookups work: a HashSet<String> answers contains("text") without allocating.
  • Building: iter.collect::<HashSet<_>>(), HashSet::from([..]) and extend(iter) are all common.
  • Comparison: == compares contents regardless of order; is_subset, is_superset and is_disjoint test relationships.
  • Not Hash itself. Sets cannot be elements of other hash sets. Use BTreeSet or a sorted Vec, which are hashable when their elements are.
  • No floats (no Eq), but f64::to_bits() works as a stand-in key.
  • Cost: like HashMap, iteration is O(capacity); reserve and shrink_to_fit manage memory.