Hashmaps and sets

Recipe	Crates
Store Key-Value Pairs into a HashMap
Store Unique Items in a HashSet
Use a Custom Type as the Key of a HashMap
Use a Custom Hash Function with HashMap and HashSet

Store Key-Value Pairs into a HashMap

HashMap↗ is a key-value data structure. It allows you to store data in an unordered collection, where each element is identified by a unique key. This makes HashMap an excellent choice for lookups, insertions, and deletions based on keys.

All hashmap keys must have the same type. All values must have the same type.

//! This example demonstrates the basic usage of `HashMap` in Rust.
//!
//! `HashMap` is a collection that stores key-value pairs, where each key is
//! unique. It's useful for scenarios where you need to quickly look up values
//! based on keys.
//!
//! This example covers creating, inserting, updating, accessing, iterating, and
//! removing elements from a `HashMap`.

use std::collections::HashMap;

fn main() {
    // Create a new, empty HashMap called 'scores'.
    let mut scores = HashMap::new();

    // Insert a key-value pair into the HashMap.
    // The key is "Blue" (a `String`), and the value is 10 (an `i32`).
    scores.insert(String::from("Blue"), 10);

    // Update the value associated with the key "Blue".
    // The previous value will be replaced with 25.
    scores.insert(String::from("Blue"), 25);

    // Get the value associated with 'team_name' from the HashMap.
    let team_name = String::from("Blue");
    // `get()` returns an `Option<&i32>`.
    // `copied()` converts it to `Option<i32>` by copying the value.
    // `unwrap_or(0)` returns the value if it exists, or 0 if it doesn't.
    let _score = scores.get(&team_name).copied().unwrap_or(0);

    // Another way to access values using pattern matching:
    let score = scores.get(&team_name);
    match score {
        Some(s) => println!("Team {team_name} score: {s}"),
        None => println!("Team {team_name} not found"),
    }

    // Iterate over and print the key-value pairs in the `HashMap`
    // (in arbitrary order). '&scores' borrows the `HashMap` immutably.
    for (key, value) in &scores {
        println!("{key}: {value}");
    }

    // Check if a key exists.
    if scores.contains_key(&String::from("Blue")) {
        println!("Blue team exists");
    }

    // Getting the length.
    println!("Number of teams: {}", scores.len());

    // Insert a key-value pair only if the key doesn't already exist.
    // `entry()` returns an `Entry` enum, and `or_insert` inserts the value if
    // the key is absent, otherwise it does nothing.
    scores.entry(String::from("Yellow")).or_insert(50);

    // Remove a key and return its value if present.
    if let Some(removed_value) = scores.remove(&String::from("Blue")) {
        println!("Removed Blue team with score: {removed_value}");
    }

    // Clear the HashMap.
    scores.clear();
    println!("After clearing, number of teams: {}", scores.len());
}

Store Unique Items in a HashSet

HashSet↗ is a common data structure that stores a collection of unique items, similar to the keys of a HashMap but without associated values.

//! This example demonstrates the basic usage of `HashSet`.
//!
//! `HashSet` is a collection that stores unique values. It's useful for
//! scenarios where you need to ensure that no duplicate values are present.
use std::collections::HashSet;

fn main() {
    // Create a new `HashSet`:
    let mut languages = HashSet::new();

    // Insert values:
    languages.insert("Rust");
    languages.insert("Python");
    languages.insert("JavaScript");

    // Insert duplicate values (which are ignored).
    let added = languages.insert("Rust");
    println!("Was 'Rust' added? {added}"); // false - it already exists.

    // Create a `HashSet` from iterators:
    let numbers = vec![1, 2, 3, 4, 5, 1, 2, 3];
    let unique_numbers: HashSet<_> = numbers.into_iter().collect();
    println!("Unique numbers: {unique_numbers:?}"); // 1, 2, 3, 4, 5 (order may vary).

    // Check if an element exists:
    if languages.contains("Rust") {
        println!("Rust is in the set.");
    }

    // Remove elements:
    if languages.remove("Python") {
        println!("Python was removed from the set.");
    }

    // Iterate over elements:
    for language in &languages {
        println!("{language}");
    }

    // Set operations:
    let set1: HashSet<_> = [1, 2, 3].iter().cloned().collect();
    let set2: HashSet<_> = [3, 4, 5].iter().cloned().collect();

    // Union.
    let union: HashSet<_> = set1.union(&set2).cloned().collect();
    println!("Union: {union:?}"); // 1, 2, 3, 4, 5.

    // Intersection.
    let intersection: HashSet<_> = set1.intersection(&set2).cloned().collect();
    println!("Intersection: {intersection:?}"); // 3.

    // Difference.
    let difference: HashSet<_> = set1.difference(&set2).cloned().collect();
    println!("Difference (set1 - set2): {difference:?}"); // 1, 2.

    // Symmetric difference (elements in either set but not both).
    let symmetric_difference: HashSet<_> =
        set1.symmetric_difference(&set2).cloned().collect();
    println!("Symmetric Difference: {symmetric_difference:?}"); // 1, 2, 4, 5.

    // Check if a set is a subset of another:
    let subset: HashSet<_> = [1, 2].iter().cloned().collect();
    println!(
        "Is {subset:?} a subset of {set1:?}? {}",
        subset.is_subset(&set1)
    ); // true

    // Get the length:
    println!("Number of languages: {}", languages.len());

    // Clear the set:
    languages.clear();
    println!("After clearing, languages: {languages:?}"); // {}
}

Use a Custom Type as the Key of a HashMap

You can use a custom-defined type (typically a struct) as keys in a HashMap. It is useful when you need to associate data with complex, multi-component identifiers that don't fit naturally into a single primitive type like an integer or a string.

//! Demonstrate using a custom type as the key in a `HashMap`.

use std::collections::HashMap;
use std::hash::DefaultHasher;
use std::hash::Hash;
use std::hash::Hasher;

// Custom struct that will be used as a key.
// `Hash` and `Eq` traits must be implemented in order to use the struct as a
// `HashMap` key. Implement them manually or use the `derive` attribute.
#[derive(Debug, PartialEq, Eq)]
struct Student {
    id: u32,
}

// Manual implementation of `Hash` for demonstration purposes.
// BEWARE: If two keys are equal, their hashes must be equal.
// This is a fundamental requirement for hash-based collections.
// k1 == k2 -> hash(k1) == hash(k2)
impl Hash for Student {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state);
    }
}

fn main() {
    // Create a new HashMap to store student grades.
    let mut grades = HashMap::new();

    // Create some student instances.
    let alice = Student { id: 1 };
    let alice2 = Student { id: 1 }; // Same ID.
    let bob = Student { id: 2 };

    // Let's make sure the hashing relationship above stands.
    assert_eq!(alice, alice2);
    assert_eq!(calculate_hash(&alice), calculate_hash(&alice2));

    // Insert student grades into the HashMap.
    grades.insert(alice, 95);
    grades.insert(bob, 87);

    // Look up a student's grade using their ID.
    // Note that we create a new Student instance for lookup,
    // but it's considered the same key if the IDs match.
    let lookup_student = Student { id: 2 };
    if let Some(grade) = grades.get(&lookup_student) {
        println!("Student with ID 2 got grade: {grade}");
    }
}

fn calculate_hash<T: Hash>(t: &T) -> u64 {
    let mut s = DefaultHasher::new();
    t.hash(&mut s);
    s.finish()
}

Use a Custom Hash Function with HashMap and HashSet

You can use a custom hash function with HashMap↗ and HashSet↗. In the following, the Fowler-Noll-Vo hash function is used for better performance with short keys.

//! Demonstrates how to use a custom hash function (FNV) with `HashMap` and
//! `HashSet` for better performance with small keys.
//!
//! **Warning:** FNV is not suitable if there is a risk of denial-of-service
//! attacks. Be certain that your program is not exposed to malicious inputs.
//!
//! Add to your `Cargo.toml`: `fnv = "1.0.7" # Or latest`.

use std::collections::HashMap;
use std::collections::HashSet;

fn main() {
    let mut fnv_map = HashMap::with_hasher(fnv::FnvBuildHasher::default());
    fnv_map.insert("key1", "value1");
    fnv_map.insert("key2", "value2");

    // Or simpler:
    let mut _map: fnv::FnvHashMap<&str, &str> = fnv::FnvHashMap::default();

    // Similarly for `HashSet`:
    let mut fnv_set = fnv::FnvHashSet::default();
    fnv_set.insert("item1");
    fnv_set.insert("item2");

    // You may also pre-allocate capacity for better performance:
    let mut _map_with_capacity: HashMap<String, String> =
        HashMap::with_capacity(100);
    let mut _set_with_capacity: HashSet<String> = HashSet::with_capacity(100);

    // Or set both capacity and a custom hasher:
    let mut map =
        fnv::FnvHashMap::with_capacity_and_hasher(10, Default::default());
    map.insert(1, "one");
    map.insert(2, "two");
}

Related Data Structures

• B-trees.
• Other Maps.

Related Topics

• Data Structures.