如何通过对两个键的引用从具有两个键的 HashMap 中获取值？

Question

HashMap

实现

get

方法的方式需要一个不可变的借用。但我想要一个单独接受两个键的实现（用于未来的特征接口），如下所示：

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

问题是我不知道如何从

&(A, B)

和

&A

构造

&B

（如果可能的话）。

Answer 1

这当然是可能的。 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对象！这个想法是创建一个特征

Q

，它将有两个实现：

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

Borrow

实现将简单地返回

self

，我们可以分别从两个元素构造一个

&dyn Q

特征对象。

---

完整的实现是这样的：

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()

   方法来帮助手动实现它们。

2. 现在我们实现从

   Borrow

   到

   (A, B)

   的

   dyn KeyPair + 'a

   特征。请注意

   'a

   — 这是使

   Table::get

   真正发挥作用所需的一个微妙的部分。任意的

   'a

   允许我们说

   (A, B)

   可以在 any 生命周期内借用给特征对象。如果我们不指定

   'a

   ，则未指定大小的特征对象将 默认为

   'static

   ，这意味着

   Borrow

   特征只能在像

   (&A, &B)

   这样的实现超过

   'static

   的情况下才能应用，这当然不是案例。

3. 最后，我们实现了

   Eq

   和

   Hash

   。与第 2 点相同的原因，我们实现

   dyn KeyPair + '_

   而不是

   dyn KeyPair

   （在这种情况下意味着

   dyn KeyPair + 'static

   ）。这里的

   '_

   是一个语法糖，表示任意生命周期。

---

在计算哈希值并检查

get()

中的相等性时，使用特征对象会产生间接成本。如果优化器能够将其去虚拟化，则可以消除成本，但 LLVM 是否会这样做尚不清楚。

另一种方法是将地图存储为

HashMap<(Cow<A>, Cow<B>), f64>

。使用此功能需要较少的“聪明代码”，但现在存储拥有/借用标志以及

get()

和

set()

中的运行时成本都存在内存成本。

除非您分叉标准

HashMap

并添加一种仅通过

Hash + Eq

查找条目的方法，否则没有保证零成本的解决方案。

Answer 2

一个

Memory

特征，需要两个键，通过值 set 和通过引用 get：

trait Memory<A: Eq + Hash, B: Eq + Hash> {

    fn get(&self, a: &A, b: &B) -> Option<&f64>;

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

您可以使用地图来

impl

这样的特征：

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

impl<A: Eq + Hash, B: Eq + Hash> Memory<A, B> for Table<A, B> {

    fn get(&self, a: &A, b: &B) -> Option<&f64> {
        self.table.get(a)?.get(b)
    }

    fn set(&mut self, a: A, b: B, v: f64) {
        let inner = self.table.entry(a).or_insert(HashMap::new());
        inner.insert(b, v);
    }
}

请注意，如果解决方案有点优雅，则当必须管理数千个 HashMap 实例时，必须考虑

HashMap 的 HashMap

的内存占用。

完整示例

Answer 3

我找到了这个问题的更好答案。我们可以创建一个包装哈希映射，它借用键的元组并在不需要它们时返回它们。

use std::cmp::Eq;
use std::hash::Hash;
use std::collections::HashMap;

struct MultiKeyHashMap<K1, K2, V>
where K1: Eq + Hash,
      K2: Eq + Hash {
    map: HashMap<(K1, K2), V>,
}

impl<K1, K2, V> MultiKeyHashMap<K1, K2, V>
where K1: Eq + Hash,
      K2: Eq + Hash {
    fn insert(&mut self, k1: K1, k2: K2, v: V) -> Option<V> {
        self.map.insert((k1, k2), v)
    }

    fn contains(&self, k1: K1, k2: K2) -> (K1, K2, bool) {
        let k = (k1, k2);
        let contained = self.map.contains_key(&k);
        (k.0, k.1, contained)
    }

    fn remove(&mut self, k1: K1, k2: K2) -> (K1, K2, Option<V>) {
        let k = (k1, k2);
        let removed = self.map.remove(&k);
        (k.0, k.1, removed)
    }

    fn with_capcity(cap: usize) -> Self {
        Self{map: HashMap::with_capacity(cap)}
    }
}

fn main() {
    let mut m = MultiKeyHashMap::<String, String, i32>::with_capcity(10);
    m.insert("hello".to_owned(), "world".to_owned(), 20);
    let (k1, k2, contained) = m.contains("hello".to_owned(), "world".to_owned());
    if !contained {
        println!("failed finding key in map");
    }

    let (k1, k2, val) = m.remove(k1, k2);
    match val {
        Some(i) => {
            if i != 20 {
                println!("failed properly storing/removing value from map");
            }
        },
        None => println!("failed removing value from map"),
    }
}

语法上不是超级优雅，但0成本。

如果您对不安全感到满意：

use std::cmp::Eq;
use std::hash::Hash;
use std::collections::HashMap;
use std::mem::forget;

struct MultiKeyHashMap<K1, K2, V>
where K1: Eq + Hash,
      K2: Eq + Hash {
    map: HashMap<(K1, K2), V>,
}

impl<K1, K2, V> MultiKeyHashMap<K1, K2, V>
where K1: Eq + Hash,
      K2: Eq + Hash {
    fn insert(&mut self, k1: K1, k2: K2, v: V) -> Option<V> {
        self.map.insert((k1, k2), v)
    }

    fn contains(&self, k1: &K1, k2: &K2) -> bool {
        unsafe {
            let k1_ptr = k1 as *const K1;
            let k2_ptr = k2 as *const K2;
            let key = (k1_ptr.read(), k2_ptr.read());
            let contained = self.map.contains_key(&key);
            forget(key);
            contained
        }
    }

    fn remove(&mut self, k1: &K1, k2: &K2) -> Option<V> {
        unsafe {
            let k1_ptr = k1 as *const K1;
            let k2_ptr = k2 as *const K2;
            let key = (k1_ptr.read(), k2_ptr.read());
            let removed = self.map.remove(&key);
            forget(key);
            removed
        }
    }

    fn with_capcity(cap: usize) -> Self {
        Self{map: HashMap::with_capacity(cap)}
    }
}

fn main() {
    let mut m = MultiKeyHashMap::<String, String, i32>::with_capcity(10);
    m.insert("hello".to_owned(), "world".to_owned(), 20);
    let (k1, k2) = ("hello".to_owned(), "world".to_owned());
    if !m.contains(&k1, &k2) {
        println!("failed finding key in map");
    }

    let val = m.remove(&k1, &k2);
    match val {
        Some(i) => {
            if i != 20 {
                println!("failed properly storing/removing value from map");
            }
        },
        None => println!("failed removing value from map"),
    }
}