Implementación interna de java.util.HashMap y HashSet

Question

He estado tratando de comprender la implementación interna de java.util.HashMap y java.util.HashSet.

Tras están apareciendo las dudas en mi mente por un tiempo:

1. ¿Cuál es la importancia de la @Override public int hashcode() en un HashMap/HashSet? ¿Dónde se usa internamente este código hash?
2. En general he visto que la clave del HashMap es String como myMap<String,Object>. ¿Puedo asignar los valores en contra de someObject (en lugar de String) como myMap<someObject, Object>? ¿Qué todos los contratos debo obedecer para que esto suceda con éxito?

¡Gracias de antemano!

EDIT:

1. ¿Estamos diciendo que el código hash de la clave (comprobar!) Es la cosa real contra la cual el valor se asigna en la tabla hash? Y cuando lo hacemos myMap.get(someKey); Java internamente está llamando al someKey.hashCode() para obtener el número en la tabla Hash para buscar el valor resultante?

Respuesta: Sí.

EDIT 2:

2. En un java.util.HashSet, desde donde se genera la clave para la tabla hash? ¿Es del objeto que estamos agregando, por ej. mySet.add(myObject); luego myObject.hashCode() va a decidir dónde se coloca en la tabla hash? (ya que no damos claves en un HashSet).

Respuesta: El objeto agregado se convierte en la clave. ¡El valor es ficticio!

Answer 1

La respuesta a la pregunta 2 es fácil: sí, puede usar cualquier Objeto que desee. Los mapas que tienen claves de tipo String son ampliamente utilizados porque son estructuras de datos típicas para nombrar servicios. Pero en general, puede asignar dos tipos como Map<Car,Vendor> o Map<Student,Course>.

Para el método hashcode() es como se contestó antes: siempre que anule equals(), debe anular hashcode() para cumplir el contrato. Por otro lado, si está contento con la implementación estándar de equals(), entonces no debe tocar hashcode() (porque eso podría romper el contrato y resultar en códigos hash idénticos para objetos desiguales).

nota lateral práctica: eclipse (y probablemente otros IDEs también) puede generar automáticamente un par de implementaciones equals() y hashcode() para su clase, solo en función de los miembros de la clase.

Editar

Por su pregunta adicional: sí, exactamente. Mire el código fuente para HashMap.get (clave Object); llama a la llave.hashcode para calcular la posición (bin) en el hashtable interno y devuelve el valor en esa posición (si hay uno).

Pero tenga cuidado con los métodos hashcode/equals 'hechos a mano': si utiliza un objeto como clave, asegúrese de que el código no cambia posteriormente, de lo contrario, ya no encontrará los valores mapeados. En otras palabras, los campos que usa para calcular iguales y hashcode deben ser finales (o 'inmutables' después de la creación del objeto).

Supongamos que tenemos un contacto con String name y String phonenumber y usamos ambos campos para calcular equals() y hashcode(). Ahora creamos "John Doe" con su número de teléfono móvil y lo asignamos a su tienda de Donut favorita. hashcode() se usa para calcular el índice (bin) en la tabla hash y ahí es donde se almacena la tienda donut.

Ahora nos enteramos de que tiene un nuevo número de teléfono y cambiamos el campo del número de teléfono del objeto John Doe. Esto da como resultado un nuevo hashcode. Y este código hash se resuelve en un nuevo índice de tablas hash, que generalmente no es el lugar donde se almacenó la tienda favorita Donut de John Does.

El problema es claro: en este caso, queríamos asignar "John Doe" a la tienda Donut, y no a "John Doe con un número de teléfono específico". Por lo tanto, debemos ser cuidadosos con equals/hashcode autogenerados para asegurarnos de que sean lo que realmente queremos, ya que pueden usar campos no deseados, lo que introduce problemas con HashMaps y HashSets.

Editar 2

Si agrega un objeto a un HashSet, el objeto es la clave para la tabla hash interna, el valor se establece pero no usado (sólo una instancia estática del objeto). Aquí está la implementación de openjdk 6 (b17):

// Dummy value to associate with an Object in the backing Map 
private static final Object PRESENT = new Object(); 
private transient HashMap<E,Object> map; 

public boolean add(E e) { 
    return map.put(e, PRESENT)==null; 
} 

Answer 2

¿Cuál es la importancia de @Override public int hashcode() en un HashMap/HashSet?

Esto permite que la instancia del mapa para producir un código hash útiles dependiendo del contenido del mapa. Dos mapas con el mismo contenido producirán el mismo código hash. Si el contenido es diferente, el código hash será diferente.

¿Dónde se utiliza este código hash internamente?

Nunca. Este código solo existe para que pueda usar un mapa como clave en otro mapa.

puedo asignar los valores contra someObject (en lugar de String) como myMap<someObject, Object>?

Si pero someObject debe ser una clase, no un objeto (su nombre sugiere que desea pasar en el objeto, sino que debe ser SomeObject para que quede claro que usted se refiere al tipo).

¿Qué todos los contratos debo obedecer para que esto suceda con éxito?

La clase debe implementar hashCode() y equals().

[EDIT]

¿Estamos diciendo que el código hash de la clave (comprobar!) Es la cosa real contra la cual el valor se asigna en la tabla hash?

Sí.

Answer 3

Existe una relación intrincada entre equals(), hashcode() y tablas hash en general en Java (y .NET también, para el caso). Para citar de la documentación:

public int hashCode()

devuelve un valor de código hash para el objeto. Este método es compatible con el beneficio de hashtables como los proporcionados por java.util.Hashtable.

El contrato general de hashCode es:

• Siempre que se invoca en el mismo objeto más de una vez durante una ejecución de una aplicación Java, el método hashCode deben volver consistentemente el mismo número entero, siempre que no información utilizada en iguales comparaciones en el objeto se modifica. 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), al 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 llamar al método hashCode en cada uno de los dos objetos debe producir 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 hashtables.

tanto como sea razonablemente práctico, el método hashCode definido por clase Object no devolver enteros distintos de objetos distintos. (Esto se implementa típicamente mediante la conversión de la dirección interna del objeto en un entero, pero esta técnica de implementación no es requerida por el lenguaje de programación Java ™.)

La línea

@Overrides public int hashCode() 

solo dice que el método hashCode() está anulado.Esto ia generalmente una señal de que es seguro usar el tipo como clave en un HashMap.

Y sí, puede utilizar aesily cualquier objeto que obedece el contrato para equals() y hashCode() en un HashMap como clave.

Answer 4

1. Cualquier Object en Java debe tener un método hashCode(); HashMap y HashSet no son excepciones. Este código hash se usa si inserta el hash map/set en otro hash map/set.
2. Cualquier tipo de clase se puede utilizar como la clave en un HashMap/HashSet. Esto requiere que el método hashCode() devuelva valores iguales para objetos iguales, y que el método equals() se implemente de acuerdo con el contrato (reflexivo, transitivo, simétrico). Las implementaciones predeterminadas desde Object ya obedecen estos contratos, pero es posible que desee anularlas si desea igualdad de valor en lugar de igualdad de referencia.

Answer 5

Sí. Puede usar cualquier objeto como la clave en un HashMap. Para hacerlo, sigue los pasos que debes seguir.

1. Sobrescribe equals.

2. Anula hashCode.

Los contratos para ambos métodos se mencionan muy claramente en la documentación de java.lang.Object. http://java.sun.com/javase/6/docs/api/java/lang/Object.html

Y sí, el método hashCode() se usa internamente en HashMap y, por lo tanto, devolver el valor correcto es importante para el rendimiento.

Aquí es el método hashCode() desde HashMap

public V put(K key, V value) { 
    if (key == null) 
     return putForNullKey(value); 
    int hash = hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
     Object k; 
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
      V oldValue = e.value; 
      e.value = value; 
      e.recordAccess(this); 
      return oldValue; 
     } 
    } 

    modCount++; 
    addEntry(hash, key, value, i); 
    return null; 
} 

Está claro a partir del código por encima de ese código hash de cada tecla no sólo se utiliza para hashCode() del mapa, pero también para encontrar el cubo para colocar la llave, par de valores. Es por eso que hashCode() está relacionado con el rendimiento de HashMap

Answer 6

Aaron Digulla es absolutamente correcto. Una nota adicional interesante que las personas no parecen darse cuenta es que el método hashCode() del objeto clave no se usa textualmente. Es, de hecho, revisado por HashMap, es decir, llama al hash(someKey.hashCode)), donde hash() es un método de hashing interno.

Para ver esto, echar un vistazo a la fuente: http://kickjava.com/src/java/util/HashMap.java.htm

La razón de esto es que algunas personas implementar hashCode() mal y el hash() función proporciona una mejor distribución de hash. Básicamente se hace por motivos de rendimiento.

Answer 7

En la respuesta a la pregunta 2, aunque puede tener cualquier clase que se pueda usar como clave en Hashmap, la mejor práctica es usar clases inmutables como claves para HashMap. O al menos si su implementación de "hashCode" y "igual" depende de algunos de los atributos de su clase, entonces debe tener cuidado de no proporcionar métodos para alterar estos atributos.

Answer 8

Los contenedores hash como HashMap y HashSet proporcionan un acceso rápido a los elementos almacenados en ellos mediante la división de sus contenidos en "cubos".

Por ejemplo, la lista de números: 1, 2, 3, 4, 5, 6, 7, 8 almacenada en un List se vería (conceptualmente) en memoria algo así como: [1, 2, 3, 4, 5, 6, 7, 8].

Almacenar el mismo conjunto de números en un Set se vería más como esto: [1, 2] [3, 4] [5, 6] [7, 8]. En este ejemplo, la lista se ha dividido en 4 segmentos.

Ahora imagine que desea encontrar el valor 6 fuera del List y el Set. Con una lista, debe comenzar al principio de la lista y verificar cada valor hasta llegar a 6, esto dará 6 pasos. Con un conjunto, encuentra el cubo correcto, verifica cada uno de los elementos en ese cubo (solo 2 en nuestro ejemplo), haciendo que este sea un proceso de 3 pasos. El valor de este enfoque aumenta drásticamente cuanto más datos tenga.

Pero, ¿cómo saber qué cubo buscar? Ahí es donde entra el método hashCode. Para determinar el depósito en el que buscar un artículo, los contenedores hash de Java llaman al hashCode y luego aplican alguna función al resultado. Esta función intenta equilibrar el número de cubos y el número de elementos para la búsqueda más rápida posible.

Durante la búsqueda, una vez que se ha encontrado la cubeta correcta, cada elemento de esa cubeta se compara de a uno por vez como en una lista. Es por eso que cuando anula hashCode, también debe anular equals. Entonces, si un objeto de cualquier tipo tiene un método equals y uno hashCode, se puede usar como clave en un Map o en una entrada en un Set. Hay un contrato que se debe seguir para implementar correctamente estos métodos el texto canónico sobre esto es de gran libro eficaz de Java de Josh Bloch: Método Item 8: Always override hashCode when you override equals

Answer 9

HashCode para clases de colección como HashSet, HashTable, HashMap etc - Código de comprobación aleatoria devuelve el número entero para el objeto que se admite con el fin de hash. Se implementa convirtiendo la dirección interna del objeto en un número entero. El método de código hash debe ser anulado en cada clase que anula el método igual. Tres de contacto general para el método HashCode

• Durante dos objetos iguales acc. para un método igual, y luego llamar a HashCode para ambos objetos, debe producir el mismo valor entero.

• Si se llama varias veces para un solo objeto, debe devolver un valor entero constante.

• Para dos objetos desiguales según. para un método igual, y luego llamar al método HashCode para ambos objetos, no es obligatorio que produzca un valor distinto.