Hash Maps and Hash Sets

Frequency Counting

Counting the occurrences of items in a sequence (a histogram or frequency table) is one of the most common applications of HashMap<K, usize> and the Entry API.

Idiomatic Single-Lookup Frequency Counter

The canonical one-line pattern for incrementing a key's count in a HashMap is:

*counts.entry(item).or_insert(0) += 1;
  1. counts.entry(item) hashes item and locates its bucket in 1 probe.
  2. .or_insert(0) initializes the bucket to 0 if this is the first time item has been seen, and returns &mut usize.
  3. *... += 1 dereferences the &mut usize and increments the counter in place.
use std::collections::HashMap;

fn main() {
    let text = "to be or not to be that is the question";
    let mut word_counts: HashMap<&str, usize> = HashMap::new();

    for word in text.split_whitespace() {
        *word_counts.entry(word).or_insert(0) += 1;
    }

    // Sort by (descending count, ascending word) for deterministic display:
    let mut sorted: Vec<(&str, usize)> = word_counts.into_iter().collect();
    sorted.sort_unstable_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(b.0)));

    for (word, count) in &sorted[..4] {
        println!("{word:<8} -> {count}");
    }
}

be       -> 2
to       -> 2
is       -> 1
not      -> 1

Functional Frequency Counting in an Iterator Pipeline (fold)

You can also express frequency counting inside a functional iterator chain using .fold():

use std::collections::HashMap;

fn char_frequencies(s: &str) -> HashMap<char, usize> {
    s.chars()
        .filter(|c| !c.is_whitespace())
        .fold(HashMap::new(), |mut acc, ch| {
            *acc.entry(ch).or_insert(0) += 1;
            acc
        })
}

fn main() {
    let freqs = char_frequencies("abracadabra");
    println!("'a' count: {}, 'b' count: {}, 'r' count: {}", freqs[&'a'], freqs[&'b'], freqs[&'r']);
}

'a' count: 5, 'b' count: 2, 'r' count: 2

Avoiding Clones When Counting Owned Keys (String)

When your map owns String keys (HashMap<String, usize>) and you are counting borrowed &str tokens from an input stream, calling map.entry(token.to_owned()) allocates a new String on every token, even when that word is already in the map!

To allocate a String only the first time a distinct word is encountered, check get_mut(token) first and fall back to insert(token.to_owned(), 1):

use std::collections::HashMap;

fn count_words_minimal_allocs(tokens: &[&str]) -> HashMap<String, usize> {
    let mut counts: HashMap<String, usize> = HashMap::new();

    for &token in tokens {
        if let Some(count) = counts.get_mut(token) {
            // Fast path on existing word: zero String allocation!
            *count += 1;
        } else {
            // Cold path on new word: allocates String once
            counts.insert(token.to_owned(), 1);
        }
    }
    counts
}

fn main() {
    let stream = ["rust", "fast", "rust", "safe", "rust"];
    let counts = count_words_minimal_allocs(&stream);
    println!("'rust' count: {}", counts["rust"]);
}

'rust' count: 3