ejemplo - hashmap java example

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

Question

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

Las siguientes son las dudas que aparecieron en mi mente por un tiempo:

1. ¿Cuál es la importancia de @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 una String como myMap<String,Object> . ¿Puedo mapear los valores contra someObject (en lugar de Cadena) como myMap<someObject, Object> ? ¿Qué todos los contratos debo obedecer para que esto suceda con éxito?

Gracias por adelantado !

EDITAR:

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

Respuesta: Sí.

EDICION 2:

2. En java.util.HashSet , ¿de dónde se genera la clave para la tabla hash? ¿Es del objeto que estamos agregando, por ej. mySet.add(myObject); entonces myObject.hashCode() va a decidir dónde se coloca esto 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

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

Esto permite que la instancia del mapa produzca un código hash útil según el 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 usa internamente este código hash?

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

¿Puedo mapear los valores contra someObject (en lugar de String ) como myMap<someObject, Object> ?

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

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

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

[EDITAR]

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

Sí.

Answer 2

1. Cualquier Object en Java debe tener un método hashCode() ; HashMap y HashSet no son ninguna excepción. Este código hash se usa si inserta el hash map / set en otro hash map / set.
2. Cualquier tipo de clase se puede usar 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 de Object ya obedecen estos contratos, pero es posible que desee anularlas si desea igualdad de valor en lugar de igualdad de referencia.

Answer 3

Aaron Digulla tiene toda la razón. 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 el HashMap, es decir, llama hash(someKey.hashCode)) , donde hash() es un método hashing interno.

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

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

Answer 4

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 5

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:

• 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 hashtables.

Tanto como sea razonablemente práctico, el método hashCode definido por el Object clase devuelve enteros distintos para objetos distintos. (Esto se implementa típicamente al convertir 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()

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

Y sí, puede usar fácilmente cualquier objeto que obedezca al contrato para equals() y hashCode() en un HashMap como clave.

Answer 6

Los contenedores hash como HashMap y HashSet proporcionan un acceso rápido a los elementos almacenados en ellos al dividir sus contenidos en "cubos".

Por ejemplo, la lista de números: 1, 2, 3, 4, 5, 6, 7, 8 almacenados en una 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 de la 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 espera, ¿cómo sabemos qué cubo buscar? Ahí es donde entra en hashCode método hashCode . Para determinar el depósito en el que buscar un artículo, los contenedores hash de Java llaman a hashCode 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 el cubo correcto, cada artículo en ese cubo 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 tanto un método equals como uno hashCode , puede usarse como una clave en un Map o una entrada en un Set . Hay un contrato que se debe seguir para implementar estos métodos correctamente. El texto canónico sobre esto es del gran libro de Josh Bloch Effective Java: Item 8: Anula siempre hashCode cuando reemplazas a iguales

Answer 7

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

1. Anular Iguales.

2. Anular 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 () es utilizado internamente por HashMap y, por lo tanto, devolver el valor adecuado es importante para el rendimiento.

Aquí está el método hashCode () de 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;
}

Del código anterior se desprende que hashCode de cada clave no solo se usa para hashCode () del mapa, sino también para encontrar el depósito para colocar la clave, par de valores. Es por eso que hashCode () está relacionado con el rendimiento de HashMap

Answer 8

Método HashCode para clases de colección como HashSet, HashTable, HashMap, etc. - El código Hash devuelve un 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 contacto general para el método HashCode

• Para 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, entonces debe devolver un valor entero constante.

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

Answer 9

La respuesta a la pregunta 2 es fácil: sí, puede usar cualquier Objeto que quiera. 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 respondió antes: siempre que sobrescriba equals (), debe anular hashcode () para obedecer 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 al margen práctica: eclipse (y probablemente otros IDE 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

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

Pero ten cuidado con los métodos hashcode / equals ''hechos a mano'': si utilizas un objeto como clave, asegúrate de que el código hash no cambie después, de lo contrario ya no encontrarás los valores mapeados. En otras palabras, los campos que usa para calcular equals 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 de 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 interna de hash, el valor se establece pero no se usa (solo una instancia estática de 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;
}