Cómo usar dos números como una clave de mapa

Question

Tengo dos números y quiero usarlos juntos como clave en un Map. Actualmente, estoy concatenando sus representaciones de cadenas. Por ejemplo, supongamos que los números de clave son 4 y 12. I usar:

String key = 4 + "," + 12; 

El mapa se declara como Map<String, Object>.

¡Creo que esto es tan malo! ¡Me gusta utilizar algo que no sea String como la clave! Quiero la forma más rápida de crear estas claves.

¿Quién tiene una buena idea?

Answer 1

Cree un objeto que contenga los dos números y úselo como la clave. Por ejemplo:

class Coordinates { 

    private int x; 
    private int y; 

    public Coordinates(int x, int y) { 
    ... 
    } 

    // getters 

    // equals and hashcode using x and y 
} 

Map<Coordinates, Location> locations = new HashMap<Coordinates, Location>(); 

Si prefiere un enfoque matemático, ver this StackOverflow answer.

Answer 2

Necesita escribir los métodos eqauls y hashcode correctos, o producir algunos errores.

Answer 3

Puede almacenar dos números enteros en un tiempo como este,

long n = (l << 32) | (r & 0XFFFFFFFFL); 

O puede utilizar después de Pair<Integer, Integer> clase,

public class Pair<L, R> { 

    private L l; 
    private R r; 

    public Pair() { 
    } 

    public Pair(L l, R r) { 
     this.l = l; 
     this.r = r; 
    } 

    public L getLeft() { 
     return l; 
    } 

    public R getRight() { 
     return r; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (!(o instanceof Pair)) { 
      return false; 
     } 
     Pair obj = (Pair) o; 
     return l.equals(obj.l) && r.equals(obj.r); 
    } 

    @Override 
    public int hashCode() { 
     return l.hashCode()^r.hashCode(); 
    } 
} 

Answer 4

Si vas con la solución objeto, asegurarse su clave el objeto es inmutable.

De lo contrario, si alguien muta el valor, no solo ya no será igual a otros valores aparentemente idénticos, sino que el código almacenado en el mapa ya no coincidirá con el devuelto por el método hashCode(). En ese momento eres básicamente SOL.

Por ejemplo, el uso de java.awt.Point - que miradas, en el papel, como exactamente lo que quiere - la siguientes:

public static void main(String[] args) { 
    Map<Point, Object> map = new HashMap<Point, Object>(); 

    Point key = new Point(1, 3); 
    Object val = new Object(); 

    map.put(key, val); 

    System.out.println(map.containsKey(key)); 
    System.out.println(map.containsKey(new Point(1, 3))); 

    // equivalent to setLeft()/setRight() in ZZCoder's solution, 
    // or setX()/setY() in SingleShot's 
    key.setLocation(2, 4); 

    System.out.println(map.containsKey(key)); 
    System.out.println(map.containsKey(new Point(2, 4))); 
    System.out.println(map.containsKey(new Point(1, 3))); 
    } 

grabados:

true 
true 
false 
false 
false 

Answer 5

Otro enfoque sería utilizar mapas anidados:

Map<Integer,Map<Integer,Object>> 

Aquí no tiene sobrecarga para crear claves. Sin embargo, tiene más sobrecarga para crear y recuperar entradas correctamente y siempre necesita acceder a los mapas para encontrar el objeto que está buscando.

Answer 6

¿Por qué escribir todo ese código extra para hacer una clase completa que no necesita para nada más es mejor que usar un simple String? ¿El cómputo del código hash para las instancias de esa clase será mucho más rápido que para el String? No lo creo.

A menos que se esté ejecutando en un entorno de potencia de cómputo extremadamente limitado, la sobrecarga de las cadenas de creación y hash no debe ser notablemente mayor que la instanciación de su clase personalizada.

Supongo que la manera más rápida sería simplemente empaquetar las entradas en una sola longitud, como sugirió ZZ Coder, pero en cualquier caso, no espero que las ganancias de velocidad sean sustanciales.

Answer 7

una respuesta práctica a esta pregunta es:

hashCode = a + b * 17; 

... donde a, b y hashCode son todos enteros. 17 es solo un número primo arbitrario. Tu hash no será único, pero está bien. Ese tipo de cosas se usan en toda la biblioteca estándar de Java.

Answer 8

Debe usar java.awt.Dimension como su clave.

Dimensión clave = nueva Dimensión (4, 12);

Dimension tiene un método hashCode() muy bueno que produce un hashCode diferente para cada par de enteros positivos, de modo que los hashCodes para (4, 12) y (12, 4) son diferentes. Entonces estos son rápidos para crear instancias y hacer muy buenos hashCodes.

Ojalá hubieran hecho la clase inmutable, pero puedes hacer tu propia clase inmutable modelada en Dimension.

Aquí hay una tabla que muestra el código hash para diferentes valores de anchura y altura:

 0 1 2 3 4 <-- width 
    +-------------------- 
0 | 0 2 5 9 14 
1 | 1 4 8 13 
2 | 3 7 12 
3 | 6 11 
4 | 10 

^ 
| 
height 

Si sigue las hashcodes con el fin de 0 a 14, verá el patrón.

Aquí está el código que produce este código hash:

public int hashCode() { 
    int sum = width + height; 
    return sum * (sum + 1)/2 + width; 
} 

Usted puede reconocer la fórmula para el número triangular dentro de la última línea. Es por eso que la primera columna de la tabla contiene todos los números triangulares.

Para la velocidad, debe calcular hashCode en el constructor. Para que toda la clase podría tener este aspecto:

public class PairHash { 
    private final int hash; 
    public PairHash(int a, int b) { 
    int sum = a+b; 
    hash = sum * (sum+1)/2 + a; 
    } 
    public int hashCode() { return hash; } 
} 

Por supuesto, si es probable que tengas un método es igual, pero usted se limita a números enteros positivos que no rebose, puede agregar una forma muy rápida una:

public class PairHash { 
    // PAIR_LIMIT is 23170 
    // Keeping the inputs below this level prevents overflow, and guarantees 
    // the hash will be unique for each pair of positive integers. This 
    // lets you use the hashCode in the equals method. 
    public static final int PAIR_LIMIT = (int) (Math.sqrt(Integer.MAX_VALUE))/2; 
    private final int hash; 

    public PairHash(int a, int b) { 
    assert a >= 0; 
    assert b >= 0; 
    assert a < PAIR_LIMIT; 
    assert b < PAIR_LIMIT; 
    int sum = a + b; 
    hash = sum * (sum + 1)/2 + a; 
    } 

    public int hashCode() { return hash; } 

    public boolean equals(Object other) { 
    if (other instanceof PairHash){ 
     return hash == ((PairHash) other).hash; 
    } 
    return false; 
    } 
} 

Restringimos esto a valores positivos porque los valores negativos producirán algunos códigos hash duplicados. Pero con esta restricción en su lugar, estos son los métodos hashCode() y equals() más rápidos que se pueden escribir. (Por supuesto, puede escribir hashCodes igual de rápido en cualquier clase inmutable calculando el hashCode en el constructor.)

Si no puede vivir con esas restricciones, solo necesita guardar los parámetros.

public class PairHash { 
    private final int a, b, hash; 
    public PairHash(int a, int b) { 
    this.a = a; 
    this.b = b; 
    int sum = a+b; 
    hash = sum * (sum+1)/2 + a; 
    } 
    public int hashCode() { return hash; } 
    public boolean equals(Object other) { 
    if (other instanceof PairHash) { 
     PairHash otherPair = (PairHash)other; 
     return a == otherPair.a && b == otherPair.b; 
    } 
    return false; 
} 

Pero aquí está el truco. No necesitas esta clase en absoluto. Dado que la fórmula le proporciona un número entero único para cada par de números, puede usar ese número entero como su clave de mapa. La clase Integer tiene sus propios métodos fast equals() y hashCode que funcionarán bien. Este método generará la clave hash a partir de dos valores cortos. La restricción es que sus entradas deben ser valores cortos positivos. Esto garantiza que no se desbordará, y al convertir la suma intermedia en una larga, tiene un rango más amplio que el método anterior: funciona con todos los valores cortos positivos.

static int hashKeyFromPair(short a, short b) { 
    assert a >= 0; 
    assert b >= 0; 
    long sum = (long) a + (long) b; 
    return (int) (sum * (sum + 1)/2) + a; 
}