Hash Tables

A HashMap in in Rust is a data structure that allows an amortized O(1) search, insert, and delete of key-value pairs.

The type of std::collections::HashMap with key type K and value type V is

pub struct HashMap<K, V>

godbolt
playground

A HashMap can be created with the new method, and the type can either be explicitly given or inferred.

use std::collections::HashMap;

fn main() {
    let map_a: HashMap<&str, i32> = HashMap::new();
    let map_b = HashMap::<&str, i32>::new();
    // Inferred to be the same type as map_a and map_b
    let mut map_c = HashMap::new();
    map_c.insert("hello", 5);
}

godbolt
playground

Inserting Values

The insert method allows inserting key-value pairs into a HashMap. The key must implement the Eq and Hash traits.

Inserting into a HashMap moves ownership, copies, or borrows depending on the type passed to HashMap.

use std::collections::HashMap;

fn main() {
    let (team, score) = (String::from("Crabs"), 5);
    let mut scores: HashMap<String, i32> = HashMap::new();
    scores.insert(team, score);
    println!("{score}"); // Cannot use `team` here

    let team = String::from("Crabs");
    let mut useless: HashMap<&str, &str> = HashMap::new();
    useless.insert(&team, &team);
    println!("{team}");
}

godbolt
playground

Retrieving Values

A reference to the value corresponding to a key can be retrieved with the get and get_mut methods:

use std::collections::HashMap;

fn main() {
    let (team, score) = (String::from("Crabs"), 5);
    let mut scores: HashMap<String, i32> = HashMap::new();
    scores.insert(team, score);

    let score_for_unknown: Option<&i32> = scores.get("Unknown");
    assert!(score_for_unknown.is_none());

    let score_for_crabs: &mut i32 = scores.get_mut("Crabs").unwrap();
    *score_for_crabs += 1;
    println!("{}", score_for_crabs);
}

godbolt
playground

Iterating Over Keys/Values/Key-Value Pairs

The iter/iter_mut methods return an iterator of key-value references
The values/values_mut methods return an iterator of value references
The keys method return an iterator of key references

use std::collections::HashMap;

fn main() {
  let mut scores = HashMap::new();

  scores.insert(String::from("Blue"), 10);
  scores.insert(String::from("Yellow"), 50);

  for (key, value) in scores.iter() {
      println!("{key}: {value}");
  }
}

godbolt
playground

Updating Values

Overwriting a Value

You can overwrite key-value pairs by calling insert:

use std::collections::HashMap;

fn main() {
  let mut scores = HashMap::new();

  scores.insert(String::from("Blue"), 10);
  scores.insert(String::from("Blue"), 50);
  // {"Blue": 50}
  println!("{scores:?}");
}

godbolt
playground

Updating Values (2)

Inserting a value if the key does not exist

You can use the Entry API:

use std::collections::HashMap;

fn main() {
  let mut scores = HashMap::new();

  scores.insert(String::from("Blue"), 10);

  scores.entry(String::from("Blue")).or_insert(50);
  scores.entry(String::from("Green")).or_insert(50);

  // {"Blue": 10, "Green": 50}
  println!("{scores:?}");
}

godbolt
playground

Updating Values (3)

Updating a value with a default if the key does not exist

The or_insert method returns a mutable reference that can be used:

use std::collections::HashMap;

fn main() {
  let words = ["a", "b", "a", "a", "c", "d", "b"];
  let mut counts = HashMap::new();

  for word in words {
      let count = counts.entry(word).or_insert(0);
      *count += 1;
  }

  // {"b": 2, "c": 1, "d": 1, "a": 3}
  println!("{counts:?}");
}

godbolt
playground