# HashMap keys & lifetimes

**URL:** <https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899>\
**Category:** help\
**Created:** [August 27, 2020, 11:41am UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899 "2020-08-27T11:41:11Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Emmanuel](https://avatars.discourse-cdn.com/v4/letter/e/3e96dc/32.png) [@Emmanuel](https://users.rust-lang.org/u/Emmanuel)\
**Post date:** [August 27, 2020, 11:41am UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/1 "2020-08-27T11:41:11Z")

</div>

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

```rust
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
}

```

---

<div class="post-metadata">

**Author:** ![nologik](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/nologik/32/23342_2.png) [@nologik](https://users.rust-lang.org/u/nologik)\
**Post date:** [August 27, 2020, 11:54am UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/2 "2020-08-27T11:54:15Z")

</div>

```rust

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.

---

<div class="post-metadata">

**Author:** ![alice](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/alice/32/9777_2.png) [@alice](https://users.rust-lang.org/u/alice)\
**Post date:** [August 27, 2020, 11:56am UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/3 "2020-08-27T11:56:50Z")

</div>

Look here:

```rust
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](https://doc.rust-lang.org/nomicon/subtyping.html), 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.

```rust
#[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);
}

```

---

<div class="post-metadata">

**Author:** ![nologik](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/nologik/32/23342_2.png) [@nologik](https://users.rust-lang.org/u/nologik)\
**Post date:** [August 27, 2020, 11:59am UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/4 "2020-08-27T11:59:30Z")

</div>

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

> [@Perpetual n00b struggling with ownership (again)](https://users.rust-lang.org/t/perpetual-n00b-struggling-with-ownership-again/46920/4):
>
> You're not allowed to use references in structs until you think Rust is easy. They're the evil-hardmode of Rust that will ruin your day. wink Use Box or Arc to store things in structs "by reference". Temporary borrows don't do what you think they do.

---

<div class="post-metadata">

**Author:** ![Emmanuel](https://avatars.discourse-cdn.com/v4/letter/e/3e96dc/32.png) [@Emmanuel](https://users.rust-lang.org/u/Emmanuel)\
**Post date:** [August 27, 2020, 1:28pm UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/5 "2020-08-27T13:28:37Z")

</div>

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,...\>\>.

---

<div class="post-metadata">

**Author:** ![trentj](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/trentj/32/5690_2.png) [@trentj](https://users.rust-lang.org/u/trentj)\
**Post date:** [August 27, 2020, 2:19pm UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/6 "2020-08-27T14:19:47Z")

</div>

You can use [kennytm's trick](https://stackoverflow.com/a/45795699/3650362) of making `Q` a trait object.

On nightly, you have [`raw_entry`](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html#method.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 `Cow`s in your `Key`s 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.

---

<div class="post-metadata">

**Author:** ![drewkett](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/drewkett/32/16805_2.png) [@drewkett](https://users.rust-lang.org/u/drewkett)\
**Post date:** [August 27, 2020, 2:31pm UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/7 "2020-08-27T14:31:07Z")

</div>

> [@Emmanuel](#):
>
> 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.

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.

---

<div class="post-metadata">

**Author:** ![Emmanuel](https://avatars.discourse-cdn.com/v4/letter/e/3e96dc/32.png) [@Emmanuel](https://users.rust-lang.org/u/Emmanuel)\
**Post date:** [August 27, 2020, 2:59pm UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/8 "2020-08-27T14:59:52Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Emmanuel](https://avatars.discourse-cdn.com/v4/letter/e/3e96dc/32.png) [@Emmanuel](https://users.rust-lang.org/u/Emmanuel)\
**Post date:** [August 27, 2020, 3:07pm UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/9 "2020-08-27T15:07:29Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![drewkett](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/drewkett/32/16805_2.png) [@drewkett](https://users.rust-lang.org/u/drewkett)\
**Post date:** [August 27, 2020, 3:28pm UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/10 "2020-08-27T15:28:49Z")

</div>

Ah. Misread your post

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [November 25, 2020, 3:28pm UTC](https://users.rust-lang.org/t/hashmap-keys-lifetimes/47899/11 "2020-11-25T15:28:52Z")

</div>

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.