¿Cómo maneja un Java HashMap diferentes objetos con el mismo código hash?
Según tengo entendido creo:
- Es perfectamente legal que dos objetos tengan el mismo código hash.
- Si dos objetos son iguales (usando el método equals()), entonces tienen el mismo código hash.
- Si dos objetos no son iguales entonces no pueden tener el mismo código hash
¿Estoy en lo correcto?
Ahora bien, si estoy en lo cierto, tengo la siguiente pregunta: HashMapInternamente utiliza el código hash del objeto. Entonces, si dos objetos pueden tener el mismo código hash, ¿cómo puede rastrear HashMapqué clave utiliza?
¿ Alguien puede explicar cómo HashMaputiliza internamente el código hash del objeto?
Un hashmap funciona así (está un poco simplificado, pero ilustra el mecanismo básico):
Tiene una cantidad de "depósitos" que utiliza para almacenar pares clave-valor. Cada depósito tiene un número único, que es lo que identifica el depósito. Cuando coloca un par clave-valor en el mapa, el mapa hash observará el código hash de la clave y almacenará el par en el depósito cuyo identificador es el código hash de la clave. Por ejemplo: el código hash de la clave es 235 -> el par se almacena en el depósito número 235. (Tenga en cuenta que un depósito puede almacenar más de un par clave-valor).
Cuando busca un valor en el mapa hash, al darle una clave, primero verá el código hash de la clave que proporcionó. Luego, el mapa hash buscará en el depósito correspondiente y luego comparará la clave que proporcionó con las claves de todos los pares en el depósito, comparándolas con equals().
Ahora puede ver cómo esto es muy eficiente para buscar pares clave-valor en un mapa: mediante el código hash de la clave, el mapa hash sabe inmediatamente en qué depósito buscar, de modo que solo tiene que probar con lo que hay en ese depósito.
Al observar el mecanismo anterior, también puede ver qué requisitos son necesarios en los métodos hashCode()y equals()de las claves:
Si dos claves son iguales (
equals()se devuelvetruecuando las comparas), suhashCode()método debe devolver el mismo número. Si las claves violan esto, entonces las claves que son iguales podrían almacenarse en depósitos diferentes y el mapa hash no podría encontrar pares clave-valor (porque buscará en el mismo depósito).Si dos claves son diferentes, entonces no importa si sus códigos hash son iguales o no. Se almacenarán en el mismo depósito si sus códigos hash son los mismos y, en este caso, el mapa hash los utilizará
equals()para diferenciarlos.
Su tercera afirmación es incorrecta.
Es perfectamente legal que dos objetos desiguales tengan el mismo código hash. Se utiliza HashMapcomo "filtro de primer paso" para que el mapa pueda encontrar rápidamente posibles entradas con la clave especificada. Luego se prueba la igualdad de las claves con el mismo código hash con la clave especificada.
No querrás que dos objetos desiguales no puedan tener el mismo código hash, ya que de lo contrario eso te limitaría a 2 32 objetos posibles. (También significaría que diferentes tipos ni siquiera podrían usar los campos de un objeto para generar códigos hash, ya que otras clases podrían generar el mismo hash).
HashMapes una serie de Entryobjetos.
Considérelo HashMapsimplemente como una serie de objetos.
Echa un vistazo a lo que Objectes esto:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
…
}
Cada Entryobjeto representa un par clave-valor. El campo nextse refiere a otro Entryobjeto si un depósito tiene más de uno Entry.
A veces puede suceder que los códigos hash de 2 objetos diferentes sean iguales. En este caso, dos objetos se guardarán en un depósito y se presentarán como una lista vinculada. El punto de entrada es el objeto agregado más recientemente. Este objeto se refiere a otro objeto con el nextcampo y así sucesivamente. La última entrada se refiere a null.
Cuando creas un HashMapcon el constructor predeterminado
HashMap hashMap = new HashMap();
La matriz se crea con un tamaño de 16 y un equilibrio de carga predeterminado de 0,75.
Agregar un nuevo par clave-valor
- Calcular el código hash para la clave
- Calcular la posición
hash % (arrayLength-1)donde se debe colocar el elemento (número de depósito) - Si intenta agregar un valor con una clave que ya se ha guardado en
HashMap, el valor se sobrescribe. - De lo contrario, el elemento se agrega al depósito.
Si el depósito ya tiene al menos un elemento, se agrega uno nuevo y se coloca en la primera posición del depósito. Su nextcampo hace referencia al elemento antiguo.
Supresión
- Calcular el código hash para la clave dada
- Calcular el número de depósito
hash % (arrayLength-1) - Obtenga una referencia al primer objeto Entry en el depósito y, mediante el método igual, itere sobre todas las entradas en el depósito determinado. Al final encontraremos el correcto
Entry. Si no se encuentra el elemento deseado, regresenull
Puede encontrar información excelente en http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html
Para resumir:
HashMap funciona según el principio de hash
put (clave, valor): HashMap almacena tanto el objeto clave como el valor como Map.Entry. Hashmap aplica el código hash (clave) para obtener el depósito. Si hay una colisión, HashMap usa LinkedList para almacenar el objeto.
get(key): HashMap usa el código hash del objeto clave para averiguar la ubicación del depósito y luego llama al métodokeys.equals() para identificar el nodo correcto en LinkedList y devolver el objeto de valor asociado para esa clave en Java HashMap.
