Hash Tables

Frequency Count

Walk a sequence and count occurrences of each value in a map. Classic "get current count, add one, write back" loop.

Algorithm

Canonical input ["fig", "apple", "fig", "pear", "apple", "fig"] produces the final map {fig: 3, apple: 2, pear: 1}.

Basic Implementation

basic.rs 
use std::collections::HashMap;

fn main() {
	let words = ["fig", "apple", "fig", "pear", "apple", "fig"];
	let mut counts: HashMap<&str, i32> = HashMap::new();
	let mut order: Vec<&str> = Vec::new();
	for i in 0..words.len() {
		let word = words[i];
		if !counts.contains_key(word) {
			order.push(word);
			counts.insert(word, 1);
		} else {
			let prev = counts[word];
			counts.insert(word, prev + 1);
		}
	}
	print!("{{");
	for i in 0..order.len() {
		if i > 0 {
			print!(", ");
		}
		let key = order[i];
		print!("{}: {}", key, counts[key]);
	}
	println!("}}");
}

Complexity

  • Time: O(n) average with HashMap<&str, i32>.
  • Space: O(k) where k is the number of distinct keys.

Implementation notes

  • Rust: let mut counts: HashMap<&str, i32> = HashMap::new(); is the idiomatic map; the counts.contains_key(word) predicate plus an explicit insert keeps the lesson on the read-or-default path without hiding it behind entry(...).or_insert(...).
  • The auxiliary order vector preserves first-seen order so the final printout is deterministic — Rust's HashMap iteration order is intentionally unspecified.
  • The replay renders the map as a list of key/value rows in first-seen order and animates the count increment on each frame.
get-or-default A first-time `word` triggers the "default" branch: append to `order` and set `counts.insert(word, 1)`. A repeat read-modify-writes `counts.insert(word, prev + 1)`.
first-seen order Keys are tracked in `order` (a `Vec<&str>`) to keep the printout deterministic; Rust's `HashMap` iteration order is unspecified by design.