如何创建带有类型擦除键的 HashMap？

Question

我希望能够使用各种不同类型作为 a 中的键HashMap，所有这些都可以实现Hash。这似乎应该是可能的：从阅读文档来看，似乎每个Hasher都会产生一个u64结果，因此它们最终会简化为通用类型。实际上我想做的是：

use std::{collections::HashMap, hash::Hash};

fn x(_: HashMap<Box<dyn Hash>, ()>) {}

我不被允许这样做：

error[E0038]: the trait `std::hash::Hash` cannot be made into an object
   --> src/lib.rs:3:9
    |
3   | fn x(_: HashMap<Box<dyn Hash>, ()>) {}
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `std::hash::Hash` cannot be made into an object

似乎我可以创建一个Hasher（例如RandomState），用它来手动计算哈希值，然后将u64结果存储在 a 中HashMap<u64, _>，但这似乎过于复杂。我不想再次获取键值，我只需要能够比较哈希值。有HashMap我不知道的替代方案吗？或者我以完全错误的方式看待这个问题？

Answer 1

似乎我可以创建一个Hasher（例如RandomState），用它来手动计算哈希值，然后将u64结果存储在 a 中HashMap<u64, _>，但这似乎过于复杂。

不幸的是，这过于简单- 由于哈希函数会丢弃一些信息，因此哈希表不仅仅适用于哈希，它们还需要原始密钥将其与您要插入或查找的密钥进行比较。这是处理两个键产生相同散列的情况所必需的，这是可能且允许的。

话虽如此，您可以在 Rust 中使用异构键实现 Python 风格的哈希表，但您需要对键进行装箱Box<dyn Key>，即用作类型擦除键，并Key作为您想要的所有具体类型定义的特征用作哈希键。特别是，您需要：

• 定义Key指定如何比较和散列实际键的特征；
• （可选）为本身的类型提供该特征的全面实现Hash，Eq因此用户不需要手动为每种类型执行此操作；
• 定义Eq并Hash使用Box<dyn Key>特征提供的方法，使其Box<dyn Key>可用作std::collections::HashMap.

该Key特质可以这样定义：

trait Key {
    fn eq(&self, other: &dyn Key) -> bool;
    fn hash(&self) -> u64;
    // see /sf/answers/2358159751/
    fn as_any(&self) -> &dyn Any;
}

Key这是对任何类型的一揽子实现，即Eqand 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
    }
}

最后，这些实现将可用作Box<dyn Key>哈希表键：

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)
}

完成所有这些后，您几乎可以像在动态语言中一样使用这些键：

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));
}

操场

请注意，此实现将始终将不同具体类型的值视为具有不同的值。虽然 Python 的字典将把键1和1.0视为相同的键（while"1"将是不同的），但 aninto_key(1u32)不仅与 不同into_key(1.0)，而且也与 不同into_key(1u64)。同样，into_key("foo")will 不同于into_key("foo".to_string())。这可以通过手动实现Key您关心的类型来更改，在这种情况下，必须删除毯子实现。