On Rust's map entry pattern

You're probably familiar with the straight forward pattern of getting an existing value from a map to modify, or inserting a new value if the key doesn't exist.

let mut counts: HashMap<char, u32> = HashMap::default();

for c in "a string of characters".chars() {
    match counts.get_mut(&c) {
        Some(count) => *count += 1,
        None => {
            counts.insert(c, 1);
        }
    }
}

That's fine, and simple. But it's less efficient than it could be. Both .get_mut() and .insert() internally have to compute the hash value of the key, and check if it exists in the map.

But Rust has a more efficient way to do this. The community seems to often call this the "entry pattern", or "entry interface". It allows you to get the entry for the given key, whether or not it has a value in the map, then either modify the existing value, or insert a new one.

You do this by using the .entry() method on the map. HashMap has it, and BTreeMap does, too. Types outside the standard library may also have it. The serde_json::Map type does, for example.

There are a few ways to use this. The most common are shown as examples in some of those docs. You call methods on the returned Entry type to manipulate the value associated with the key. Here's an example that produces the same result as the one above, but uses the entry pattern to get a mutable reference to the existing value, or a default value (via the .or_default() method).

let mut counts: HashMap<char, u32> = HashMap::default();

for c in "a string of characters".chars() {
    *counts.entry(c).or_default() += 1;
}

If you want to do something different if there's an existing value, the .and_modify() method is useful. You can use .or_insert() when you want to insert value that is not he default for the type (or if the type doesn't implement Default). This example produces the same result as the previous ones.

let mut counts: HashMap<char, u32> = HashMap::default();

for c in "a string of characters".chars() {
    counts.entry(c).and_modify(|count| *count += 1).or_insert(1);
}

There are additional methods available, too. For example, if the value you want to insert has a cost associated with producing it, you can use .or_insert_with(), and provide a closure to produce the value, which will only be called if there isn't already a value for the key. There is also a method that provides your closure with a reference to the key in case you need it to compute the value (.or_insert_with_key()).

There's another way you can use .entry(), as well. There are scenarios where you can't use the methods provided by Entry because of more complicated ownership issues involved in computing the values. Well, Entry is just an enum. You can match on it and manipulate the entry. That's all the methods on Entry are doing, anyway. Here's an example that, again, does the same thing as the examples above, but this time uses Entry manually:

let mut counts: HashMap<char, u32> = HashMap::default();

for c in "a string of characters".chars() {
    match counts.entry(c) {
        Entry::Occupied(mut entry) => *entry.get_mut() += 1,
        Entry::Vacant(entry) => {
            // Note that even though this may look similar to the common pattern,
            // not using `Entry`, this pattern doesn't pass the key again,
            // so this is more efficient.
            entry.insert(1);
        }
    }
}

There you go. You can see these examples run, and mess around with them in the playground.