Insert into map, only clone key if needed

help
1

I have a HashMap that contains keys that are expensive to clone. I have access to a lot of references to the keys. I want to access the values they map to and modify them. If they don't exist, I am willing to pay the price to clone the reference and insert it into the map. Is there a straightforward way to do this without needing to clone the keys every time?

I've read similar posts, and some have recommended directly using the hashbrown crate. If you use hashbrown::HashMap with String keys, then using entry_ref with String/&String/&str works out of the box—but only because String implements From<&str>. If my custom Key type doesn't implement From<&Key> but does implement Clone, I should still be able to do this.

I was able to get this to work but only by using the "raw" API. Am I missing something in the std::collections::HashMap or the hashbrown::HashMap "normal" API? Or is the answer just "implement From<&Key>? It would be nice to be able to do this even if you didn't have access to the Key type. It seems like this is the kind of thing that would be generally useful. If others agree, I could create an issue/submit a PR to the hashbrown crate.

Here is a link to a playground that demonstrates the issue. I'll copy and paste the code here as well:

use hashbrown::HashMap;
use std::hash::Hash;

// Implements Clone, does _NOT_ implement From<&Key>
#[derive(Eq, PartialEq, Hash, Clone, Debug)]
struct Key(String);

fn main() {
    let mut map = HashMap::<Key, i32>::new();
    let foo_owned = Key("foo".to_string());
    let bar_owned = Key("boo".to_string());
    map.insert(foo_owned.clone(), 3);
    map.insert(bar_owned.clone(), 2);
    let foo_ref = &foo_owned;

    // Does not work, &Key is not Key
    // map.entry(&foo);

    // Cloning works
    map.entry(foo_ref.clone()).or_insert_with(|| 4);
    *map.entry(foo_ref.clone()).or_insert_with(|| 4) *= 5;

    // Works, but useless because...
    map.entry_ref(foo_ref);

    // error[E0277]: the trait bound `Key: From<&Key>` is not satisfied
    // map.entry_ref(&foo).or_insert_with(|| 4);

    // Seems verbose, needs to use "raw entry" API
    *map.raw_entry_mut()
        .from_key(foo_ref)
        .or_insert_with(|| (foo_ref.clone(), 4))
        .1 *= 5;

    // I can write a helper method?
    fn get_mut_or_insert_with<'a, K, V, F>(
        map: &'a mut HashMap<K, V>,
        key: &K,
        create: F,
    ) -> &'a mut V
    where
        K: Eq + Hash + Clone,
        F: FnOnce() -> V,
    {
        map.raw_entry_mut()
            .from_key(key)
            .or_insert_with(|| (key.clone(), create()))
            .1
    }
    *get_mut_or_insert_with(&mut map, foo_ref, || 4) *= 5;

    println!("{:?}", map);
}
1 Like
2

Is there a problem with using the raw API?

It's more boilerplate, but you can newtype it.

#[derive(Hash)]
struct Query<T>(T);

impl From<&Query<&Key>> for Key {
    fn from(query: &Query<&Key>) -> Self {
        query.0.clone()
    }
}

impl Equivalent<Key> for Query<&Key> {
    fn equivalent(&self, key: &Key) -> bool {
        self.0.equivalent(key)
    }
}

// ...
    map.entry_ref(&Query(foo_ref))
        .or_insert_with(|| 4);

(Or use a newtype for your key type.)

4 Likes
3

I would stay with using raw entry API, but move get_mut_or_insert_with helper function into an extension trait. For example:

use hashbrown::HashMap;
use std::hash::Hash;

trait HashMapExt<K, V> {
    fn get_mut_or_insert_with<'a, F>(&'a mut self, key: &K, create: F) -> &'a mut V
    where
        K: Eq + Hash + Clone,
        F: FnOnce() -> V;
}

impl<K, V> HashMapExt<K, V> for HashMap<K, V> {
    fn get_mut_or_insert_with<'a, F>(&'a mut self, key: &K, create: F) -> &'a mut V
    where
        K: Eq + Hash + Clone,
        F: FnOnce() -> V,
    {
        self.raw_entry_mut()
            .from_key(key)
            .or_insert_with(|| (key.clone(), create()))
            .1
    }
}

#[derive(Eq, PartialEq, Hash, Clone, Debug)]
struct Key(String);

fn foo(mut map: HashMap<Key, i32>, key: Key) {
    *map.get_mut_or_insert_with(&key, || 4) *= 5;
}
1 Like
4

I guess not :person_shrugging: I guess I was thinking of it as an "internal" API that might be subject to change, but after looking with a fresh set of eyes that doesn't seem to be the case.

Yeah this is a good use case for a newtype wrapper. Thanks for the suggestion!

5

This is pretty much what I did! Glad to hear that someone else also thinks this a good idea :upside_down_face:

1 Like