java - example - hashtable

Hashing Keys en Java

Question

En java, cuando uso un String como clave para Hashmap obtengo un resultado un poco diferente que cuando uso el código hash de cadena como una clave en el HashMap.

¿Alguna idea?

Answer 1

cuando uso el código hash de cadena como una clave en HashMap.

No debe usar el código hash como la clave. Los códigos hash no están destinados a ser únicos; está totalmente permitido que dos valores no iguales tengan el mismo código hash. Deberías usar la cadena misma como una clave. El mapa comparará los códigos hash primero (para reducir las coincidencias de los candidatos rápidamente) y luego los comparará con equals de cadenas genuina .

Por supuesto, eso supone que tu código realmente es como lo hace tu pregunta, por ejemplo

HashMap<String, String> goodMap = new HashMap<String, String>();
goodMap.put("foo", "bar");

HashMap<Integer, String> badMap = new HashMap<Integer, String>();
badMap.put("foo".hashCode(), "bar");

Si ese es realmente el aspecto de tu código, simplemente usa HashMap<String, String> .

De los documentos para Object.hashCode() (el énfasis es mío):

El contrato general de hashCode es:

• Cada vez que se invoca en el mismo objeto más de una vez durante la ejecución de una aplicación Java, el método hashCode debe devolver el mismo entero de forma consistente, siempre que no se modifique la información utilizada en comparaciones iguales en el objeto. Este entero no necesita ser consistente desde una ejecución de una aplicación hasta otra ejecución de la misma aplicación.
• Si dos objetos son iguales de acuerdo con el método equals (Object), entonces llamar al método hashCode en cada uno de los dos objetos debe producir el mismo resultado entero.
• No es necesario que si dos objetos son desiguales de acuerdo con el método equals (java.lang.Object), al invocar el método hashCode en cada uno de los dos objetos se produzcan resultados enteros distintos. Sin embargo, el programador debe tener en cuenta que la producción de resultados enteros distintos para objetos desiguales puede mejorar el rendimiento de las tablas hash.

Answer 2

El problema es que, incluso si dos objetos son diferentes, no significa que sus códigos hash también sean diferentes.

Dos objetos diferentes pueden compartir el mismo código hash. Por lo tanto, no debería tenerlos como una clave HashMap.

Además, como los códigos hash devueltos por el método Object.hashCode() son de tipo int , solo puede tener 2^32 valores diferentes. Es por eso que tendrás "colisiones" según el algoritmo hash, para diferentes objetos.

En breve: -

!obj.equals(obj1) no garantiza que obj.hashCode() != obj1.hashCode() .

Answer 3

Por supuesto. Diferentes cadenas pueden tener el mismo código hash, por lo que si almacena dos cadenas como claves en un mapa, tendrá dos entradas (ya que las cadenas son diferentes). Por lo que si utiliza su hashCode como clave, solo tendrá una entrada (ya que hashCode es el mismo).

El hashCode no se usa para decir si dos claves son iguales. Solo se usa para asignar un cubo a la clave. Una vez que se encuentra el cubo, se compara cada clave contenida en el cubo con la nueva clave con iguales, y la clave se agrega al cubo si no se puede encontrar la misma tecla.

Answer 4

Puede utilizar el código hash como la clave solo si la función hash es un hash perfecto (consulte, por ejemplo, GPERF ). Mientras sus objetos clave no residan en la memoria, está en lo cierto al guardar la memoria.

Answer 5

HashCodes pueden ser iguales o diferentes para la misma Cadena, así que ten cuidado con eso. Puede ser esta es la razón por la que está obteniendo un resultado diferente.

Aquí hay otra pregunta ASÍ . Ver la respuesta aceptada de Jon Skeet.