CODEWITHSUNDEEP
hashmaprustlookup
Yusuke Shinyama
Yusuke Shinyama

Reputation: 2063

How to lookup from and insert into a HashMap efficiently?

I'd like to do the following:

How to do this efficiently? Naturally I thought I could use match:

use std::collections::HashMap;

// This code doesn't compile.
let mut map = HashMap::new();
let key = "foo";
let values: &Vec<isize> = match map.get(key) {
    Some(v) => v,
    None => {
        let default: Vec<isize> = Vec::new();
        map.insert(key, default);
        &default
    }
};

When I tried it, it gave me errors like:

error[E0502]: cannot borrow `map` as mutable because it is also borrowed as immutable
  --> src/main.rs:11:13
   |
7  |     let values: &Vec<isize> = match map.get(key) {
   |                                     --- immutable borrow occurs here
...
11 |             map.insert(key, default);
   |             ^^^ mutable borrow occurs here
...
15 | }
   | - immutable borrow ends here

I ended up with doing something like this, but I don't like the fact that it performs the lookup twice (map.contains_key and map.get):

// This code does compile.
let mut map = HashMap::new();
let key = "foo";
if !map.contains_key(key) {
    let default: Vec<isize> = Vec::new();
    map.insert(key, default);
}
let values: &Vec<isize> = match map.get(key) {
    Some(v) => v,
    None => {
        panic!("impossiburu!");
    }
};

Is there a safe way to do this with just one match?

Upvotes: 206

Views: 78421

Answers (3)

Daniil Fajnberg
Daniil Fajnberg

Reputation: 18388

Just to present an alternative to the Entry solution in @huon's excellent answer, you could do this in two steps using the relatively new try_insert method, which only inserts the value, if the key is not yet occupied.

let _ = map.try_insert(key, Vec::new());  // May or may not insert the empty vector.
let values = map.get_mut(key).unwrap();   // Guaranteed to be occupied now.

(Full Playground example here.)

As of today, the try_insert method is still available in nightly Rust only, behind the map_try_insert feature gate.

Ironically, it is currently implemented using the Entry API itself. Though in OP's case I would probably prefer using entry directly with or_default as in the accepted answer myself.

Upvotes: 1

huon
huon

Reputation: 102006

The entry API is designed for this. In manual form, it might look like

let values = match map.entry(key) {
    Entry::Occupied(o) => o.into_mut(),
    Entry::Vacant(v) => v.insert(default),
};

One can use the briefer form via Entry::or_insert_with:

let values = map.entry(key).or_insert_with(|| default);

If default is already computed, or if it's OK/cheap to compute even when it isn't inserted, you can use Entry::or_insert:

let values = map.entry(key).or_insert(default);

If the HashMap's value implements Default, you can use Entry::or_default, although you may need to provide some type hints:

let values = map.entry(key).or_default();

Upvotes: 268

Daniel
Daniel

Reputation: 768

I've used huon's answer and implemented it as a trait:

use std::collections::HashMap;
use std::hash::Hash;

pub trait InsertOrGet<K: Eq + Hash, V: Default> {
    fn insert_or_get(&mut self, item: K) -> &mut V;
}

impl<K: Eq + Hash, V: Default> InsertOrGet<K, V> for HashMap<K, V> {
    fn insert_or_get(&mut self, item: K) -> &mut V {
        return match self.entry(item) {
            std::collections::hash_map::Entry::Occupied(o) => o.into_mut(),
            std::collections::hash_map::Entry::Vacant(v) => v.insert(V::default()),
        };
    }
}

Then I can do:

use crate::utils::hashmap::InsertOrGet;

let new_or_existing_value: &mut ValueType = my_map.insert_or_get(my_key.clone());

Upvotes: 3

Related Questions