Saltar al contenido

¿Cómo maneja un Java HashMap diferentes objetos con el mismo código hash?

Si te encuentras con alguna parte que no entiendes puedes dejarlo en la sección de comentarios y te responderemos lo mas rápido que podamos.

Solución:

Un hashmap funciona así (esto está un poco simplificado, pero ilustra el mecanismo básico):

Tiene una serie de “cubos” que utiliza para almacenar key-valor pares en. Cada cubo tiene un número único, eso es lo que identifica el cubo. cuando pones un key-valor par en el mapa, el hashmap mirará el código hash del keyy almacene el par en el depósito cuyo identificador es el código hash del key. Por ejemplo: El código hash del key es 235 -> el par se almacena en el cubo número 235. (Tenga en cuenta que un cubo puede almacenar más de uno keypar de valores).

Cuando busca un valor en el hashmap, dándole un keyprimero mirará el código hash del key que diste. El hashmap luego buscará en el cubo correspondiente y luego comparará el key que diste con el keys de todos los pares en el balde, comparándolos con equals().

Ahora puede ver cómo esto es muy eficiente para buscar key-pares de valores en un mapa: por el código hash del key el hashmap sabe de inmediato en qué cubo buscar, de modo que solo tiene que probar con lo que hay en ese cubo.

Mirando el mecanismo anterior, también puede ver qué requisitos son necesarios en el hashCode() y equals() métodos de keys:

  • si dos keys son lo mismo (equals() devoluciones true cuando los comparas), su hashCode() El método debe devolver el mismo número. Si keys violar esto, entonces keys que son iguales podrían almacenarse en diferentes cubos, y el mapa hash no podría encontrar key-pares de valor (porque se verá en el mismo cubo).

  • si dos keys 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 usará equals() para diferenciarlos.

Tu tercera afirmación es incorrecta.

Es perfectamente legal que dos objetos desiguales tengan el mismo código hash. es usado por HashMap como un “filtro de primer paso” para que el mapa pueda encontrar rápidamente posible entradas con el especificado key. Él keys con el mismo código hash luego se prueba la igualdad con el especificado key.

No querría un requisito de que dos objetos desiguales no puedan tener el mismo código hash, ya que de lo contrario lo limitaría a 232 objetos posibles. (También significaría que los 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).

Diagrama de estructura de HashMap

HashMap es un array de Entry objetos.

Considerar HashMap como solo un array de objetos

Echa un vistazo a lo que esto Object es:

static class Entry implements Map.Entry 
        final K key;
        V value;
        Entry next;
        final int hash;
… 

Cada Entry objeto representa un key-par de valores. El campo next se refiere a otro Entry objeto 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, se guardarán dos objetos en un cubo 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 next campo y así sucesivamente. La última entrada se refiere a null.

Cuando creas un HashMap con el constructor por defecto

HashMap hashMap = new HashMap();

Él array se crea con el tamaño 16 y el balance de carga predeterminado de 0,75.

Agregando un nuevo keypar de valores

  1. Calcular código hash para el key
  2. Calcular posición hash % (arrayLength-1) dónde debe colocarse el elemento (número de depósito)
  3. Si intenta agregar un valor con un key que ya ha sido guardado en HashMapentonces el valor se sobrescribe.
  4. De lo contrario, el elemento se agrega al cubo.

Si el cubo ya tiene al menos un elemento, se agrega uno nuevo y se coloca en la primera posición del cubo. Su next campo se refiere al elemento antiguo.

Supresión

  1. Calcular hashcode para el dado key
  2. Calcular número de cubo hash % (arrayLength-1)
  3. Obtenga una referencia al primer objeto Entry en el depósito y, mediante el método equals, itere sobre todas las entradas en el depósito dado. Eventualmente encontraremos el correcto. Entry. Si no se encuentra un elemento deseado, devuelva null
¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *