Doble en HashMap

Estaba pensando en usar un doble como la clave de un HashMap, pero sé que las comparaciones de coma 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 mi especulación aquí?

Respuesta corta: no lo hagas

Respuesta larga: Así es como se calculará la clave:

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

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

El método doubleToLongBits() básicamente toma los 8 bytes y los representa como largos. 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 convierta a int (por ejemplo, para 2 dígitos multiplique por 100).

Será mucho más seguro.

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 usas un doble como entrada para una función hash, debes usar doubleToLongBits () . Del mismo modo, use floatToIntBits para flotantes.

En particular, para usar un doble como hash, siguiendo la receta de Josh Bloch, harías:

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

Esto es del Ítem 8 de Java Efectivo, “Anula siempre el código hash cuando anulas iguales”. Se puede encontrar en este pdf del capítulo del libro .

Espero que esto ayude.

Depende de cómo lo estarías usando.

Si está contento con solo poder encontrar el valor basado en el mismo patrón de bits exacto (o potencialmente uno equivalente, como +/- 0 y varios NaN) entonces podría estar bien.

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

Tenga en cuenta que en la mayoría de los casos, para dos instancias de la clase Double, d1 y d2, el valor de d1.equals (d2) es verdadero si y solo si

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

  • Si d1 y d2 representan ambos Double.NaN, el método equals devuelve true, aunque Double.NaN == Double.NaN tiene el valor false.
  • Si d1 representa +0.0 mientras d2 representa -0.0, o viceversa, la prueba igual tiene el valor falso, aunque +0.0 == – 0.0 tiene el valor verdadero.

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

Sin embargo, 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.

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 map = new HashMap(); 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 tanto no encuentra la entrada en el Mapa (probablemente el código de almohadilla también sea diferente, pero ese no es el problema principal).

Si utiliza

 map.get(key) 

debería encontrar la entrada … []]

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 punto 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, ¿se generan tus dobles de tal manera que sabes que los iguales realmente significan 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.

¿Tal vez BigDecimal te lleve a donde quieres ir?

Se usa el hash del doble, no el doble en sí mismo.

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

No estoy seguro de esto (solo debes mirar el código fuente del objeto Double), pero creo que cualquier problema con las comparaciones de punto flotante se resolverá por ti.

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

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

sería todo bien, sin embargo

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

sería peligroso