HashMap es una estructura de datos que almacena los datos en pares (Clave, Valor), ¡similar al Diccionario en python si te interesa!
Para entender el funcionamiento interno de Hashmap, vamos a familiarizarnos con los siguientes términos:
HASHING:
Hashing es el proceso de convertir una clave dada en otro valor basado en una fórmula utilizando una función. Una función hash se utiliza para generar el nuevo valor según un algoritmo matemático. El resultado de una función hash se conoce como valor hash o simplemente, hash. Se utiliza para indexar y recuperar elementos y para algoritmos de
encriptación.
Una verdadera función hash debe seguir esta regla –
«La función hash debe devolver el mismo código hash todas y cada una de las veces que la función se aplique sobre objetos iguales o iguales. En otras palabras, dos objetos iguales deben producir el mismo código hash de forma consistente.»
Todos los objetos en Java heredan una implementación por defecto de la función hashCode() definida en la clase Object.
COLISIONES :
Tenga en cuenta que dos claves pueden generar el mismo hash que puede conducir a la misma dirección. Este fenómeno se conoce como colisión.
Funciones de HashMap
1. Public V get(Object key) : es decir, para obtener un valor del mapa en base a la clave.
2. Public V put(K key, V value) : o para insertar un par clave , valor en el mapa.
Nota: generalmente es necesario anular el método hashCode() siempre que se anule el método equals(), para mantener el contrato general del método hashCode(), que establece que los objetos iguales deben tener códigos hash iguales.
HashMap en JAVA
Modo de instanciar un HashMap en java:
1. Construye un HashMap vacío con la
capacidad inicial y el factor de carga especificados.
public HashMap(int initialCapacity, float loadFactor)
2. Construye un HashMap vacío con la
capacidad inicial especificada y el factor de carga por defecto (0,75).
public HashMap(int initialCapacity)
3. Construye un HashMap vacío con la capacidad inicial por defecto (16) y el factor de carga por defecto (0.75).
public HashMap()
Factor de carga y capacidad inicial.
Una instancia de HashMap tiene dos parámetros que afectan a su rendimiento:
1. Capacidad inicial
2. Factor de carga.
Capacidad inicial :
La capacidad es el número de cubos de la tabla hash, y la capacidad inicial es simplemente la capacidad en el momento en que se crea la tabla hash.
Factor de carga:
El factor de carga es una medida de cuán llena se permite que esté la tabla hash antes de que su capacidad se incremente automáticamente. Cuando el número de entradas en la tabla hash excede el producto del factor de carga y la capacidad actual, la tabla hash se rehace (es decir, se reconstruyen las estructuras de datos internas) para que la tabla hash tenga aproximadamente el doble de cubos.
NOTA:
Como regla general, el factor de carga por defecto (.75) ofrece un buen equilibrio entre los costes de tiempo y espacio. Los valores más altos disminuyen la sobrecarga de espacio pero aumentan el coste de búsqueda (reflejado en la mayoría de las operaciones de la clase HashMap, incluyendo get y put.
El número esperado de entradas en el mapa y su factor de carga deben tenerse en cuenta al establecer su capacidad inicial, con el fin de minimizar el número de operaciones de refrito. Si la capacidad inicial es mayor que el número máximo de entradas dividido por el factor de carga, nunca se producirán operaciones de refrito.
HashMap en Java 8
Un HashMap(de java 8) almacena los datos en múltiples listas de entradas enlazadas individualmente o en múltiples Red BlacK Trees o mezcla de ambos , dependiendo del umbral, también llamados buckets o bins.
Todas las listas/árboles se registran en un array de entradas (tabla Entry<K,V>) y la capacidad por defecto de este array interno es de 16.
Cada uno de los registros individuales o un solo par de Clave y un valor en un HashMap se llama como Entry<Clave,Valor>.
Entry
Los HashMaps utilizan una clase interna para almacenar datos: la Entry<K, V>.
Esta entrada es un simple par clave-valor con dos valores extra que son los siguientes:
1. Una referencia a otra Entrada para que un HashMap pueda almacenar entradas como listas enlazadas individualmente, o como Árbol con nodos de izquierda y derecha para proporcionar una mejor búsqueda.
2. Un valor hash que representa el valor hash de la clave. Este valor hash se almacena para evitar el cálculo del hash cada vez que el HashMap lo necesita.
La entrada en java 8 puede ser de 2 tipos LinkedList Node o RedBlack Tree Node.
*tamaño de este como se ha comentado anteriormente se define durante la instanciación o por defecto 16. En base al factor de carga, se incrementa al doble del tamaño anterior para poder acomodar más Entradas.
Tabla de Nodos<K,V>; //contiene todas las entradas.
En la tabla, cada índice es un Nodo de un LinkedList o un RedBlackTree.
La jerarquía de la entrada va así:
Mapa.Entry<K,V> → implements → Node<K,V> → extends → TreeNode<K,V>
LinkedList Node:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //para mantener una LinkedList.
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
TreeNode:
HashMap, en java 8 , utiliza RedBlackTree después de cierto umbral conocido como TREEIFY_THRESHOLD(valor por defecto 8), ya que da una complejidad de tiempo en el peor de los casos de O(log n), en comparación con LinkedList que da la búsqueda en O(n).
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // enlaces del árbol rojo-negro
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // necesario para desvincular next al borrar
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Funciones de HashMap
1. Comprueba si la clave es nula o no . Tenga en cuenta que sólo puede haber una clave nula en HashMap.Si la clave es nula , entonces las claves nulas siempre se asignan a hash 0, por lo tanto el índice 0 de la tabla.
2. Si la clave no es nula, el método llama al método hashCode() en el objeto clave (anulado por el usuario en la respectiva clase Key) y aplica el hashValue devuelto a su propia función hash estática para encontrar una ubicación de cubo (matriz de respaldo) donde las claves y los valores se almacenan en forma de una clase anidada llamada Entry.
La ubicación de cubo es un índice de la tabla Entry namely.
NOTA: estamos calculando el valor hash de nuevo utilizando hash(hashValue) ya que defiende contra la función hash de mala calidad.
3. El valor hash final se utiliza para encontrar la ubicación del cubo en el que se almacena el objeto Entry.
La complejidad de get() y put() es O(1) ,asumiendo que la función hash dispersa los elementos correctamente entre los cubos.
Nota: Como sabemos ahora que en caso de colisión de hash los objetos de entrada se almacenan como un nodo en una lista enlazada y el método equals() se utiliza para comparar las claves. Esa comparación para encontrar la clave correcta dentro de una lista enlazada es una operación lineal, por lo que en el peor de los casos la complejidad se convierte en O(n).
Para resolver este problema, los elementos hash de Java 8 utilizan árboles equilibrados en lugar de listas enlazadas después de alcanzar un cierto umbral. Lo que significa que HashMap comienza con el almacenamiento de objetos de entrada en la lista enlazada, pero después de que el número de elementos en un hash se hace más grande que un determinado umbral, el hash cambiará de usar una lista enlazada a un árbol equilibrado, lo que mejorará el rendimiento en el peor de los casos de O(n) a O(log n).
¿Qué pasa cuando dos claves diferentes tienen el mismo hashcode?
4. En un índice podemos tener múltiples valores ya que podemos tener colisiones en el hashing. Para averiguar cuál necesitamos, HashMap toma la ayuda de equals().
Solución, el método equals() viene al rescate. Dado que el cubo es uno y tenemos dos objetos con el mismo código hash.
Así que después de obtener el índice de la clave, obtiene el primer nodo presente en ese índice. El primer nodo se compara con la clave usando equals(), Si este es el nodo deseado, devuelve el valor directamente desde aquí.
Si no, encuentra la instancia del Nodo, para averiguar si los datos que contienen almacenados en este índice están en el formato de lista enlazada o árbol RedBlack.
Una vez que lo averiguamos, recorremos la LinkedList o Árbol, comparando las claves en cada una de las entradas usando keys.equals() hasta que devuelve true. Entonces se devuelve el objeto de entrada correspondiente Value.
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {
Node<K,V> tab; //representa el Array de Entry
Node<K,V> first, e;
int n; K k;/* Comprobar si la tabla tiene entradas .*/
/* Además, encontrar el índice sobre la base del hash calculado en los pasos anteriores, donde la entrada se almacena ya sea como Lista o Árbol Nodo.*/if ((tab = tabla) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Obtener el Primer nodo en el índice obtenido sobre la base del hash.*/
if (first.hash == hash && /* comprobar siempre el primer nodo*/
((k = first.key) == key|| (key != null && key.equals(k))))
return first;/*Si el primer nodo de ese índice no es el valor que buscamos ,entonces pasa a recorrerlo.*/
if ((e = first.next) != null) {
if (first instance of TreeNode)
/*Fetching from Red Black Tree if starting Node on the index if of TreeNode .*/return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {/*Fetching from LinkedList si el nodo de partida es de tipo Node y no de Tree.*/
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
while ((e = e.next) != null);
}
return null;
}
PUT:
1. Comprueba si la clave es nula o no. Si la clave es nula, las claves nulas siempre se asignan al hash 0, por lo que el índice 0 de la tabla.
2. Si la clave no es nula, el método llama al método hashCode() en el objeto clave (anulado por el usuario en la respectiva clase Key) y aplica el hashValue devuelto a su propia función hash estática para encontrar una ubicación de cubo (matriz de respaldo) donde las claves y los valores se almacenan en forma de una clase anidada llamada Entry.La ubicación del cubo es un índice de la entrada, es decir, la tabla.
3. El valor hash final se utiliza para encontrar la ubicación del cubo en el que se debe almacenar el objeto de entrada. A continuación, se recorren las Claves de la misma manera que se describe en el get(), para comprobar si la clave ya existe si existe el valor se sustituye por el nuevo valor.
Si no, se comprueba el tamaño de la lista,
Si supera el TREEIFY_THRESHOLD(por defecto 8), se reestructuran los nodos en RedBlackTree y se almacena la nueva clave con el valor en ella.
Si no se supera el umbral, se crea la nueva Entrada con el respectivo valor-clave, y se almacena.
public V put(K clave, V valor) {
return putVal(hash(clave), clave, valor, falso, verdadero);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing as in get()*/
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/*Para comprobar si se ha superado el TREEIFY_THRESHOLD o no.¡*/if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 para la 1ª*/
treeifyBin(tab, hash);
break;}if (e.hash == hash &&((k = e.key) == key | (key != null && key.equals(k))))
break;
p = e;
}if (e != null) { /* mapeo existente para la clave*/
V oldValue = e.value;
if (!onlyIfAbsent | oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;}
Más para leer
Inmutabilidad de la clave:
¿Por qué las cadenas y los enteros son una buena implementación de claves para HashMap? ¡Principalmente porque son inmutables! Si eliges crear tu propia clase de Clave y no la haces inmutable, podrías perder datos dentro del HashMap.
Rehashing:
Rehashing es el proceso de recalcular el hashcode de las entradas ya almacenadas (pares Clave-Valor), para moverlas a otro hashmap de mayor tamaño cuando se alcanza el umbral del factor de carga.
Cuando el número de elementos en el mapa, cruza el límite del factor de carga, en ese momento el hashmap duplica su capacidad y se recalcula el hashcode de los elementos ya almacenados para una distribución uniforme de los pares clave-valor a través de nuevos cubos.
¿Por qué es necesario?
Después de duplicar la capacidad, ¿qué hacer con los pares clave-valor ya presentes en los cubos?
Si mantenemos los pares clave-valor existentes tal y como están, entonces duplicar la capacidad puede no ayudar, porque la complejidad O(1) se logrará sólo si los elementos se distribuyen uniformemente en todos los cubos.
Así que para cada par clave-valor existente, el hashcode se calcula de nuevo con el aumento de la capacidad del hashmap como parámetro, lo que resulta en la colocación del elemento en el mismo cubo o en un cubo diferente.