Hash Sets in Rust: HashSet Basics

Hash Sets are collections of unique items i.e no element can be repeated.

Hash Sets were designed to give us a way of adding and looking for unique values in a collection in a quick manner.

The values in a Hash Set can be either simple primitives like strings or integers as well as more complex types like structs or tuples.

In Rust, the Hash Set is implemented as the HashSet type from the Standard Library.

Creation:

To create a new empty HashSet that holds strings, you use the following syntax:

use std::collections::HashSet;
let mut my_set: HashSet<String> = HashSet::new();

Creating an empty Set takes O(1) time.

Constructing from iterable

You can also build a set from any iterator with collect(). All the unique elements of the iterator will be added to the new set:

let elements = vec!["b", "c", "c", "d"];
let my_set: HashSet<&str> = elements.into_iter().collect();

// my_set contains {"b", "c", "d"}

This takes O(n) time, where n is the number of elements in the iterator.

Adding elements:

To add an element to the set, you use the insert() method:

let mut my_set: HashSet<&str> = ["b", "c", "c", "d"].iter().cloned().collect();

// Adding new elements
my_set.insert("x");

// Adding an existing element
my_set.insert("d"); // nothing happens

// my_set contains {"b", "c", "d", "x"}

The Set first checks if that element already exists and if so, it does nothing and also doesn't raise an error.

Adding an element to a Set takes O(1) time.

Checking if a value exists:

To check if a Set has a specific element, you use the contains() method which returns true if the set contains the element, otherwise, it returns false.

let my_set: HashSet<&str> = ["b", "c", "c", "d"].iter().cloned().collect();

my_set.contains("c"); // returns true since 'c' exists in the set

my_set.contains("x"); // returns false since it does not exist in the set

Checking if a value exists in a Set takes O(1) time.

Removing elements:

To delete a specified element from a set, you use the remove() method:

let mut my_set: HashSet<&str> = ["b", "c", "c", "d"].iter().cloned().collect();

// Deleting elements
my_set.remove("c");

// Deleting a non-existent element
my_set.remove("z"); // does nothing

// my_set contains {"b", "d"}

The Set first checks if that key exists and if not, it does nothing and also doesn't raise an error, so it's safe to delete non-existing elements.

Removing an element from a Set takes O(1) time.

Iterating over the Set values:

If we want to iterate over values of the HashSet, we can use the for loop along with the & operator:

let my_set: HashSet<&str> = ["b", "c", "c", "d"].iter().cloned().collect();

for val in &my_set {
    println!("{}", val);
}

// This will print the following:
// d
// c
// b

Iterating over a HashSet takes O(n) time.

Notice the order is not the same as we initiated. HashSet keeps the data in random order

Space Complexity

A Set uses O(n) space, where n is the number of elements existing in the Set.

Assignment
Follow the Coding Tutorial and let's play with some Hash Sets.

Hint
Look at the examples above if you get stuck.