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()
devolucionestrue
cuando los comparas), suhashCode()
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).
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
- Calcular código hash para el key
- Calcular posición
hash % (arrayLength-1)
dónde debe colocarse el elemento (número de depósito) - Si intenta agregar un valor con un key que ya ha sido guardado en
HashMap
entonces el valor se sobrescribe. - 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
- Calcular hashcode para el dado key
- Calcular número de cubo
hash % (arrayLength-1)
- 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, devuelvanull