How to implement a HashMap with two keys?

Question

HashMapimplements methods getand insertthat take one constant borrowing and one move of value, respectively.

I need a trait that looks like this, but that takes two keys instead of two. It uses the map inside, but this is just an implementation detail.

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

It is certainly possible. Signature getequals

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

The problem is to implement a type &Qsuch that (1) (A, B): Borrow<Q>, and also (2) Qimplements Hash + Eq.

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

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

&Q , ! Q, :

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

Borrow self, - &Q .

---

:

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

// See explanation (1).
#[derive(PartialEq, Eq, Hash)]
struct Pair<A, B>(A, B);

#[derive(PartialEq, Eq, Hash)]
struct BorrowedPair<'a, 'b, A: 'a, B: 'b>(&'a A, &'b B);

// See explanation (2).
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;
    /// Checks if this pair is equal to another pair elementwise.
    fn eq_pair(&self, a: &A, b: &B) -> bool;
    /// Computes the hash of the pair.
    fn erased_hash(&self, state: ErasedHasher);
}

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

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

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

impl<'a, A: Eq, B: Eq> Eq for (KeyPair<A, B> + 'a) {}

pub struct Table<A: Eq + Hash, B: Eq + Hash> {
    map: HashMap<Pair<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(&BorrowedPair(a, b) as &KeyPair<A, B>).unwrap()
    }

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

// Boring stuff below.

impl<A, B> KeyPair<A, B> for Pair<A, B>
where
    A: Eq + Hash,
    B: Eq + Hash,
{
    fn a(&self) -> &A {
        &self.0
    }
    fn b(&self) -> &B {
        &self.1
    }
    fn eq_pair(&self, a: &A, b: &B) -> bool {
        &self.0 == a && &self.1 == b
    }
    fn erased_hash(&self, mut state: ErasedHasher) {
        self.0.hash(&mut state);
        self.1.hash(&mut state);
    }
}
impl<'a, 'b, A, B> KeyPair<A, B> for BorrowedPair<'a, 'b, A, B>
where
    A: Eq + Hash + 'a,
    B: Eq + Hash + 'a,
{
    fn a(&self) -> &A {
        self.0
    }
    fn b(&self) -> &B {
        self.1
    }
    fn eq_pair(&self, a: &A, b: &B) -> bool {
        self.0 == a && self.1 == b
    }
    fn erased_hash(&self, mut state: ErasedHasher) {
        self.0.hash(&mut state);
        self.1.hash(&mut state);
    }
}

// This is needed simply because `&mut Hasher` is not a `Hasher`,
// and `hash<H: Hasher>(&self, &mut H)` means we need a Sized `Hasher`.
struct ErasedHasher<'a>(&'a mut Hasher);

impl<'a> Hasher for ErasedHasher<'a> {
    fn finish(&self) -> u64 { self.0.finish() }
    fn write(&mut self, bytes: &[u8]) { self.0.write(bytes) }
    fn write_u8(&mut self, i: u8) { self.0.write_u8(i) }
    fn write_u16(&mut self, i: u16) { self.0.write_u16(i) }
    fn write_u32(&mut self, i: u32) { self.0.write_u32(i) }
    fn write_u64(&mut self, i: u64) { self.0.write_u64(i) }
    fn write_usize(&mut self, i: usize) { self.0.write_usize(i) }
    fn write_i8(&mut self, i: i8) { self.0.write_i8(i) }
    fn write_i16(&mut self, i: i16) { self.0.write_i16(i) }
    fn write_i32(&mut self, i: i32) { self.0.write_i32(i) }
    fn write_i64(&mut self, i: i64) { self.0.write_i64(i) }
    fn write_isize(&mut self, i: isize) { self.0.write_isize(i) }
}

:

• Pair BorrowedPair. (A, B) - E0210. , .

• KeyPair Q, . impl Eq + Hash for KeyPair, Eq Hash . , a(), b(), eq_pair() erased_hash(), .

• Borrow Pair<A, B> KeyPair + 'a. 'a - , Table::get. 'a , a Pair<A, B> - . 'a, 'static, , Borrow , BorrowedPair 'static, , , .

• , Eq Hash. , KeyPair + 'a KeyPair ( KeyPair + 'static ).

---

get(). , , LLVM .

HashMap<(Cow<A>, Cow<B>), f64>. " ", Owned/Borrowed, get(), set().

, , HashMap Hash + Eq, .

Answer 2

get , a b, .

[--- A ---]      other random stuff in between      [--- B ---]
 \                                                 /
  &a points to here                               &b points to here

&(A, B) a a b.

     [--- A ---][--- B ---]
      \
       we could have a borrow of type &(A, B) pointing to here

! *a *b.

use std::collections::HashMap;
use std::hash::Hash;
use std::mem::ManuallyDrop;
use std::ptr;

#[derive(Debug)]
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 get(&self, a: &A, b: &B) -> f64 {
        unsafe {
            // The values `a` and `b` may not be adjacent in memory. Perform a
            // shallow copy to make them adjacent. This should be fast! This is
            // not a deep copy, so for example if the type `A` is `String` then
            // only the pointer/length/capacity are copied, not any of the data.
            //
            // This makes a `(A, B)` backed by the same data as `a` and `b`.
            let k = (ptr::read(a), ptr::read(b));

            // Make sure not to drop our `(A, B)`, even if `get` panics. The
            // caller or whoever owns `a` and `b` will drop them.
            let k = ManuallyDrop::new(k);

            // Deref `k` to get `&(A, B)` and perform lookup.
            let v = self.map.get(&k);

            // Turn `Option<&f64>` into `f64`.
            *v.unwrap()
        }
    }

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

fn main() {
    let mut table = Table { map: HashMap::new() };
    table.set(true, true, 1.0);
    table.set(true, false, 2.0);

    println!("{:#?}", table);

    let v = table.get(&true, &true);
    assert_eq!(v, 1.0);
}