HashMap keys & lifetimes

help
#1

I have encountered a problem trying to deal with keys with a specific lifetimes in a HashMap.
I have isolated the relevant parts of a HashMap in a simplified MyHashMap in the following code.
I don't understand why the compiler has no problem with the get() method but complains when calling get_mut().

use std::borrow::Borrow;

#[derive(Debug, Clone, Eq, Hash, PartialEq)]
struct Key<'a> {
    s: &'a str,
    // more irrelevant fields
}

struct MyHashMap<K, V> {
    entries: Vec<(K, V)>,
}

impl<K, V> MyHashMap<K, V> {
    fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        Q: ?Sized,
        K: Borrow<Q>,
    {
        todo!()
    }

    fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        Q: ?Sized,
        K: Borrow<Q>,
    {
        todo!()
    }

    // Trying to be more explicit about lifetimes doesn't help.
    fn get_mut2<'a, Q>(&'a mut self, key: &Q) -> Option<&'a mut V>
    where
        Q: ?Sized,
        K: Borrow<Q>,
    {
        todo!()
    }
}

fn foo<'a>(map: &MyHashMap<Key<'static>, i32>, key: &Key<'a>) {
    map.get(&key);  // Ok
    map.get_mut(&key); // Error: lifetime mismatch
    //map.get_mut2(&key); // Error: lifetime mismatch
    // also, with std HashMap:  map[&key]; gives the same error: lifetime mismatch
}
#2 

fn foo<'a: 'static>(map: &mut MyHashMap<Key<'static>, i32>, key: &Key<'a>) {
    map.get(&key);  // Ok
    map.get_mut(&key); // Error: lifetime mismatch
    //map.get_mut2(&key); // Error: lifetime mismatch
    // also, with std HashMap:  map[&key]; gives the same error: lifetime mismatch
}

change the function to that, and it'l compile. I state that the lifetime 'a lasts at least as long as the static lifetime. However:

I really think you should replace all the 'a lifetimes with 'static since your keys reference static-lifetimed &str's.

#3

Look here:

fn foo<'a>(map: &MyHashMap<Key<'static>, i32>, key: &Key<'a>) {

The hash map has key type Key<'static>, but your key has type Key<'a>. This is not the same type, hence the type mismatch.

As for the reason it works with get, it's rather subtle. It's because HashMap<Key<'static>, i32> is a subtype of HashMap<Key<'a>, i32> since 'a is shorter, but due to something known as variance, you can only shorten the lifetime behind an immutable reference, not a mutable one.

As for solving your problem, I recommend not using references in structs.

#[derive(Debug, Clone, Eq, Hash, PartialEq)]
struct Key {
    s: String,
    // more irrelevant fields
}

fn foo(mut map: MyHashMap<Key, i32>, key: &Key) {
    map.get(key);
    map.get_mut(key);
}
1 Like
#4

Yeah, go with String's like alice said to avoid lifetimes. You should exercise @kornel's axiom:

#5

Ok, the variance argument makes sense.
get_mut() doesn't actually need mutable references to the keys inside the map, but the compiler can not know that from the function signature.

As for using Strings instead of references in my keys, that's what I'm trying to avoid. My keys are actually made of several strings, that can be quite large. I need hundreds of thousands of get()/get_mut() accesses, and I don't want useless string copies for each access.
Sadly, since Borrow::borrow() needs to return a reference, I can't have e.g. a Key(String,String) implementing Borrow returning some KeyRef(&str, &str).
I guess I could use an unsafe hack with lifetimes since the key I use for get_mut() doesn't really need to live beyond the get_mut() call.
I can't think of a safe solution that doesn't involve writing a custom hashmap. Or maybe maybe I could make a wrapper for some HashMap<String,HashMap<String,...>>.

#6

You can use kennytm's trick of making Q a trait object.

On nightly, you have raw_entry. The documentation mentions this as one of the use cases:

This is useful for

  • Hash memoization
  • Using a search key that doesn't work with the Borrow trait
  • Using custom comparison logic without newtype wrappers

I'm not super familiar with the API, but you probably need to use the map's hasher method to get a Hasher that can hash the Key, then use raw_entry().from_hash(...) with the hash and a function that compares Key to the real key type (KeyOwned?) Complicated, but this is the only option that probably has no runtime overhead.

A third option that might work, depending on your API: put Cows in your Keys so they can either be owned or borrowed transparently. Then the ones inside the map can be 'static (subtyped as 'a when the map is indexed) and the ones you create for lookup purposes can be of arbitrary lifetime.

#7

It depends on what your doing with it, but HashMap<String,String> will not actually copy the string data on a get(..) lookup for example. As long as you're not cloning the data explicitly, the strings can be moved in and out of the HashMap with only copying pointer/length/capacity and not the string data.

#8

The raw_entry api seems to be exactly what I need, thanks!

Cow doesn't solve the problem by itself : my real keys actually use Cow instead of &str, but the lifetime problem is the same if I use lookup keys with non static lifetimes for a hashmap with static keys.

#9

HashMap<String, ...> doesn't copy on a get/get_mut, but with several strings, e.g. HashMap<(String,String),...> I have to clone to use get() from a (&str, &str) pair.
But the raw_entry api trentj suggested should work fine without cloning.

#10

Ah. Misread your post