Stuck with querying a hashmap

#1

Code:

#[derive(Eq, PartialEq, Hash)]
enum Key {
    String(String),
    Bytes(Vec<u8>),
}

enum KeyRef<'a> {
    String(&'a str),
    Bytes(&'a [u8]),
}

fn query(map: &HashMap<Key, u32>, key: KeyRef) -> Option<u32> {
    // how to do it without allocating?
}

I tried various approaches, the only one I found working is to implement:

impl Borrow<str> for Key { ... }
impl Borrow<[u8]> for Key { ... }

Which is not safe, because Borrow would panic if used with the wrong enum variant, and also the hash of Key must not include an enum discriminator.

Maybe something else is possible?

#2

Instead of having a key which is either a String or some bytes, what about just using a Vec<u8> as your key then calling some_string.as_bytes() when you want to do a lookup with a string?

#3

This is just simplied example of what I actually wanted to do, in my real use case enum has not just string and bytes.

However, now I think that maybe I can instead create multiple maps:

struct MyMaps {
  string_map: HashMap<String, u32>,
  bytes_map: HashMap<Vec<u8>, u32>,
}

and query different map depending on the variant. Thanks!

1 Like
#4

Another solution is to use the indexmap crate, and impl Equivalent<Key> for KeyRef.

1 Like
#5

You can define a trait AsKeyRef, and then implement Borrow<dyn AsKeyRef> for Key:


pub trait AsKeyRef {
    fn as_key_ref(&self)->KeyRef<'_>;
}

impl<'a> PartialEq for dyn AsKeyRef+'a {
    fn eq(&self, other:&Self)->bool { self.as_key_ref() == other.as_key_ref() }
}

impl<'a> Eq for dyn AsKeyRef+'a {}

impl<'a> Hash for dyn AsKeyRef+'a {
    fn hash<H:Hasher>(&self, state: &mut H) { self.as_key_ref().hash(state); }
}

impl<'a> Borrow<dyn AsKeyRef +'a> for Key {
    fn borrow(&self)->&(dyn AsKeyRef + 'a) { self }
}

fn query<'a>(map: &HashMap<Key, u32>, key: KeyRef<'a>) -> Option<u32> {
    // how to do it without allocating?
    map.get(&key as &dyn AsKeyRef).copied()
}

(Playground)

3 Likes
Compare struct of owned with struct of references?
#6

Thank you very much! I tried to do something similar, my mistake was writing:

impl Hash for dyn AsKeyRef { ... }

instead of

impl<'a> Hash for dyn AsKeyRef + 'a { ... }

(I did not even know the latter is possible)

and Rust complained:

72 |     map.get(&key as &dyn AsKeyRef).cloned()
   |         ^^^ lifetime `'static` required