How do I create a HashMap with type erased keys?

It seems like I could create a Hasher (e.g. RandomState), use that to manually calculate hash values, then store the u64 result in a HashMap<u64, _> but that seems kind of overly complex.

Unfortunately that’s overly simple – since a hash function discards some information, hash tables don’t just work on hashes, they also need the original key to compare it with the key you’re inserting or looking for. This is necessary to handle the case when two keys produce the same hash, which is both possible and allowed.

Having said that, you can implement Python-style hash tables with heterogeneous keys in Rust, but you’ll need to box the keys, i.e. use Box<dyn Key> as the type-erased key, with Key being a trait you define for all concrete types you want to use as the hash key. In particular, you’ll need to:

define the Key trait that specifies how to compare and hash the actual keys;
(optionally) provide a blanket implementation of that trait for types that are themselves Hash and Eq so the user doesn’t need to do that for every type manually;
define Eq and Hash for Box<dyn Key> using the methods the trait provides, making Box<dyn Key> usable as key in std::collections::HashMap.

The Key trait could be defined like this:

trait Key {
    fn eq(&self, other: &dyn Key) -> bool;
    fn hash(&self) -> u64;
    // see https://stackoverflow.com/a/33687996/1600898
    fn as_any(&self) -> &dyn Any;
}

And here is a blanket implementation of Key for any type that is Eq and Hash:

use std::any::{Any, TypeId};
use std::collections::{HashMap, hash_map::DefaultHasher};
use std::hash::{Hash, Hasher};

impl<T: Eq + Hash + 'static> Key for T {
    fn eq(&self, other: &dyn Key) -> bool {
        if let Some(other) = other.as_any().downcast_ref::<T>() {
            return self == other;
        }
        false
    }

    fn hash(&self) -> u64 {
        let mut h = DefaultHasher::new();
        // mix the typeid of T into the hash to make distinct types
        // provide distinct hashes
        Hash::hash(&(TypeId::of::<T>(), self), &mut h);
        h.finish()
    }

    fn as_any(&self) -> &dyn Any {
        self
    }
}

Finally, these impls will make Box<dyn Key> usable as hash table keys:

impl PartialEq for Box<dyn Key> {
    fn eq(&self, other: &Self) -> bool {
        Key::eq(self.as_ref(), other.as_ref())
    }
}

impl Eq for Box<dyn Key> {}

impl Hash for Box<dyn Key> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let key_hash = Key::hash(self.as_ref());
        state.write_u64(key_hash);
    }
}

// just a convenience function to box the key
fn into_key(key: impl Eq + Hash + 'static) -> Box<dyn Key> {
    Box::new(key)
}

With all that in place, you can use the keys almost as you would in a dynamic language:

fn main() {
    let mut map = HashMap::new();
    map.insert(into_key(1u32), 10);
    map.insert(into_key("foo"), 20);
    map.insert(into_key("bar".to_string()), 30);
    assert_eq!(map.get(&into_key(1u32)), Some(&10));
    assert_eq!(map.get(&into_key("foo")), Some(&20));
    assert_eq!(map.get(&into_key("bar".to_string())), Some(&30));
}

Playground

Note that this implementation will always consider values of distinct concrete types to have different values. While Python’s dictionaries will consider keys 1 and 1.0 to be the same key (while "1" will be distinct), an into_key(1u32) will be distinct not just from into_key(1.0), but also from into_key(1u64). Likewise, into_key("foo") will be a distinct from into_key("foo".to_string()). This could be changed by manually implementing Key for the types you care about, in which case the blanket implementation must be removed.

More Related Contents:

Leave a Comment Cancel reply