Funcionamiento interno de HashMap en Java

En este artículo, veremos cómo funciona internamente el método get y put de hashmap. ¿Qué operaciones se realizan? Cómo se hace el hashing. Cómo se obtiene el valor por clave. Cómo se almacena el par clave-valor.
En el artículo anterior , HashMap contiene una array de Node y Node puede representar una clase que tiene los siguientes objetos: 

1. hash int
2. tecla k
3. valor V
4. Node siguiente

Ahora veremos cómo funciona esto. Primero, veremos el proceso de hash. 

hash

Hashing es un proceso de convertir un objeto en forma de número entero mediante el método hashCode(). Es necesario escribir correctamente el método hashCode() para un mejor rendimiento de HashMap. Aquí estoy tomando la clave de mi clase para poder anular el método hashCode() para mostrar diferentes escenarios. Mi clase de clave es 

//custom Key class to override hashCode()
// and equals() method
class Key
{
  String key;
  Key(String key)
  {
    this.key = key;
  }
  
  @Override
  public int hashCode() 
  {
     return (int)key.charAt(0);
  }

  @Override
  public boolean equals(Object obj)
  {
    return key.equals((String)obj);
  }
}

Aquí anular el método hashCode() devuelve el valor ASCII del primer carácter como código hash. Entonces, siempre que el primer carácter de la clave sea el mismo, el código hash será el mismo. No debe acercarse a estos criterios en su programa. Es solo para fines de demostración. Como HashMap también permite una clave nula, el código hash de nulo siempre será 0.

Método hashCode() : el método hashCode() se utiliza para obtener el código hash de un objeto. El método hashCode() de la clase de objeto devuelve la referencia de memoria de un objeto en forma de número entero. La definición del método hashCode() es hashCode() nativo público. Indica que la implementación de hashCode() es nativa porque no hay ningún método directo en Java para obtener la referencia del objeto. Es posible proporcionar su implementación de hashCode(). 
En HashMap, hashCode() se usa para calcular el depósito y, por lo tanto, calcular el índice. 

Método equals() : este método se utiliza para comprobar si 2 objetos son iguales o no. Este método lo proporciona la clase Object. Puede anular esto en su clase para proporcionar su implementación. 
HashMap usa equals() para comparar la clave si son iguales o no. Si el método equals() devuelve verdadero, son iguales, de lo contrario no son iguales. 

Cubos: el cubo es un elemento de la array HashMap. Se utiliza para almacenar Nodes. Dos o más Nodes pueden tener el mismo depósito. En ese caso, se utiliza una estructura de lista de enlaces para conectar los Nodes. Los cubos son diferentes en capacidad. Una relación entre el cubo y la capacidad es la siguiente: 

capacity = number of buckets * load factor

Un solo depósito puede tener más de un Node, depende del método hashCode(). Cuanto mejor sea su método hashCode(), mejor se utilizarán sus cubos. 

Cálculo de índice en Hashmap

El código Hash de la clave puede ser lo suficientemente grande como para crear una array. El código hash generado puede estar en el rango de enteros y si creamos arrays para dicho rango, fácilmente causará outOfMemoryException. Entonces generamos un índice para minimizar el tamaño de la array. La siguiente operación se realiza para calcular el índice. 

index = hashCode(key) & (n-1).

donde n es el número de cubos o el tamaño de la array. En nuestro ejemplo, consideraré n como el tamaño predeterminado, que es 16. 

¿Por qué se utiliza el método anterior para calcular el índice?

El uso de un operador AND bit a bit es similar al enmascaramiento de bits en el que solo se consideran los bits inferiores del entero hash, lo que a su vez proporciona un método muy eficiente para calcular el módulo en función de la longitud del hashmap.

• HashMap inicialmente vacío: aquí, el tamaño del hashmap se toma como 16. 
   

HashMap map = new HashMap();

• Mapa hash: 
   

• Inserción de un par clave-valor: poner un par clave-valor en el HashMap anterior 
   

map.put(new Key("vishal"), 20);

• Pasos: 
  1. Calcule el código hash de Key {“vishal”}. Se generará como 118.
  2. Calcule el índice utilizando el método de índice, será 6.
  3. Cree un objeto de Node como: 

{
  int hash = 118

  // {"vishal"} is not a string but 
  // an object of class Key
  Key key = {"vishal"}

  Integer value = 20
  Node next = null
}

1. Coloque este objeto en el índice 6, si no se presenta ningún otro objeto allí.

• Insertando otro par clave-valor: Ahora, poniendo el otro par que es, 

map.put(new Key("sachin"), 30);

• Pasos:
  1. Calcule el código hash de la clave {“sachin”}. Se generará como 115.
  2. Calcule el índice utilizando el método de índice, será 3.
  3. Cree un objeto de Node como: 
      

{
  int hash = 115
  Key key = {"sachin"}
  Integer value = 30
  Node next = null
}

• En caso de colisión: Ahora, poniendo otro par que sea, 
   

map.put(new Key("vaibhav"), 40);

• Pasos: 
  1. Calcule el código hash de Key {“vaibhav”}. Se generará como 118.
  2. Calcule el índice utilizando el método de índice, será 6.
  3. Cree un objeto de Node como:

 {
  int hash = 118
  Key key = {"vaibhav"}
  Integer value = 40
  Node next = null
}

1. Coloque este objeto en el índice 6 si no se presenta ningún otro objeto allí.
2. En este caso, se encuentra un objeto de Node en el índice 6 ; este es un caso de colisión.
3. En ese caso, verifique a través del método hashCode() y equals() si ambas claves son iguales.
4. Si las claves son las mismas, reemplace el valor con el valor actual.
5. De lo contrario, conecte este objeto de Node al objeto de Node anterior a través de una lista vinculada y ambos se almacenan en el índice 6. 
   Ahora HashMap se convierte en:

Usando el método get()

Ahora probemos algunos métodos get para obtener un valor. El método get (clave K) se usa para obtener un valor por su clave. Si no conoce la clave, no es posible obtener un valor. 

• Obtenga los datos para la clave sachin:

map.get(new Key("sachin"));

• Pasos: 
  1. Calcule el código hash de Key {“sachin”}. Se generará como 115.
  2. Calcule el índice utilizando el método de índice, será 3.
  3. Vaya al índice 3 de la array y compare la clave del primer elemento con la clave dada. Si ambos son iguales, devuelva el valor; de lo contrario, verifique el siguiente elemento si existe.
  4. En nuestro caso, se encuentra como primer elemento y el valor devuelto es 30.
• Obtenga los datos para la clave vaibhav: 

map.get(new Key("vaibhav"));

• Pasos: 
  1. Calcule el código hash de Key {“vaibhav”}. Se generará como 118.
  2. Calcule el índice utilizando el método de índice, será 6.
  3. Vaya al índice 6 de la array y compare la clave del primer elemento con la clave dada. Si ambos son iguales, devuelva el valor; de lo contrario, verifique el siguiente elemento si existe.
  4. En nuestro caso, no se encuentra como primer elemento y el siguiente objeto de Node no es nulo.
  5. Si el siguiente Node es nulo, devuelva nulo.
  6. Si el siguiente Node no es nulo, vaya al segundo elemento y repita el proceso 3 hasta que no se encuentre la clave o el siguiente no sea nulo.
  7. La complejidad del tiempo es casi constante para el método put y get hasta que no se realiza el refrito.
  8. En caso de colisión, es decir, el índice de dos o más Nodes es el mismo, los Nodes se unen mediante una lista de enlaces, es decir, el segundo Node es referenciado por el primer Node y el tercero por el segundo, y así sucesivamente.
  9. Si la clave dada ya existe en HashMap, el valor se reemplaza con el nuevo valor.
  10. El código hash de la clave nula es 0.
  11. Al obtener un objeto con su clave, la lista vinculada se recorre hasta que la clave coincide o se encuentra nulo en el siguiente campo.