Como implementar o HashMap com duas chaves?

HashMap implementa os methods get e insert , que recebem um único empréstimo imutável e um único movimento de um valor, respectivamente.

Eu quero um traço que é assim, mas que leva duas chaves em vez de um. Ele usa o mapa dentro, mas é apenas um detalhe de implementação.

 pub struct Table { map: HashMap, } impl Memory for Table { 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); } } 

Isso é certamente possível. A assinatura de get é

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

O problema aqui é implementar um tipo &Q tal que

  1. (A, B): Borrow
  2. Q implementa Hash + Eq

Para satisfazer a condição (1), precisamos pensar em como escrever

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

O truque é que &Q não precisa ser um ponteiro simples , pode ser um object de traço ! A ideia é criar um traço Q que terá duas implementações:

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

A implementação do Borrow simplesmente retorna self e podemos construir um object de característica &Q partir dos dois elementos separadamente.


A implementação completa é assim:

 use std::collections::HashMap; use std::hash::{Hash, Hasher}; use std::borrow::Borrow; // See explanation (1). #[derive(PartialEq, Eq, Hash)] struct Pair(A, B); #[derive(PartialEq, Eq, Hash)] struct BorrowedPair<'a, 'b, A: 'a, B: 'b>(&'a A, &'b B); // See explanation (2). trait KeyPair { /// Obtains the first element of the pair. fn a(&self) -> &A; /// Obtains the second element of the pair. fn b(&self) -> &B; } // See explanation (3). impl<'a, A, B> Borrow + 'a> for Pair where A: Eq + Hash + 'a, B: Eq + Hash + 'a, { fn borrow(&self) -> &(KeyPair + 'a) { self } } // See explanation (4). impl<'a, A: Hash, B: Hash> Hash for (KeyPair + 'a) { fn hash(&self, state: &mut H) { self.a().hash(state); self.b().hash(state); } } impl<'a, A: Eq, B: Eq> PartialEq for (KeyPair + 'a) { fn eq(&self, other: &Self) -> bool { self.a() == other.a() && self.b() == other.b() } } impl<'a, A: Eq, B: Eq> Eq for (KeyPair + 'a) {} // OP's Table struct pub struct Table { map: HashMap, f64>, } impl Table { fn new() -> Self { Table { map: HashMap::new() } } fn get(&self, a: &A, b: &B) -> f64 { *self.map.get(&BorrowedPair(a, b) as &KeyPair).unwrap() } fn set(&mut self, a: A, b: B, v: f64) { self.map.insert(Pair(a, b), v); } } // Boring stuff below. impl KeyPair for Pair where A: Eq + Hash, B: Eq + Hash, { fn a(&self) -> &A { &self.0 } fn b(&self) -> &B { &self.1 } } impl<'a, 'b, A, B> KeyPair for BorrowedPair<'a, 'b, A, B> where A: Eq + Hash + 'a, B: Eq + Hash + '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"))); } 

Explicação:

  1. Nós introduzimos os tipos Pair e BorrowedPair . Não podemos usar (A, B) diretamente devido à regra órfã E0210 . Isso é bom, já que o mapa é um detalhe de implementação.

  2. O traço de KeyPair assume o papel de Q que mencionamos acima. Nós precisaríamos impl Eq + Hash for KeyPair , mas Eq e Hash não são objects seguros . Adicionamos os methods a a() e b() para ajudar a implementá-los manualmente.

  3. Agora implementamos o traço Borrow do Pair para KeyPair + 'a . Note o 'a – este é um bit sutil que é necessário para fazer o Table::get realmente funcionar. O arbitrário 'a nos permite dizer que um Pair pode ser emprestado ao object de traço para toda a vida. Se não especificarmos o 'a , o object de atributo não-valorizado será padronizado como 'static , o que significa que o atributo Borrow só pode ser aplicado quando a implementação como BorrowedPair sobrevive 'static , o que certamente não é o caso.

  4. Finalmente, implementamos Eq e Hash . Como acima, nós implementamos para KeyPair + 'a vez de KeyPair (que significa KeyPair + 'static neste contexto).


O uso de objects de traço incorrerá no custo indireto ao calcular o hash e verificar a igualdade em get() . O custo pode ser eliminado se o otimizador conseguir desvirtualizar isso, mas se o LLVM fará isso é desconhecido.

Uma alternativa é armazenar o mapa como HashMap<(Cow, Cow), f64> . Usar isso requer menos “código inteligente”, mas agora há um custo de memory para armazenar o sinalizador de propriedade / emprestado, bem como o custo de tempo de execução em get() e set() .

A menos que você bifurque o HashMap padrão e adicione um método para procurar uma input via Hash + Eq sozinho, não há uma solução de custo zero garantido.

Dentro do método get , os valores emprestados por b podem não estar adjacentes na memory.

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

Emprestar um valor do tipo &(A, B) requereria um A e um B que são adjacentes.

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

Um pouco de código inseguro pode consertar isso! Precisamos de uma cópia superficial de *b .

 use std::collections::HashMap; use std::hash::Hash; use std::mem::ManuallyDrop; use std::ptr; #[derive(Debug)] pub struct Table { map: HashMap<(A, B), f64> } impl Table { 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); } 

Um traço de Memory que leva duas chaves, definido por valor e obter por referência:

 trait Memory { fn get(&self, a: &A, b: &B) -> Option<&f64>; fn set(&mut self, a: A, b: B, v: f64); } 

Você pode impl esse traço usando um mapa de mapas:

 pub struct Table { table: HashMap>, } impl Memory for Table { 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); } } 

Observe que, se a solução for um pouco elegante, a pegada de memory de um HashMap de HashMaps deve ser considerada quando milhares de instâncias do HashMap tiverem que ser gerenciadas.

Exemplo completo