如何用两个键实现 HashMap? [英] How to implement HashMap with two keys?

问题描述

HashMap 实现了 get 和 insert 方法，它们分别采用单个不可变借用和单个值移动.

HashMap implements the get and insert methods which take a single immutable borrow and a single move of a value respectively.

我想要一个像这样但需要两个键而不是一个的特征.它使用内部的地图，但它只是一个实现的细节.

I want a trait which is just like this but which takes two keys instead of one. It uses the map inside, but it's just a detail of implementation.

pub struct Table<A: Eq + Hash, B: Eq + Hash> {
    map: HashMap<(A, B), f64>,
}

impl<A: Eq + Hash, B: Eq + Hash> Memory<A, B> for Table<A, B> {
    fn get(&self, a: &A, b: &B) -> f64 {
        let key: &(A, B) = ??;
        *self.map.get(key).unwrap()
    }

    fn set(&mut self, a: A, b: B, v: f64) {
        self.map.insert((a, b), v);
    }
}

推荐答案

这当然是可能的.get 的签名是

This is certainly possible. The signature of get is

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> 
where
    K: Borrow<Q>,
    Q: Hash + Eq, 

这里的问题是实现一个 &Q 类型使得

The problem here is to implement a &Q type such that

1. (A, B): 借用<Q>
2. Q 实现 Hash + Eq

要满足条件(1)，我们需要考虑怎么写

To satisfy condition (1), we need to think of how to write

fn borrow(self: &(A, B)) -> &Q

诀窍在于&Q 不需要是简单的指针，可以是特征对象！这个想法是创建一个特征 Q 它将有两个实现:

The trick is that &Q does not need to be a simple pointer, it can be a trait object! The idea is to create a trait Q which will have two implementations:

impl Q for (A, B)
impl Q for (&A, &B)

Borrow 实现将简单地返回 self，我们可以分别从这两个元素构造一个 &dyn Q trait 对象.

The Borrow implementation will simply return self and we can construct a &dyn Q trait object from the two elements separately.

完整实施是这样的:

use std::borrow::Borrow;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};

// See explanation (1).
trait KeyPair<A, B> {
    /// Obtains the first element of the pair.
    fn a(&self) -> &A;
    /// Obtains the second element of the pair.
    fn b(&self) -> &B;
}

// See explanation (2).
impl<'a, A, B> Borrow<dyn KeyPair<A, B> + 'a> for (A, B)
where
    A: Eq + Hash + 'a,
    B: Eq + Hash + 'a,
{
    fn borrow(&self) -> &(dyn KeyPair<A, B> + 'a) {
        self
    }
}

// See explanation (3).
impl<A: Hash, B: Hash> Hash for dyn KeyPair<A, B> + '_ {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.a().hash(state);
        self.b().hash(state);
    }
}

impl<A: Eq, B: Eq> PartialEq for dyn KeyPair<A, B> + '_ {
    fn eq(&self, other: &Self) -> bool {
        self.a() == other.a() && self.b() == other.b()
    }
}

impl<A: Eq, B: Eq> Eq for dyn KeyPair<A, B> + '_ {}

// OP's Table struct
pub struct Table<A: Eq + Hash, B: Eq + Hash> {
    map: HashMap<(A, B), f64>,
}

impl<A: Eq + Hash, B: Eq + Hash> Table<A, B> {
    fn new() -> Self {
        Table {
            map: HashMap::new(),
        }
    }

    fn get(&self, a: &A, b: &B) -> f64 {
        *self.map.get(&(a, b) as &dyn KeyPair<A, B>).unwrap()
    }

    fn set(&mut self, a: A, b: B, v: f64) {
        self.map.insert((a, b), v);
    }
}

// Boring stuff below.

impl<A, B> KeyPair<A, B> for (A, B) {
    fn a(&self) -> &A {
        &self.0
    }
    fn b(&self) -> &B {
        &self.1
    }
}
impl<A, B> KeyPair<A, B> for (&A, &B) {
    fn a(&self) -> &A {
        self.0
    }
    fn b(&self) -> &B {
        self.1
    }
}

//----------------------------------------------------------------

#[derive(Eq, PartialEq, Hash)]
struct A(&'static str);

#[derive(Eq, PartialEq, Hash)]
struct B(&'static str);

fn main() {
    let mut table = Table::new();
    table.set(A("abc"), B("def"), 4.0);
    table.set(A("123"), B("456"), 45.0);
    println!("{:?} == 45.0?", table.get(&A("123"), &B("456")));
    println!("{:?} == 4.0?", table.get(&A("abc"), &B("def")));
    // Should panic below.
    println!("{:?} == NaN?", table.get(&A("123"), &B("def")));
}

说明:

1. KeyPair trait 扮演了我们上面提到的 Q 的角色.我们需要 impl Eq + Hash for dyn KeyPair，但 Eq 和 Hash 都不是 对象安全.我们添加了 a() 和 b() 方法来帮助手动实现它们.

1. The KeyPair trait takes the role of Q we mentioned above. We'd need to impl Eq + Hash for dyn KeyPair, but Eq and Hash are both not object safe. We add the a() and b() methods to help implementing them manually.

现在我们从 (A, B) 到 dyn KeyPair + 'a 实现 Borrow trait.注意 'a - 这是使 Table::get 实际工作所需要的一个微妙的位.任意 'a 允许我们说 (A, B) 可以在 any 生命周期内借用给 trait 对象.如果我们不指定 'a，未调整大小的 trait 对象将 默认为 'static，意味着 Borrow trait 只能在像 (&A, &B) 比 'static 长，当然不是这样.

Now we implement the Borrow trait from (A, B) to dyn KeyPair + 'a. Note the 'a — this is a subtle bit that is needed to make Table::get actually work. The arbitrary 'a allows us to say that an (A, B) can be borrowed to the trait object for any lifetime. If we don't specify the 'a, the unsized trait object will default to 'static, meaning the Borrow trait can only be applied when the implementation like (&A, &B) outlives 'static, which is certainly not the case.

最后，我们实现Eq和Hash.与第 2 点相同的原因，我们实现了 dyn KeyPair + '_ 而不是 dyn KeyPair (这意味着 dyn KeyPair + 'static 在这种情况下).这里的 '_ 是一个语法糖，意思是任意生命周期.

Finally, we implement Eq and Hash. Same reason as point 2, we implement for dyn KeyPair + '_ instead of dyn KeyPair (which means dyn KeyPair + 'static in this context). The '_ here is a syntax sugar meaning arbitrary lifetime.

---

在 get() 中计算哈希和检查相等性时，使用 trait 对象会产生间接成本.如果优化器能够将其去虚拟化，则可以消除成本，但 LLVM 是否会这样做是未知的.

---

Using trait objects will incur indirection cost when computing the hash and checking equality in get(). The cost can be eliminated if the optimizer is able to devirtualize that, but whether LLVM will do it is unknown.

另一种方法是将映射存储为 HashMap<(Cow, Cow), f64>.使用它需要更少的智能代码"，但现在在 get() 和 set().

An alternative is to store the map as HashMap<(Cow<A>, Cow<B>), f64>. Using this requires less "clever code", but there is now a memory cost to store the owned/borrowed flag as well as runtime cost in both get() and set().

除非你 fork 标准的 HashMap 并添加一个方法来单独通过 Hash + Eq 查找条目，否则没有保证零成本的解决方案.

Unless you fork the standard HashMap and add a method to look up an entry via Hash + Eq alone, there is no guaranteed-zero-cost solution.

这篇关于如何用两个键实现 HashMap?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！