Hash maps and sets in Rust

Think of the contact list on your phone. You type a name and the number appears. You never scroll through every contact from the top, because the phone jumps straight to the right one.

That is a hash map. It stores pairs. Each pair is a key and a value: a student's roll number and their name, or a word and how many times it appears. You give the map a key, and it gives you the matching value back, without looking through every pair.

Other languages call this a dictionary, an object or a map. A hash set is the same machine with keys only and no values. It answers one question quickly: "is this thing in here?"

Reach for a hash map when you need to look things up by something other than position, or when you need to count, group or remember things. It is the most useful single structure for solving interview problems, because it turns a slow search through a list into a quick lookup.

A hash map keeps its pairs in a row of buckets, which are small containers numbered from 0. To decide which bucket a key belongs in, it runs the key through a hash function. A hash function turns any key into a number, and the same key always gives the same number. The map reduces that number to a bucket number, and the pair goes there.

To find a key later, the map does the same thing: hash the key, jump straight to that bucket, and look only inside it. It does not touch the other buckets.

Two different keys can land in the same bucket. This is called a collision, and it is normal. The picture shows it: keys 3 and 11 both end up in bucket 3. The simple answer, used here, is for each bucket to hold a short list of pairs, and to compare keys inside the bucket to find the right one. This is called chaining.

As long as the buckets stay short, lookups are quick. A real hash map watches how full it is and, when the buckets get crowded, grows the row of buckets and moves the pairs to spread them out. That is why the cost is O(1) on average and not always. A map where every key collides would be one long list.

Remember: a hash map finds things by jumping to one bucket, not by searching the whole collection.

Two things follow from this design. A key must be able to be hashed and compared for equality. And the map does not remember the order you added things, so never rely on the order a hash map gives you back.

This map goes from i32 keys to i32 values. It has eight buckets and never grows, so it only shows the idea.

/// A small hash map from `i32` to `i32`: eight buckets, no resizing.
/// Each bucket is a short list of the pairs that hashed to it.
pub struct TinyMap {
    buckets: Vec<Vec<(i32, i32)>>,
    len: usize,
}

impl TinyMap {
    pub fn new() -> Self {
        TinyMap {
            buckets: vec![Vec::new(); 8],
            len: 0,
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// The hash: turns a key into a bucket number from 0 to 7.
    /// `rem_euclid` keeps the answer positive even for a negative key.
    fn bucket_of(&self, key: i32) -> usize {
        key.rem_euclid(self.buckets.len() as i32) as usize
    }

    /// Stores a pair. If the key was already there, its old value is returned.
    pub fn insert(&mut self, key: i32, value: i32) -> Option<i32> {
        let b = self.bucket_of(key);
        for pair in &mut self.buckets[b] {
            if pair.0 == key {
                return Some(std::mem::replace(&mut pair.1, value));
            }
        }
        self.buckets[b].push((key, value));
        self.len += 1;
        None
    }

    /// Finds a key's value by looking only inside its own bucket.
    pub fn get(&self, key: i32) -> Option<i32> {
        self.buckets[self.bucket_of(key)]
            .iter()
            .find(|pair| pair.0 == key)
            .map(|pair| pair.1)
    }

    /// Removes a key and returns its value.
    pub fn remove(&mut self, key: i32) -> Option<i32> {
        let b = self.bucket_of(key);
        let bucket = &mut self.buckets[b];
        let at = bucket.iter().position(|pair| pair.0 == key)?;
        self.len -= 1;
        Some(bucket.swap_remove(at).1)
    }

    /// How many pairs sit in each bucket. More than one means a collision.
    pub fn bucket_sizes(&self) -> Vec<usize> {
        self.buckets.iter().map(|bucket| bucket.len()).collect()
    }
}

impl Default for TinyMap {
    fn default() -> Self {
        Self::new()
    }
}

Go through it in order.

• buckets is a Vec of Vecs. Each inner Vec is a bucket holding (key, value) pairs, and len counts all the pairs.
• bucket_of is the hash. It takes the key's remainder after dividing by the number of buckets, so every key lands in a bucket from 0 to 7. rem_euclid is used rather than % because -1 % 8 is -1 in Rust, which is not a valid bucket, while (-1).rem_euclid(8) is 7.
• insert looks in the key's bucket. If the key is already there, std::mem::replace swaps in the new value and returns the old one. Otherwise it pushes a new pair.
• get searches only inside the one bucket for a matching key.
• remove finds the pair's position and takes it out with swap_remove, which fills the gap with the last pair instead of shifting everything. The order inside a bucket doesn't matter, so that is fine.
• bucket_sizes is only here so you can see collisions.

Here it is in use. The Playground link on the code above runs this.

let mut map = TinyMap::new();
map.insert(3, 30);
map.insert(11, 110); // 11 % 8 is 3, the same bucket as 3: a collision
map.insert(-1, 70); // rem_euclid puts -1 in bucket 7

assert_eq!(map.get(3), Some(30)); // both are found, even sharing a bucket
assert_eq!(map.get(11), Some(110));
assert_eq!(map.get(4), None);
assert_eq!(map.insert(3, 31), Some(30)); // replaces, returns the old value
println!("{:?}", map.bucket_sizes());
assert_eq!(map.bucket_sizes(), [0, 0, 0, 2, 0, 0, 0, 1]);
assert_eq!(map.remove(11), Some(110));
assert_eq!(map.len(), 2);

Keys 3 and 11 share bucket 3, and both are still found, because get compares the keys themselves and not just the bucket. The key -1 goes to bucket 7. The printed bucket sizes show the collision as a 2.

The standard library's HashMap is this idea, finished: it grows when needed, it takes any key type that can be hashed and compared, and it is carefully tested.

use std::collections::HashMap;

let mut ages = HashMap::new();
ages.insert("Asha", 20);
ages.insert("Ravi", 22);

assert_eq!(ages.get("Asha"), Some(&20));
assert_eq!(ages.get("Meera"), None);
assert!(ages.contains_key("Ravi"));
assert_eq!(ages.insert("Asha", 21), Some(20)); // replaced: old value returned
assert_eq!(ages.remove("Ravi"), Some(22));
assert_eq!(ages.len(), 1);

insert returns the old value if the key was already there. get returns an Option<&V>, a borrowed look at the value, and None if the key is missing. The key you pass to get is a reference, and you can look up a String key with a &str.

Counting is the job you will do most. The first idea is to check whether the key exists, then add or insert. Rust has a better tool, the entry API:

use std::collections::HashMap;

let text = "to be or not to be";
let mut counts: HashMap<&str, i32> = HashMap::new();
for word in text.split_whitespace() {
    *counts.entry(word).or_insert(0) += 1; // start at 0 if new, then add 1
}

assert_eq!(counts["to"], 2);
assert_eq!(counts["or"], 1);
assert_eq!(counts.get("maybe"), None);

// The order of a HashMap is not defined, so sort before printing.
let mut pairs: Vec<(&str, i32)> = counts.into_iter().collect();
pairs.sort();
println!("{:?}", pairs);
assert_eq!(pairs, [("be", 2), ("not", 1), ("or", 1), ("to", 2)]);

counts.entry(word) finds the slot for that key, whether or not it has a value yet. or_insert(0) fills the slot with 0 if it was empty, and in both cases it returns a mutable reference to the value. The * in *... += 1 writes through that reference. The key is looked up once, not twice, and there is no way to forget a case.

Notice how the example ends. It sorts before printing, because a HashMap does not promise any order. If you need keys in order, lesson 9 introduces BTreeMap.

The entry API has more forms:

use std::collections::HashMap;

let mut groups: HashMap<usize, Vec<&str>> = HashMap::new();
for word in ["cat", "ox", "dog", "emu"] {
    // `or_default` makes an empty Vec the first time a length is seen.
    groups.entry(word.len()).or_default().push(word);
}
assert_eq!(groups[&3], ["cat", "dog", "emu"]);
assert_eq!(groups[&2], ["ox"]);

let mut score = HashMap::new();
score.insert("Asha", 10);
score.entry("Asha").and_modify(|s| *s += 5).or_insert(0); // exists: add 5
score.entry("Ravi").and_modify(|s| *s += 5).or_insert(0); // new: insert 0
assert_eq!(score["Asha"], 15);
assert_eq!(score["Ravi"], 0);

or_default() fills in the type's default value, which for a Vec is an empty one, so it is perfect for grouping. and_modify runs only if the key exists, and or_insert covers the case where it doesn't.

A HashSet is a map with only keys.

use std::collections::HashSet;

let mut seen = HashSet::new();
assert!(seen.insert(4)); // true: it was new
assert!(seen.insert(9));
assert!(!seen.insert(4)); // false: already there, nothing changed
assert!(seen.contains(&9));
assert_eq!(seen.len(), 2);

let evens: HashSet<i32> = [2, 4, 6].into_iter().collect();
let small: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();
let mut both: Vec<i32> = evens.intersection(&small).copied().collect();
both.sort();
assert_eq!(both, [2, 4]);

insert returns true if the value was new and false if it was already there, which makes de-duplicating and "have I seen this?" checks very short. Sets also have operations like intersection, union and difference.

Finally, your own types can be keys if they can be hashed and compared:

use std::collections::HashMap;

// A key needs `Hash` (turn it into a number) and `Eq` (tell two keys apart).
#[derive(Debug, Hash, PartialEq, Eq)]
struct Point {
    x: i32,
    y: i32,
}

let mut names = HashMap::new();
names.insert(Point { x: 0, y: 0 }, "origin");
names.insert(Point { x: 1, y: 0 }, "east");

assert_eq!(names.get(&Point { x: 1, y: 0 }), Some(&"east"));
assert_eq!(names.get(&Point { x: 5, y: 5 }), None);

#[derive(Hash, PartialEq, Eq)] asks the compiler to write the code for you. A rule to keep: if two keys are equal, they must hash to the same number, and the derive guarantees that. By default, Rust's hash function is chosen to be hard to attack with keys picked to collide. It is a little slower than the simplest hash functions, and that is a good trade for most programs.

"Average" means that over many operations on ordinary keys, each one takes a constant number of steps, even though one unlucky case could take longer. In practice, a HashMap is the way to turn an O(n) search into an O(1) lookup, at the cost of extra memory. Compare it with a Vec, where contains has to look at every item.

All three have a slow answer that compares many things with each other, and a quick answer that remembers something as it goes. The quick answers use a map or a set to do the remembering.

pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    todo!("two different positions whose values add up to target")
}

pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    use std::collections::HashMap;

    let mut seen: HashMap<i32, usize> = HashMap::new(); // value -> where we saw it
    for (i, &n) in nums.iter().enumerate() {
        let needed = target - n;
        if let Some(&j) = seen.get(&needed) {
            return Some((j, i));
        }
        seen.insert(n, i);
    }
    None
}

pub fn group_anagrams(words: &[&str]) -> Vec<Vec<String>> {
    todo!("put words made of the same letters into the same group")
}

pub fn group_anagrams(words: &[&str]) -> Vec<Vec<String>> {
    use std::collections::HashMap;

    let mut groups: HashMap<String, Vec<String>> = HashMap::new();
    for &word in words {
        // Words made of the same letters have the same letters once sorted.
        let mut letters: Vec<char> = word.chars().collect();
        letters.sort_unstable();
        let key: String = letters.into_iter().collect();
        groups.entry(key).or_default().push(word.to_string());
    }
    groups.into_values().collect()
}

pub fn longest_consecutive(nums: &[i32]) -> usize {
    todo!("the longest run of values that go up by one: 4, 5, 6, 7")
}

pub fn longest_consecutive(nums: &[i32]) -> usize {
    use std::collections::HashSet;

    let set: HashSet<i32> = nums.iter().copied().collect();
    let mut best = 0;
    for &start in &set {
        if set.contains(&(start - 1)) {
            continue; // not the start of a run: something sits just below it
        }
        let mut end = start;
        while set.contains(&(end + 1)) {
            end += 1;
        }
        best = best.max((end - start + 1) as usize);
    }
    best
}

If you only get good at one structure for interviews, make it this one. A few habits help.

• Ask "can I remember something?" When a first idea compares every item with every other, try a map or a set that remembers what has been seen. This turns O(n squared) into O(n), and it is the idea behind all three problems here.
• Know the patterns. Counting how often things appear (the entry API), looking up a partner or complement (problem 1), grouping by a shared key (problem 2), and checking for membership (problem 3) cover a large share of questions.
• Ask about duplicates and the key type. Can values repeat? Are the keys small numbers, where a plain array might do, or strings? Do you need the answer in order?
• Be honest about "O(1)". Say "O(1) on average". A strong answer adds that the worst case is O(n) if many keys collide, and that the map uses extra space to buy the speed.
• Remember that order is not kept. A HashMap returns items in no useful order. If you need sorted keys, say you would use a BTreeMap instead.
• In Rust, use the entry API. Writing *counts.entry(x).or_insert(0) += 1 rather than checking and inserting separately shows you know the idiom, and it does one lookup instead of two.

Made by VeraStack Labs