¿Cómo funciona HashMap en Java?

La mayoría de ustedes estarán de acuerdo en que HashMap, hoy en día, es el tema favorito de discusión durante las entrevistas. A veces tuve discusiones similares con mis colegas y realmente me ayudó. Ahora tendré esa discusión contigo. Supongo que si está interesado en los aspectos internos y el funcionamiento de HashMap, entonces ya está familiarizado con los conceptos básicos de HashMap , así que me saltaré esa parte. Pero si eres nuevo en esto, te sugiero que visites el sitio Java Docs . Antes de continuar, le recomiendo que consulte mi artículo anterior: Trabajar con hashCode y el método igual en Java. Contenido de este artículo:

1. La única respuesta posible.
2. ¿Qué es el hash?
3. Un poco sobre la clase Entry.
4. Lo que hace el put().
5. Cómo funciona el método get().
6. Notas

La única respuesta posible

Si alguien me pide que le explique "¿ Cómo funciona HashMap?" ", simplemente responderé: " Según los principios de Hashing ". No podría ser más sencillo. Para comprender esto y obtener una respuesta ampliada, debe asegurarse de conocer los conceptos básicos de Hashing. ¿Bien?

¿Qué es el hash?

El hash en su forma más simple es una forma de convertir cualquier variable/objeto en un código único después de aplicar cualquier fórmula/algoritmo a sus propiedades. Una función hash verdadera debe seguir la siguiente regla: una función hash debe devolver el mismo código hash siempre que se aplique a objetos iguales o iguales. En otras palabras, dos objetos idénticos deben devolver a su vez los mismos códigos hash. Puede leer más sobre esto aquí: Trabajar con hashCode y el método igual en Java

Un poco sobre la clase de Entrada.

Por definición, un mapa es “un objeto que almacena valores y claves en pares”. Bastante simple, ¿verdad? Entonces, ¿debe haber algún tipo de mecanismo en HashMap que almacene pares de Valores y Claves? Respuesta: sí. HashMaptiene una clase interna Entryque se ve así:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной código тут…
}

Naturalmente, la clase Entrytiene una clave y un valor almacenados como atributos. La clave está marcada como finaly también vemos dos campos adicionales: nexty hash. Intentaremos comprender el propósito de estos campos a medida que avance el artículo.

¿Qué hace el método Java put()?

Antes de profundizar en la implementación del método put(), es muy importante comprender que las instancias de una clase Entryse almacenan en una matriz. La clase HashMap define esta variable como:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Ahora eche un vistazo al código de implementación del método put():

/**
* Связывает определенное significado с определенным ключом в этой карте(map).
* Если карта перед этим содержала significado для данного ключа, это significado
* заменится на новое.
*
* @param key
*            ключ с которым указанное significado должно быть связано.
* @param value
*            significado которое должно быть связано с ключом.
* @return вернет предыдущее significado связанное с key, o null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со significadoм null)
*/
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;
}

Averigüémoslo paso a paso:

• En primer lugar, comprobamos si la clave existe. Si la clave no existe ( ), el valor se coloca en la tabla en la posición nullcero porque el código hash para el valor es null,.это – всегда 0


• En el siguiente paso, el valor hash se calcula utilizando el código hash de la clave obtenida llamando al método hashCode(). Este valor hash se utiliza para calcular la posición en la matriz donde se colocará el objeto Entry. Los diseñadores del JDK asumieron que una función mal escrita hashCode()podría devolver un valor hash demasiado alto o demasiado bajo. Para resolver este problema, introdujeron otra hash()función y le pasaron el valor hash de un objeto para que el valor hash coincidiera con el tamaño de la matriz.


• Ahora se llama a la función indexFor(hash, table.length)para calcular la posición exacta donde se colocará el objeto Entry.


• Aquí comienza la parte principal. LinkedListAhora, basándonos en lo que sabemos de que dos objetos desiguales pueden tener códigos hash iguales , hacemos la pregunta: ¿Se colocarán dos objetos diferentes en la misma posición en la matriz [bucket]? Si recuerdas, la clase Entrytiene un atributo " next". Este atributo siempre apunta al siguiente objeto de la cadena. Este es exactamente el comportamiento LinkedList.

Entonces, los objetos Entryse almacenan en el formulario LinkedList. Cuando se va a colocar un objeto Entryen una ubicación específica, HashMap verifica si ya existe una entrada en esa ubicación. Si no hay entrada, entonces el objeto se coloca en esta posición. Sin embargo, si ya hay un objeto en esta posición, se comprueba el siguiente atributo. Si regresa nully el objeto actual Entryse convierte en el siguiente enlace del archivo LinkedList. Si la siguiente variable no lo es null, se repite el procedimiento para la siguiente hasta encontrarla null. ¿Qué pasa si ponemos otro objeto con un valor diferente pero con la misma clave que antes? Lógicamente, esto debería dar como resultado que se reemplace el valor anterior. ¿Como sucedió esto? En general, después de determinar la posición de un objeto Entry, mientras atraviesa LinkedListhasta la posición calculada, HashMapllama al método de comparación de claves para cada objeto Entry. Todos estos Entryobjetos LinkedListpueden tener códigos hash similares, pero el método equals()comprobará la verdadera similitud. Esto solo reemplazará el valor dentro del archivo Entry. Por tanto, HashMap garantiza la unicidad de todas las claves.

¿Cómo funciona el método get() de Java?

Ahora tenemos una idea de cómo se almacenan los pares clave-valor HashMap. La siguiente gran pregunta es: ¿Qué sucede cuando un objeto pasa de un HashMap a un método get()? ¿Cómo se determina el valor de un objeto? Ya deberíamos saber la respuesta, porque la forma en que se determina la unicidad de una clave en el método put()tiene la misma lógica que aplica el método get(). Una vez que HashMapdetermina la clave del objeto pasado como argumento, simplemente devuelve el valor del correspondiente Entry. Si no se encuentran coincidencias, el método get()devolverá null. Echemos un vistazo al código:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

El código anterior es similar al método put()hasta este punto if (e.hash == hash && ((k = e.key) == key || key.equals(k))), después de eso simplemente devuelve el valor del objeto.

Notas

• La estructura de datos que se almacenará en un objeto Entryes una matriz con un nombre tabley un tipo Entry.
• Cada posición individual en la matriz se llama depósito porque puede contener el primer elemento LinkedListde los objetos Entry.
• hashCode()La clave es necesaria para calcular la posición del objeto Entry.
• equals()La clave se utiliza para verificar la unicidad de la clave en el mapa ( map).
• hashCode()y equals()los valores no se utilizan en métodos get()ni set()en HashMap.
• El código hash para claves con un valor nulles siempre 0. Y dicho objeto Entrysiempre se almacenará en la posición cero de la matriz.

Espero haber transmitido mis pensamientos correctamente en este artículo. Si encuentra errores o tiene preguntas, déjelas en los comentarios. ¡Feliz aprendizaje!