Doble en HashMap

Question

Estaba pensando en utilizar un doble como la clave de un HashMap pero sé que las comparaciones de punto flotante no son seguras, eso me hizo pensar. ¿El método equals en la clase Double también es inseguro? Si es así, entonces el método hashCode probablemente también sea incorrecto. Esto significaría que usar Double como la clave de un HashMap llevaría a un comportamiento impredecible.

¿Alguien puede confirmar cualquiera de mis especulaciones aquí?

Answer 1

Respuesta corta: No practico

Respuesta larga: Así es como el la clave se va a calcular:

La clave real será un objeto java.lang.Double, ya que las claves deben ser objetos. Aquí es su hashCode() método:

public int hashCode() { 
    long bits = doubleToLongBits(value); 
    return (int)(bits^(bits >>> 32)); 
} 

El método doubleToLongBits() básicamente toma los 8 bytes y representan el mayor tiempo. Por lo tanto, significa que pequeños cambios en el cálculo del doble pueden significar mucho y tendrá errores importantes.

Si puede conformarse con un número determinado de puntos después del punto, multiplique por 10^(número de dígitos después del punto) y conviértalo en int (por ejemplo, para 2 dígitos multiplique por 100).

Será mucho más seguro.

Answer 2

Se usa el hash del doble, no el doble.

Edit: Gracias, Jon, en realidad no sabía eso.

No estoy seguro de esto (solo debe mirar el código fuente del objeto Double) pero creo que cualquier problema con las comparaciones de coma flotante se ocuparía de usted.

Answer 3

Depende de cómo lo vaya a usar.

Si usted es feliz con sólo ser capaz de encontrar el valor basado en el patrón mismo bit exacta (o potencialmente uno equivalente, como +/- 0 y varios NaNs), entonces puede estar bien .

En particular, todos los NaN terminarían siendo considerados iguales, pero +0 y -0 se considerarían diferentes. A partir de los documentos de Double.equals:

Tenga en cuenta que en la mayoría de los casos, para los dos instancias de la clase doble, D1 y D2, el valor de d1.equals (d2) es verdadero si y sólo si

d1.doubleValue() == d2.doubleValue() también tiene el valor true. Sin embargo, hay dos excepciones:

• Si D1 y D2 representan ambos Double.NaN, entonces el método es igual devuelve verdadero, a pesar de que Double.NaN == Double.NaN tiene el valor falsa.
• Si d1 representa 0,0 mientras d2 representa -0,0, o viceversa, la de prueba igual tiene el valor falso, incluso aunque 0,0 == - 0.0 tiene el valor verdadero.

Esta definición permite que las tablas hash a funcionen correctamente.

Lo más probable es que esté interesado en "números muy cercanos a la clave", lo que lo hace mucho menos viable. En particular, si va a hacer un conjunto de cálculos para obtener la clave una vez, luego un conjunto diferente de cálculos para obtener la clave por segunda vez, tendrá problemas.

Answer 4

Creo que tienes razón. Aunque el hash de los dobles son enteros, el doble podría estropear el hash. Es por eso que, como menciona Josh Bloch en Java efectivo, cuando utilizas un doble como entrada para una función hash, debes usar doubleToLongBits(). Del mismo modo, use floatToIntBits para flotantes.

En particular, para utilizar un doble como su hachís, siguiendo la receta de Josh Bloch, que haría:

public int hashCode() { 
    int result = 17; 
    long temp = Double.doubleToLongBits(the_double_field); 
    result = 37 * result + ((int) (temp^(temp >>> 32))); 
    return result; 
} 

Ésta es la de la casilla 8 de Effective Java, "Siempre anular hashCode cuando se reemplaza iguales". Se puede encontrar en this pdf of the chapter from the book.

Espero que esto ayude.

Answer 5

Depende de cómo almacene y acceda al mapa, sí, valores similares podrían ser ligeramente diferentes y, por lo tanto, no el hash tiene el mismo valor.

private static final double key1 = 1.1+1.3-1.6; 
private static final double key2 = 123321; 
... 
map.get(key1); 

estaría bien, sin embargo

map.put(1.1+2.3, value); 
... 
map.get(5.0 - 1.6); 

sería peligroso

Answer 6

El problema no es el código hash, sino la precisión de los dobles. Esto causará algunos resultados extraños. Ejemplo:

double x = 371.4; 
    double y = 61.9; 
    double key = x + y; // expected 433.3 

    Map<Double, String> map = new HashMap<Double, String>(); 
    map.put(key, "Sum of " + x + " and " + y); 

    System.out.println(map.get(433.3)); // prints null 

El valor calculado (clave) es "433,29999999999995" que no es igual a 433,3 y por lo que no encuentra la entrada en el mapa (el código hash probablemente también es diferente, pero eso no es el problema principal).

Si utiliza

map.get(key) 

debe encontrar la entrada ... []]

Answer 7

Tal BigDecimal llegar a donde quiere ir?

Answer 8

Respuesta corta: Probablemente no funcionará.

Respuesta honesta: Todo depende.

Respuesta más larga: El código hash no es el problema, es la naturaleza de las comparaciones iguales en coma flotante. Como señalan Nalandial y los comentaristas en su publicación, en última instancia, cualquier partida contra una tabla hash termina usando iguales para elegir el valor correcto.

Entonces la pregunta es, ¿sus dobles se generan de tal manera que usted sabe que los iguales realmente significa iguales? Si lee o calcula un valor, lo almacena en la tabla hash, y luego lee o calcula el valor usando exactamente el mismo cálculo, entonces Double.equals funcionará. Pero de lo contrario no es confiable: 1.2 + 2.3 no es necesariamente igual a 3.5, podría equivaler a 3.4999995 o lo que sea. (No es un ejemplo real, me lo inventé, pero ese es el tipo de cosas que suceden). Puedes comparar flotaciones y dobles razonablemente confiables por menos o mayor, pero no por iguales.