How to lookup from and insert into a HashMap efficiently?

Question

I'd like to do the following:

Lookup a Vec for a certain key, and store it for later use.
If it doesn't exist, create an empty Vec for the key, but still keep it in the variable.

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?

Shepmaster · Accepted Answer · 2022-04-06 19:47:49Z

273

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();

edited Apr 6, 2022 at 19:47

Shepmaster

440k116 gold badges1.3k silver badges1.5k bronze badges

answered Feb 14, 2015 at 4:41

huon

104k24 gold badges239 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Yusuke Shinyama Over a year ago

Thanks for a swift anser! Now I've learned I should look into a little deep down to the documents.

Pascalius Over a year ago

the issue with entry() is, that you always have to clone the key, is there a way to avoid this?

kbolino Over a year ago

@Pascalius you could make your key type &T (if the keys outlive the map, e.g. static strings) or Rc<T> instead of T -- but it's not pretty in either case

Chris Beck Over a year ago

@Pascalius: you can use v.key() in the expression for default, and then it will get a reference to the key as it exists in the hashmap, so you may avoid a clone this way

Bogdan Mircea Over a year ago

@Pascalius Note that since 1.50 there's or_insert_with_key

Shepmaster · Accepted Answer · 2022-04-06 19:40:15Z

3

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());

edited Apr 6, 2022 at 19:40

Shepmaster

440k116 gold badges1.3k silver badges1.5k bronze badges

answered Feb 27, 2021 at 10:14

Daniel

8081 gold badge7 silver badges23 bronze badges

1 Comment

Sarfaraz Nawaz Over a year ago

Why don't you use my_map.entry(my_key).or_default(); instead? You dont need this trait.

Daniel Fainberg · Accepted Answer · 2024-01-02 19:30:40Z

1

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.

answered Jan 2, 2024 at 19:30

Daniel Fainberg

20.1k3 gold badges43 silver badges80 bronze badges

Collectives™ on Stack Overflow

How to lookup from and insert into a HashMap efficiently?

3 Answers 3

5 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related