hashmap - 如何实现有两个键的HashMap？

Question

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

我想要一个类似这样的特征，但它需要两个键而不是一个。它使用了里面的 map ，但它只是一个实现细节。

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

Answer 1

这当然是可能的。 signature of get 是

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

这里的问题是实现一个 &Q 类型，这样

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

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

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

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

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

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

---

full implementation 是这样的:

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 都不是 object safe 。我们添加了 a() 和 b() 方法来帮助手动实现它们。

2. 现在我们将 Borrow 特性从 (A, B) 实现到 dyn KeyPair + 'a 。注意 'a——这是使 Table::get 实际工作所需的一个微妙的部分。任意 'a 允许我们说 (A, B) 可以借用到 trait 对象any 生命周期。如果我们不指定 'a ，未调整大小的特征对象将是 default to 'static ，这意味着 Borrow 特征只能在像 (&A, &B) 这样的实现超过 'static 时应用，当然不是这种情况。

3. 最后，我们实现 Eq 和 Hash 。与第 2 点相同的原因，我们实现的是 dyn KeyPair + '_ 而不是 dyn KeyPair(在此上下文中表示 dyn KeyPair + 'static)。这里的'_是一个语法糖，意思是任意生命周期。

---

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

另一种方法是将 map 存储为 HashMap<(Cow<A>, Cow<B>), f64> 。使用它需要较少的“聪明代码”，但现在存储拥有/借用标志以及 get() 和 set() 中的运行时成本需要内存成本。

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