rust - 如何创建带有类型删除键的 HashMap？

Question

我希望能够在 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导致 HashMap<u64, _>但这似乎有点过于复杂。我不想再次获取键值，我只需要能够比较哈希值。有没有 HashMap替代方案我不知道？还是我以完全错误的方式看待这个问题？

Answer 1

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.

不幸的是，这太简单了——因为散列函数会丢弃一些信息，散列表不仅可以处理散列，它们还需要原始键来与您插入或查找的键进行比较。这对于处理两个键产生相同散列的情况是必要的，这既可能又允许。
话虽如此，您可以在 Rust 中使用异构键实现 Python 风格的哈希表，但您需要将键装箱，即使用 Box<dyn Key>作为类型删除的 key ，使用 Key作为您为要用作散列键的所有具体类型定义的特征。特别是，您需要:

定义 Key指定如何比较和散列实际键的特征；

(可选)为本身是 Hash 的类型提供该特征的全面实现和 Eq所以用户不需要手动为每种类型执行此操作；

定义 Eq和 Hash为 Box<dyn Key>使用 trait 提供的方法，使 Box<dyn Key>可用作 std::collections::HashMap 中的 key .

Key trait 可以这样定义:

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

这是 Key 的全面实现对于 Eq 的任何类型和 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));
}

Playground
请注意，此实现将始终考虑不同具体类型的值具有不同的值。虽然 Python 的字典会考虑键 1和 1.0要成为相同的键(而 "1" 将不同)，一个 into_key(1u32)不仅与 into_key(1.0) 不同，也来自 into_key(1u64) .同样， into_key("foo")将不同于 into_key("foo".to_string()) .这可以通过手动实现 Key 来改变。对于您关心的类型，在这种情况下，必须删除一揽子实现。