如何用两个键实现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): Borrow<Q>
2. Q实现Hash + Eq

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

要满足条件(1)，我们需要考虑如何写

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

fn borrow(self: &(A, B)) -> &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特质对象.

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特性扮演我们上面提到的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特征.请注意'a-这是使Table::get实际工作所需的细微之处.任意的'a允许我们说(A, B)可以在 any 生存期内借用到特征对象.如果不指定'a，则未设置大小的特征对象将默认为'static ，这意味着Borrow特性只能在类似(&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()中的相等性时，使用特征对象将产生间接成本.如果优化程序能够将其虚拟化，则可以消除成本，但是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<A>, Cow<B>), 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().

除非您分叉标准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屋！