如何创建带有类型已擦除密钥的HashMap? [英] How do I create a HashMap with type erased keys?

问题描述

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

I want to be able to use a variety of different types as keys in a HashMap, all of which would implement Hash. This seems like it should be possible: from reading the docs it seems that every Hasher will produce a u64 result, so they eventually get reduced down to a common type. Effectively I want to do:

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 替代方法吗?还是我以一种完全错误的方式看待这个问题?

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. I don't ever want to get the key values back out again, I just need to be able to compare the hash values. Is there a HashMap alternative I'm not aware of? Or am I looking at this in a totally wrong way?

推荐答案

似乎我可以创建一个 Hasher (例如 RandomState )，使用它手动计算哈希值，然后存储 u64 结果在 HashMap< u64，_> 中，但这似乎过于复杂.

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.

话虽如此，您可以用Rust中的异构键实现Python样式的哈希表，但是您需要 box 键，即使用将Box< dyn Key> 作为类型擦除的密钥，其中 Key 是为要用作哈希密钥的所有具体类型定义的特征.特别是，您需要:

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:

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

• 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.

Key 特性可以这样定义:

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 的任何类型:

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

最后，这些提示将使 Box< dyn Key> 可用作哈希表键:

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

游乐场

请注意，此实现将始终考虑不同具体类型的值具有不同的值.尽管Python的字典将键 1 和 1.0 视为相同的键(而"1" 是不同的)，但into_key(1u32)不仅不同于 into_key(1.0)，而且也不同于 into_key(1u64).同样， into_key("foo")将不同于 into_key("foo" .to_string()).可以通过为您关心的类型手动实现 Key 来更改此设置，在这种情况下，必须删除全部实现.

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.

这篇关于如何创建带有类型已擦除密钥的HashMap?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！