¿Cómo crear un HashMap con dos claves (par de claves, valor)?

118

Tengo una matriz 2D de enteros. Quiero que se incluyan en un HashMap. Pero quiero acceder a los elementos del HashMap basado en Array Index. Algo como:

Para A [2] [5], map.get(2,5)que devuelve un valor asociado con esa clave. Pero, ¿cómo creo un hashMap con un par de claves? O en general, múltiples claves: Map<((key1, key2,..,keyN), Value)de manera que pueda acceder al elemento usando get (key1, key2, ... keyN).

EDITAR: 3 años después de publicar la pregunta, quiero agregarle un poco más

Me encontré con otro camino para NxN matrix .

Índices de matriz, iy jse pueden representar como uno solo de keyla siguiente manera:

int key = i * N + j;
//map.put(key, a[i][j]); // queue.add(key); 

Y los índices se pueden recuperar de la keysiguiente manera:

int i = key / N;
int j = key % N;
Crocode
fuente
Una solución simple es mapear una clave en otro mapa hash.
Mihai8
1
No responda la pregunta de la pregunta. Tu edición es interesante, así que no dudes en publicarla como respuesta.
Ole VV
@Crocode ¡guau! las matemáticas detrás de la respuesta en la Edición son brillantes. Me pregunto si funciona en general para dos enteros iy j.
likejudo
@Crocode, ¿i y j cambiarán de ciclo si son múltiplos de N?
likejudo

Respuestas:

190

Hay varias opciones:

2 dimensiones

Mapa de mapas

Map<Integer, Map<Integer, V>> map = //...
//...

map.get(2).get(5);

Objeto de clave de envoltura

public class Key {

    private final int x;
    private final int y;

    public Key(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Key)) return false;
        Key key = (Key) o;
        return x == key.x && y == key.y;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }

}

Implementar equals()y hashCode()es crucial aquí. Entonces simplemente usa:

Map<Key, V> map = //...

y:

map.get(new Key(2, 5));

Table de Guayaba

Table<Integer, Integer, V> table = HashBasedTable.create();
//...

table.get(2, 5);

Tableutiliza mapa de mapas debajo.

N dimensiones

Tenga en cuenta que la Keyclase especial es el único enfoque que escala a n dimensiones. También puede considerar:

Map<List<Integer>, V> map = //...

pero eso es terrible desde la perspectiva del rendimiento, así como la legibilidad y la corrección (no es una manera fácil de hacer cumplir el tamaño de la lista).

Tal vez eche un vistazo a Scala donde tiene tuplas y caseclases (reemplazando toda la Keyclase con una sola línea).

Tomasz Nurkiewicz
fuente
3
Hola, otros tienen x'or los dos valores al hacer hashCode. ¿Por qué usas 31? Pensé que tenía algo que ver con un entero de 32 bits, pero cuando lo pienso no tiene sentido, porque x = 1 e y = 0 todavía se asigna al mismo código hash que x = 0 e y = 31
pete
1
@pete Joshua Bloch, en Effective Java ch 3. s 9., recomienda, "1. Almacene algún valor constante distinto de cero, digamos, 17, en una variable int llamada result ...", que funciona mejor en cuanto a colisiones si es un primo. Ver también: stackoverflow.com/questions/3613102/…
fncomp
2
En lugar del objeto de clave Wrapper, ¿por qué no usarlo Map.Entry<K, V>como clave?
Roland
1
¿Qué hay de Map<Pair<Key1, Key2>, Value>?
Joaquin Iurchuk
1
tenga en cuenta que hashCode()también se puede implementar con una sola línea comoObjects.hash(x,y)
xdavidliu
23

Cuando crea su propio objeto de par de claves, debe enfrentar algunas cosas.

Primero, debe tener en cuenta la implementación de hashCode()y equals(). Necesitará hacer esto.

En segundo lugar, al implementarlo hashCode(), asegúrese de comprender cómo funciona. El ejemplo de usuario dado

public int hashCode() {
    return this.x ^ this.y;
}

es en realidad una de las peores implementaciones que puede hacer. La razón es simple: ¡tienes muchos hashes iguales! Y hashCode()debería devolver valores int que tienden a ser raros, únicos en el mejor de los casos. Usa algo como esto:

public int hashCode() {
  return (X << 16) + Y;
}

Esto es rápido y devuelve hashes únicos para claves entre -2 ^ 16 y 2 ^ 16-1 (-65536 a 65535). Esto encaja en casi cualquier caso. Muy rara vez estás fuera de estos límites.

En tercer lugar, al implementar equals() también debes saber para qué se usa y ser consciente de cómo creas tus claves, ya que son objetos. A menudo hace declaraciones innecesarias porque siempre tendrá el mismo resultado.

Si crea claves como esta: map.put(new Key(x,y),V);nunca comparará las referencias de sus claves. Porque cada vez que quieras acceder al mapa, harás algo como map.get(new Key(x,y));. Por lo tanto equals(), no necesita una declaración como if (this == obj). Será no aparecer dentro.

En lugar de if (getClass() != obj.getClass())en su equals()mejor uso if (!(obj instanceof this)). Será válido incluso para subclases.

Entonces, lo único que necesita comparar es en realidad X e Y. Entonces, la mejor equals()implementación en este caso sería:

public boolean equals (final Object O) {
  if (!(O instanceof Key)) return false;
  if (((Key) O).X != X) return false;
  if (((Key) O).Y != Y) return false;
  return true;
}

Entonces, al final, su clase clave es así:

public class Key {

  public final int X;
  public final int Y;

  public Key(final int X, final int Y) {
    this.X = X;
    this.Y = Y;
  }

  public boolean equals (final Object O) {
    if (!(O instanceof Key)) return false;
    if (((Key) O).X != X) return false;
    if (((Key) O).Y != Y) return false;
    return true;
  }

  public int hashCode() {
    return (X << 16) + Y;
  }

}

Puede dar sus índices de dimensión Xy Yun nivel de acceso público, ya que son definitivos y no contienen información sensible. No estoy 100% seguro de si el privatenivel de acceso funciona correctamente en cualquier caso cuando se envía Objecta unKey .

Si se pregunta acerca de las finales, declaro cualquier cosa como final cuyo valor se establece en la instanciación y nunca cambia, y por lo tanto es una constante de objeto.

chrixle
fuente
7

No puede tener un mapa hash con varias claves, pero puede tener un objeto que tome varios parámetros como clave.

Cree un objeto llamado Índice que tome un valor xey.

public class Index {

    private int x;
    private int y;

    public Index(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        return this.x ^ this.y;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Index other = (Index) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }
}

Entonces tienes tu HashMap<Index, Value>para obtener tu resultado. :)

Puntilla
fuente
4
Necesita anular hashCodey equals.
Tom Hawtin - tackline
4
la implementación de hashCode no diferencia entre (2,1) y (1,2)
user1947415
1
Eso es una colisión. Hashcode no necesita garantizar un valor diferente para cada objeto diferente. @ user1947415
Ajak6
6

Implementado en colecciones comunes MultiKeyMap

Miguel
fuente
@Wilson Arreglé el enlace ahora, esperando la revisión de pares
computingfreak
@computingfreak parece haber recibido una opinión favorable. ¡Hurra! Nota: esta es la mejor respuesta en mi humilde opinión. A menos que le apetezca pasar horas compitiendo con los ingenieros expertos de Apache por alguna funcionalidad muy útil (como siempre) pero en última instancia mundana.
Mike Rodent
4

Dos posibilidades. Utilice una clave combinada:

class MyKey {
    int firstIndex;
    int secondIndex;
    // important: override hashCode() and equals()
}

O un mapa de mapa:

Map<Integer, Map<Integer, Integer>> myMap;
Cyrille Ka
fuente
2
Solo use un mapa de mapas si no le importa el rendimiento o el uso de la memoria aquí (es decir, el mapa es pequeño), o si hay muchas claves con el mismo primer índice, ya que esta solución significa pagar la sobrecarga de un objeto HashMap por cada primer índice único.
BeeOnRope
1
Para mejorar esta respuesta, aquí hay información sobre anulación hashCodey equalsmétodos.
Pshemo
2

Utilice Paircomo claves para el HashMap. JDK no tiene par, pero puede usar una biblioteca de terceros como http://commons.apache.org/lang o escribir una etiqueta de par por su cuenta.

MrSmith42
fuente
1

Cree una clase de valor que represente su clave compuesta, como:

class Index2D {
  int first, second;

  // overrides equals and hashCode properly here
}

teniendo cuidado de anular equals()y hashCode()correctamente. Si eso le parece mucho trabajo, podría considerar algunos contenedores genéricos listos para usar, comoPair proporcionados por apache commons, entre otros.

También hay muchas preguntas similares aquí, con otras ideas, como usar Guava's Tabla , aunque permite que las claves tengan diferentes tipos, lo que podría ser excesivo (en uso de memoria y complejidad) en su caso, ya que entiendo que sus claves son ambas enteras.

BeeOnRope
fuente
1

Si son dos enteros, puedes probar un truco rápido y sucio: Map<String, ?>usar la tecla como i+"#"+j.

Si la clave i+"#"+jes la misma que j+"#"+iintentar min(i,j)+"#"+max(i,j).

arutaku
fuente
2
Realmente mala idea. En primer lugar, es simplemente malo. En segundo lugar, esta técnica se copiará para otros tipos donde diferentes claves pueden asignarse a la misma Stringcon divertidas consecuencias.
Tom Hawtin - tackline
Me parece que i#j = j#isi i == jlo hace, el min/maxtruco no servirá.
Matthieu
1
@Matthieu ¿cuál es la diferencia entre 5#5y 5#5intercambiado?
enrey
@enrey Ninguno. Eso es lo que estaba señalando. Realmente depende del conocimiento que tenga sobre sus claves.
Matthieu
@Matthieu aha, veo lo que quieres decir. Creo que lo que @arutaku quiso decir fue cuando quieres 5#3tener el mismo hash como 3#5, luego usas min / max para hacer cumplir 3#5en este orden.
enrey
1

También puedes usar Guayaba Table implementación de para esto.

La tabla representa un mapa especial donde se pueden especificar dos claves de manera combinada para hacer referencia a un solo valor. Es similar a crear un mapa de mapas.

//create a table
  Table<String, String, String> employeeTable = HashBasedTable.create();

  //initialize the table with employee details
  employeeTable.put("IBM", "101","Mahesh");
  employeeTable.put("IBM", "102","Ramesh");
  employeeTable.put("IBM", "103","Suresh");

  employeeTable.put("Microsoft", "111","Sohan");
  employeeTable.put("Microsoft", "112","Mohan");
  employeeTable.put("Microsoft", "113","Rohan");

  employeeTable.put("TCS", "121","Ram");
  employeeTable.put("TCS", "122","Shyam");
  employeeTable.put("TCS", "123","Sunil");

  //get Map corresponding to IBM
  Map<String,String> ibmEmployees =  employeeTable.row("IBM");
slisnychyi
fuente
1

Podrías crear tu objeto clave de esta manera:

MapKey de clase pública {

public  Object key1;
public Object key2;

public Object getKey1() {
    return key1;
}

public void setKey1(Object key1) {
    this.key1 = key1;
}

public Object getKey2() {
    return key2;
}

public void setKey2(Object key2) {
    this.key2 = key2;
}

public boolean equals(Object keyObject){

    if(keyObject==null)
        return false;

    if (keyObject.getClass()!= MapKey.class)
        return false;

    MapKey key = (MapKey)keyObject;

    if(key.key1!=null && this.key1==null)
        return false;

    if(key.key2 !=null && this.key2==null)
        return false;

    if(this.key1==null && key.key1 !=null)
        return false;

    if(this.key2==null && key.key2 !=null)
        return false;

    if(this.key1==null && key.key1==null && this.key2 !=null && key.key2 !=null)
        return this.key2.equals(key.key2);

    if(this.key2==null && key.key2==null && this.key1 !=null && key.key1 !=null)
        return this.key1.equals(key.key1);

    return (this.key1.equals(key.key1) && this.key2.equals(key2));
}

public int hashCode(){
    int key1HashCode=key1.hashCode();
    int key2HashCode=key2.hashCode();
    return key1HashCode >> 3 + key2HashCode << 5;
}

}

La ventaja de esto es: siempre se asegurará de que esté cubriendo todos los escenarios de Iguales también.

NOTA : su key1 y key2 deben ser inmutables. Solo entonces podrá construir un Objeto clave estable.

Andy
fuente
1

podemos crear una clase para pasar más de una clave o valor y el objeto de esta clase se puede utilizar como parámetro en el mapa.

import java.io.BufferedReader; 
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

 public class key1 {
    String b;
    String a;
    key1(String a,String b)
    {
        this.a=a;
        this.b=b;
    }
  }

public class read2 {

private static final String FILENAME = "E:/studies/JAVA/ReadFile_Project/nn.txt";

public static void main(String[] args) {

    BufferedReader br = null;
    FileReader fr = null;
    Map<key1,String> map=new HashMap<key1,String>();
    try {

        fr = new FileReader(FILENAME);
        br = new BufferedReader(fr);

        String sCurrentLine;

        br = new BufferedReader(new FileReader(FILENAME));

        while ((sCurrentLine = br.readLine()) != null) {
            String[] s1 = sCurrentLine.split(",");
            key1 k1 = new key1(s1[0],s1[2]);
            map.put(k1,s1[2]);
        }
        for(Map.Entry<key1,String> m:map.entrySet()){  
            key1 key = m.getKey();
            String s3 = m.getValue();
               System.out.println(key.a+","+key.b+" : "+s3);  
              }  
  //            }   
        } catch (IOException e) {

        e.printStackTrace();

    } finally {

        try {

            if (br != null)
                br.close();

            if (fr != null)
                fr.close();

        } catch (IOException ex) {

            ex.printStackTrace();

        }

    }

    }

 }
Vikas Pal
fuente