Crear un hashmap con una doble clave

Question

Estoy buscando una estructura de datos adecuada para mi problema. Me gustaría poder seleccionar objetos de nodo de la manera más eficiente posible con dos teclas. La inserción y la eliminación también deben ser eficientes. Básicamente, cada objeto nodo tiene un par de dos claves. Los pares son únicos pero las claves individuales no lo son. Necesito poder seleccionar un grupo de nodos que tengan un valor particular para una de las dos claves.

Ejemplo:

el nodo 1 tiene teclas A1 y B1

Nodo2 tiene teclas a1 y b2

Nodo3 tiene teclas A2 y B2

me gustaría por ejemplo ser capaz para seleccionar el nodo con la clave a1, b1 pero también todos los nodos que tienen b2 como clave2.

Podría, por supuesto, hacer dos HashMaps (uno para cada clave) pero esta es una solución bastante fea porque cuando agrego o elimino algo, tengo que hacerlo en ambos mapas. Como habrá muchas cosas que agregar y eliminar, preferiría hacer esto de una vez. ¿Alguien tiene alguna idea sobre cómo hacer esto?

Obviamente, tener una sola tecla que combina las dos teclas juntas no resuelve el problema porque también necesito poder buscar una sola clave sin tener que buscar en todo el mapa. Eso no sería muy eficiente. El problema es un problema de eficiencia. Podría buscar todas las entradas en el mapa para una clave en particular, pero en su lugar me gustaría utilizar un hash para poder seleccionar múltiples objetos de nodo utilizando una de las dos teclas al instante.

No estoy buscando algo así como MultiKeyMap porque en esta estructura de datos la primera clave siempre permanece igual, solo puede agregar claves en lugar de reemplazar la primera con una clave diferente. Quiero poder cambiar entre la primera y la segunda clave.

Quiero y no quiero almacenar varios objetos con la misma clave. Si observa el ejemplo, puede ver que las dos claves juntas son siempre únicas. Esto se puede ver como una sola clave, por lo tanto, no almacenaría múltiples objetos bajo la misma clave. Pero si miras las claves individuales, estas no son únicas, por lo tanto, quiero almacenar varios objetos a los que hacen referencia las claves individuales.

Answer 1

Si puede utilizar una biblioteca, echar un vistazo a la interfaz Table de guayaba. Asocia una fila y una columna con un valor. La fila y las columnas pueden ser su primera y segunda clave. También puede tener búsquedas por fila o por columna.

Una de las implementaciones de esta interfaz es hash based.

Answer 2

Escriba una clase simple que sea capaz de contener dos valores (las claves) y anule iguales (..) y hashCode() para verificaciones de igualdad utilizadas por el mapa. Use esta clase simple como la clave para el mapa.

Aquí puede encontrar una clase HashMap compatibles par (segunda respuesta):

What is the equivalent of the C++ Pair<L,R> in Java?

Answer 3

Dado que esto es bastante específico para su problema en cuestión, muy probablemente necesitará desarrollar su propia colección. Me gustaría incluir dos MultiMaps de Apache Commons en mi propia clase de colección que se ocupa de las actualizaciones de ambos mapas múltiples al mismo tiempo, y utilizar mi clase para realizar inserciones y consultas.

Answer 4

Como un HashMap solo puede ordenar en un hash para cada objeto, nunca podrá seleccionar las distintas listas 'de fábrica'. Lo que sugeriría es usar una Tupla con dos claves, y luego iterar sobre el HashMap y seleccionar solo aquellos elementos que tengan tuple.key1 = X.

Answer 5

HashMaps puede tener cualquier objeto como clave, así que ¿por qué no crear una clase con 2 campos y considerar esta clase como su clave. También puede anular el método Equals para decirle cómo las claves son iguales

Answer 6

Tienes que crear una clase de clave (igualdad es tratado como Point):

public class Key { 

    int field1; 
    int field2; 

    public boolean equals(Object o) { 
     if (o == null || !(o instanceof Key)) return false; 
     Key other = (Key) o; 
     return field1 == other.field1 && field2 == other.field2; 
    } 

    public int hashCode() { 
     return field1*field2; // doesn't matter if some keys have same hash code 
    } 

} 

Para seleccionar teclas con un valor específico en el primer campo:

public List<Key> getKeysWithField1EqualsTo(int value) { 
    List<Key> result = new ArrayList<>(); 
    for (Key k: map.keySet()) { 
     if (k.field1 == value) result.add(k); 
    } 
    return result; 
} 

Answer 7

Creo que podemos hacerlo de esta manera: para cada tecla, podemos calcular el hashcode correspondiente.

key1 -> hashcode1 
key2 -> hashcode2 

Luego tenemos una matriz de 2 d, con N columnas y N filas.

key1 -> rowIndex: hashcode1 MOD N 
key2 -> columnIndex: hashcode2 MOD N 

Entonces almacenamos el artículo en array[rowIndex][columnIndex].

En esta implementación, puede obtener todas las entradas con una clave de destino1 y cualquier tecla2. También puede obtener todas las entradas con un objetivo clave2 y cualquier clave1.

Esta matriz se puede expandir cuando hay muchas colisiones, tal como lo hace con el hashmap ordinario.