Collections

Count Word Frequency in a Document

Splits a string into words with split_whitespace and counts each word’s occurrences. HashMap::entry with or_insert initializes a missing key to zero and returns a mutable reference, so the increment requires no separate lookup. sort_by_key with Reverse sorts the results descending by count; wrapping the count in Reverse flips the natural ascending order without a manual comparator.

use std::cmp::Reverse;
use std::collections::HashMap;

fn word_count(text: &str) -> HashMap<&str, usize> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    counts
}

fn main() {
    let text = "the quick brown fox jumps over the lazy dog the fox";
    let counts = word_count(text);

    let mut pairs: Vec<(&str, usize)> = counts.iter().map(|(&w, &c)| (w, c)).collect();
    pairs.sort_by_key(|&(word, count)| (Reverse(count), word));
    for (word, count) in &pairs {
        println!("{word:>12}  {count}");
    }

    assert_eq!(counts["the"], 3);
    assert_eq!(counts["fox"], 2);
    assert_eq!(counts["quick"], 1);
}

Group Records by Key

Groups a flat list of records into a HashMap of vectors using entry with or_default, which inserts an empty Vec the first time a key is seen and returns a mutable reference to it on every call. keys with copied produces an owned Vec<&str> for sorting — copied turns the &&str references that keys yields into &str values.

use std::collections::HashMap;

fn main() {
    let log_lines = vec![
        ("ERROR", "disk full"),
        ("WARN", "high memory usage"),
        ("INFO", "server started"),
        ("ERROR", "connection refused"),
        ("INFO", "request received"),
    ];

    let mut by_level: HashMap<&str, Vec<&str>> = HashMap::new();
    for (level, message) in log_lines {
        by_level.entry(level).or_default().push(message);
    }

    let mut levels: Vec<&str> = by_level.keys().copied().collect();
    levels.sort();
    for level in levels {
        println!("[{level}]");
        for msg in &by_level[level] {
            println!("  {msg}");
        }
    }

    assert_eq!(by_level["ERROR"].len(), 2);
    assert_eq!(by_level["INFO"].len(), 2);
    assert_eq!(by_level["WARN"].len(), 1);
}

Look Up Records Within a Time Range

Stores timestamped sensor readings in a BTreeMap, which keeps keys in sorted order using a B-tree structure. BTreeMap::range locates the start of the range with binary search in O(log n) time and then iterates forward — so the cost scales with the result size, not the total number of entries. A HashMap cannot do this at all; it has no ordering to exploit.

use std::collections::BTreeMap;

fn main() {
    let mut readings: BTreeMap<u32, f64> = BTreeMap::new();
    readings.insert(1_000, 20.1);
    readings.insert(2_000, 21.3);
    readings.insert(3_000, 19.8);
    readings.insert(4_000, 22.5);
    readings.insert(5_000, 23.1);

    let window: Vec<(&u32, &f64)> = readings.range(2_000..=4_000).collect();
    println!("Readings from t=2000 to t=4000:");
    for (ts, temp) in &window {
        println!("  t={ts:>5}  {temp:.1}°C");
    }

    assert_eq!(window.len(), 3);
    assert_eq!(*window[0].0, 2_000);
    assert_eq!(*window[2].0, 4_000);
}

Set Operations with HashSet

Computes the difference, intersection, and union of two HashSets. Each operation returns an iterator of references; copied converts &&str to &str for easier collection.

use std::collections::HashSet;

fn main() {
    let deployed: HashSet<&str> = ["web", "api", "worker", "scheduler"]
        .iter()
        .copied()
        .collect();
    let monitored: HashSet<&str> = ["web", "api", "database"].iter().copied().collect();

    // Services running but not being monitored
    let mut unmonitored: Vec<&str> = deployed.difference(&monitored).copied().collect();
    unmonitored.sort();
    println!("Deployed but not monitored: {unmonitored:?}");
    assert_eq!(unmonitored, ["scheduler", "worker"]);

    // Services present in both sets
    let mut common: Vec<&str> = deployed.intersection(&monitored).copied().collect();
    common.sort();
    println!("Monitored and deployed:     {common:?}");
    assert_eq!(common, ["api", "web"]);

    // All services mentioned across both sets
    let mut all: Vec<&str> = deployed.union(&monitored).copied().collect();
    all.sort();
    println!("All services:               {all:?}");
    assert_eq!(all.len(), 5);
}

Use a Custom Type as a HashMap Key

A type can be a HashMap key or HashSet member when it implements Eq and Hash. When equality is plain field-by-field comparison, #[derive(Hash, PartialEq, Eq)] is enough, as with Coord below.

A manual Hash implementation is needed when equality is custom. The Hash trait works with a generic Hasher abstraction that supplies a mutable state object you write hashed data into. Email treats addresses as equal regardless of letter case, so its Hash must also ignore case: it feeds the lowercased bytes to the hasher. The rule is that a == b must imply hash(a) == hash(b); if the two disagree, equal keys can land in different buckets and lookups silently miss. The assertions at the end check this property.

use std::collections::hash_map::DefaultHasher;
use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher};

#[derive(Debug, Hash, PartialEq, Eq)]
struct Coord {
    x: i32,
    y: i32,
}

#[derive(Debug)]
struct Email(String);

impl PartialEq for Email {
    fn eq(&self, other: &Self) -> bool {
        self.0.eq_ignore_ascii_case(&other.0)
    }
}

impl Eq for Email {}

impl Hash for Email {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for byte in self.0.bytes() {
            state.write_u8(byte.to_ascii_lowercase());
        }
        // Mirrors what `str::hash` does, so a prefix cannot collide with a longer value.
        state.write_u8(0xff);
    }
}

fn hash_of<T: Hash>(value: &T) -> u64 {
    let mut hasher = DefaultHasher::new();
    value.hash(&mut hasher);
    hasher.finish()
}

fn main() {
    let mut grid: HashMap<Coord, &str> = HashMap::new();
    grid.insert(Coord { x: 0, y: 0 }, "origin");
    grid.insert(Coord { x: 3, y: -2 }, "treasure");
    println!("{:?}", grid.get(&Coord { x: 3, y: -2 }));
    assert_eq!(grid.get(&Coord { x: 3, y: -2 }), Some(&"treasure"));

    let mut seen: HashSet<Email> = HashSet::new();
    seen.insert(Email("Ferris@Example.com".to_string()));
    let is_new = seen.insert(Email("ferris@example.COM".to_string()));
    println!("second insert was new: {is_new}");
    assert!(!is_new);
    assert_eq!(seen.len(), 1);

    let a = Email("Ferris@Example.com".to_string());
    let b = Email("FERRIS@example.com".to_string());
    assert_eq!(a, b);
    assert_eq!(hash_of(&a), hash_of(&b));
}

Look Up a Tuple Key Without Cloning

A HashMap<(Email, Coord), V> owns its keys, but HashMap::get only accepts &Q where the key type implements Borrow<Q>. A plain &(Email, Coord) would force the caller to build, and so clone, both halves just to ask a question. (&Email, &Coord) is a different type, and the standard library has no Borrow impl that connects it to (Email, Coord).

The workaround is a small KeyPair trait that both tuple shapes implement. Borrow turns the owned tuple into a dyn KeyPair, and Hash and Eq for that trait object compare the two halves. The get_pair helper casts &(a, b) to &dyn KeyPair once, so callers just pass references and no data is copied.

The trait object’s Hash must feed the hasher exactly what (Email, Coord)::hash does: the first element, then the second. If the orders differ, the lookup hashes to the wrong bucket and misses. This is the same rule as in the previous recipe, applied across a type boundary.

This technique trades complexity for fewer allocations, so it pays off mainly when key halves are heap-allocated, such as String, and lookups are frequent. Every hash and comparison goes through a trait object, and for cheap Copy keys that can be slower than cloning. Two simpler alternatives are worth trying first: nested maps, HashMap<Email, HashMap<Coord, V>>, which take a plain &Email and then a plain &Coord with no extra traits; and the Equivalent trait from the hashbrown crate, which lets a map be queried with any type that compares equal to the key and hashes the same way, without the dyn indirection.

use std::borrow::Borrow;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Debug, Hash, PartialEq, Eq)]
struct Coord {
    x: i32,
    y: i32,
}

#[derive(Debug)]
struct Email(String);

impl PartialEq for Email {
    fn eq(&self, other: &Self) -> bool {
        self.0.eq_ignore_ascii_case(&other.0)
    }
}

impl Eq for Email {}

impl Hash for Email {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for byte in self.0.bytes() {
            state.write_u8(byte.to_ascii_lowercase());
        }
        state.write_u8(0xff);
    }
}

trait KeyPair<A, B> {
    fn first(&self) -> &A;
    fn second(&self) -> &B;
}

impl<A, B> KeyPair<A, B> for (A, B) {
    fn first(&self) -> &A {
        &self.0
    }
    fn second(&self) -> &B {
        &self.1
    }
}

impl<A, B> KeyPair<A, B> for (&A, &B) {
    fn first(&self) -> &A {
        self.0
    }
    fn second(&self) -> &B {
        self.1
    }
}

impl<'a, A, B> Borrow<dyn KeyPair<A, B> + 'a> for (A, B)
where
    A: Eq + Hash + 'a,
    B: Eq + Hash + 'a,
{
    fn borrow(&self) -> &(dyn KeyPair<A, B> + 'a) {
        self
    }
}

impl<A: Hash, B: Hash> Hash for dyn KeyPair<A, B> + '_ {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.first().hash(state);
        self.second().hash(state);
    }
}

impl<A: PartialEq, B: PartialEq> PartialEq for dyn KeyPair<A, B> + '_ {
    fn eq(&self, other: &Self) -> bool {
        self.first() == other.first() && self.second() == other.second()
    }
}

impl<A: Eq, B: Eq> Eq for dyn KeyPair<A, B> + '_ {}

fn get_pair<'m, A, B, V>(map: &'m HashMap<(A, B), V>, a: &A, b: &B) -> Option<&'m V>
where
    A: Eq + Hash,
    B: Eq + Hash,
{
    map.get(&(a, b) as &dyn KeyPair<A, B>)
}

fn main() {
    let mut last_seen: HashMap<(Email, Coord), &str> = HashMap::new();
    last_seen.insert(
        (
            Email("ferris@example.com".to_string()),
            Coord { x: 3, y: -2 },
        ),
        "harbor",
    );

    let email = Email("FERRIS@example.com".to_string());
    let here = Coord { x: 3, y: -2 };
    let elsewhere = Coord { x: 0, y: 0 };

    let hit = get_pair(&last_seen, &email, &here);
    println!("{hit:?}");
    assert_eq!(hit, Some(&"harbor"));

    let miss = get_pair(&last_seen, &email, &elsewhere);
    println!("{miss:?}");
    assert_eq!(miss, None);
}

Process Tasks in Priority Order

Uses BinaryHeap as a max-priority queue: push inserts an item and pop always removes the highest-priority one first. Wrapping items in Reverse turns it into a min-priority queue without a custom comparator.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    // Max-heap: highest priority number is processed first
    let mut queue: BinaryHeap<(u32, &str)> = BinaryHeap::new();
    queue.push((3, "send report"));
    queue.push((1, "check email"));
    queue.push((5, "fix production bug"));
    queue.push((2, "review PR"));

    println!("Max-heap — processing order:");
    while let Some((priority, task)) = queue.pop() {
        println!("  [{priority}] {task}");
    }

    // Min-heap: wrap with Reverse so lowest number is processed first
    let mut min_queue: BinaryHeap<Reverse<(u32, &str)>> = BinaryHeap::new();
    min_queue.push(Reverse((3, "send report")));
    min_queue.push(Reverse((1, "check email")));
    min_queue.push(Reverse((5, "fix production bug")));

    println!("Min-heap — processing order:");
    while let Some(Reverse((priority, task))) = min_queue.pop() {
        println!("  [{priority}] {task}");
    }
}

Sliding-Window Buffer with VecDeque

Maintains a fixed-size window over a stream of values using VecDeque. push_back appends new values and pop_front discards the oldest, keeping memory bounded regardless of input length. with_capacity is optional — VecDeque::new() works fine — but pre-allocating the window size avoids reallocations as the buffer fills up for the first time. zip pairs each original reading with its computed average for display.

use std::collections::VecDeque;

fn sliding_average(values: &[f64], window: usize) -> Vec<f64> {
    let mut buf: VecDeque<f64> = VecDeque::with_capacity(window);
    let mut averages = Vec::with_capacity(values.len());

    for &v in values {
        if buf.len() == window {
            buf.pop_front();
        }
        buf.push_back(v);
        averages.push(buf.iter().sum::<f64>() / buf.len() as f64);
    }
    averages
}

fn main() {
    let readings = [1.0, 2.0, 3.0, 4.0, 5.0];
    let averages = sliding_average(&readings, 3);

    println!("reading  average");
    for (r, a) in readings.iter().zip(&averages) {
        println!("  {r:.1}      {a:.2}");
    }

    assert_eq!(averages[0], 1.0); // window: [1.0]
    assert_eq!(averages[1], 1.5); // window: [1.0, 2.0]
    assert_eq!(averages[2], 2.0); // window: [1.0, 2.0, 3.0]
    assert_eq!(averages[3], 3.0); // window: [2.0, 3.0, 4.0]
    assert_eq!(averages[4], 4.0); // window: [3.0, 4.0, 5.0]
}