recorrer - ¿Cómo implementar HashMap con dos claves?

obtener valor de un map java

Question

HashMap implementa los métodos de get e insert que toman un solo préstamo inmutable y un solo movimiento de un valor respectivamente.

Quiero un rasgo que sea como este pero que tome dos teclas en lugar de una. Utiliza el mapa interior, pero es solo un detalle de la implementación.

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

Dentro del método de get , los valores tomados en préstamo por a y b pueden no estar adyacentes entre sí en la memoria.

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

Tomar prestado un valor de tipo &(A, B) requeriría una A y una B que son adyacentes.

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

Un poco de código inseguro puede arreglar esto! Necesitamos una copia superficial de *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);
}

Answer 2

Esto es ciertamente posible. La firma de get es

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

El problema aquí es implementar un tipo &Q tal que

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

Para satisfacer la condición (1), debemos pensar en cómo escribir

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

El truco es que &Q no necesita ser un simple puntero , ¡puede ser un objeto de rasgo ! La idea es crear un rasgo Q que tendrá dos implementaciones:

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

La implementación de Borrow simplemente se devolverá y podremos construir un objeto de rasgo &Q partir de los dos elementos por separado.

La implementación completa es así:

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

// 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.a().hash(state);
        self.b().hash(state);
    }
}

impl<''a, A: Eq, B: Eq> PartialEq for (KeyPair<A, B> + ''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, B> + ''a) {}

// OP''s Table struct
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
    }
}
impl<''a, ''b, A, B> KeyPair<A, B> 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")));
}

Explicación:

1. Presentamos los tipos Pair y BorrowedPair . No podemos usar (A, B) directamente debido a la regla huérfana E0210 . Esto está bien ya que el mapa es un detalle de implementación.

2. El rasgo KeyPair toma el papel de Q que mencionamos anteriormente. Necesitaríamos impl Eq + Hash for KeyPair , pero Eq y Hash son seguros para objetos . Añadimos los métodos a a() y b() para ayudar a implementarlos manualmente.

3. Ahora implementamos el rasgo de Borrow del Pair<A, B> a KeyPair + ''a . Tenga en cuenta que ''a - esto es un bit sutil que se necesita para hacer que Table::get funcione realmente. El ''a arbitrario nos permite decir que un Pair<A, B> puede ser prestado al objeto de rasgo para cualquier vida. Si no especificamos ''a , el objeto de rasgo sin tamaño se establecerá como predeterminado ''static , lo que significa que el rasgo de Borrow solo se puede aplicar cuando la implementación como BorrowedPair sobreviva a ''static , lo que ciertamente no es el caso.

4. Finalmente, implementamos Eq y Hash . Como se KeyPair + ''a anteriormente, implementamos para KeyPair + ''a lugar de KeyPair (lo que significa que KeyPair + ''static en este contexto).

El uso de objetos de rasgos incurrirá en un costo indirecto al calcular el hash y verificar la igualdad en get() . El costo puede eliminarse si el optimizador puede desvirtualizar eso, pero se desconoce si LLVM lo hará.

Una alternativa es almacenar el mapa como HashMap<(Cow<A>, Cow<B>), f64> . El uso de este requiere menos "código inteligente", pero ahora hay un costo de memoria para almacenar el indicador propio / prestado, así como el costo de tiempo de ejecución tanto en get() como en set() .

A menos que bifurque el HashMap estándar y agregue un método para buscar una entrada a través de Hash + Eq solo, no hay una solución de costo cero garantizado.

Answer 3

Un rasgo de Memory que toma dos claves, establecido por valor y obtener por referencia:

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

Puede impl dicho rasgo usando un Mapa de Mapas:

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

Tenga en cuenta que si la solución es algo elegante, la huella de memoria de un HashMap de HashMaps debe considerarse cuando se deben administrar miles de instancias de HashMap .

Ejemplo completo