Geekly articles weekly

HashMap interno en Java

[nota del autor de la traducción] La traducción fue hecha para las propias necesidades, pero si resulta ser útil para alguien, entonces el mundo se ha vuelto al menos un poco, ¡pero mejor! Artículo original - Funcionamiento interno de HashMap en Java


En este artículo, veremos cómo los métodos get y put en la colección HashMap funcionan internamente. Qué operaciones se realizan. Cómo ocurre el hash. Cómo se recupera el valor por clave. ¿Cómo se almacenan los pares clave-valor?


Como en el artículo anterior , HashMap contiene una matriz de Node y Node puede representar una clase que contiene los siguientes objetos:


  1. int - hash
  2. K es la clave
  3. V es el valor
  4. Nodo: siguiente elemento

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


Hashing


Hashing es el proceso de convertir un objeto a una forma entera, realizado utilizando el método hashCode (). Es muy importante implementar correctamente el método hashCode () para garantizar el mejor rendimiento de la clase HashMap.


Aquí uso mi propia clase Key y de esta manera puedo anular el método hashCode () para demostrar varios scripts. Mi clase clave:


//   Key    hashCode() //  equals() 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í, el método anulado hashCode () devuelve el código ASCII del primer carácter de la cadena. Por lo tanto, si los primeros caracteres de la cadena son iguales, entonces los códigos hash serán los mismos. No use una lógica similar en sus programas.


Este código es solo para fines de demostración. Debido a que HashCode acepta una clave nula, el código hash nulo siempre será 0.


Método HashCode ()


El método hashCode () se usa para obtener el código hash del objeto. El método hashCode () de la clase Object devuelve una referencia de memoria entera (código hash de identidad ). La firma del método public native hashCode() . Esto sugiere que el método se implementa como nativo, porque en Java no hay ningún método para obtener una referencia al objeto. Está permitido definir su propia implementación del método hashCode (). En la clase HashMap, el método hashCode () se usa para calcular el depósito y, por lo tanto, calcular el índice.


Método igual ()


El método de igualdad se usa para probar la igualdad de dos objetos. El método se implementa en la clase Object. Puedes anularlo en tu propia clase. En la clase HashMap, el método equals () se usa para verificar la igualdad de claves. En caso de que las claves sean iguales, el método equals () devuelve verdadero, de lo contrario falso.


Cestas


Bucket es el único elemento de la matriz HashMap. Se utiliza para almacenar nodos (nodos). Dos o más nodos pueden tener el mismo depósito. En este caso, se utiliza una estructura de datos de lista vinculada para vincular nodos. Los cubos difieren en capacidad (propiedad de capacidad). La relación entre el cucharón y la capacidad es la siguiente:


 capacity = number of buckets * load factor

Un depósito puede tener más de un nodo, depende de la implementación del método hashCode (). Cuanto mejor se implemente su método hashCode (), mejor se usará su bucket.


Cálculo del índice HashMap


El código clave hash puede ser lo suficientemente grande como para crear una matriz. El código hash generado puede estar en el rango de un tipo entero y si creamos una matriz de este tamaño, podemos obtener fácilmente una excepción OutOfMemoryException. Por lo tanto, generamos un índice para minimizar el tamaño de la matriz. En esencia, se realiza la siguiente operación para calcular el índice:


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

donde n es igual al número de cubeta o al valor de la longitud de la matriz. En nuestro ejemplo, considero n como el valor predeterminado de 16.


  • inicialmente hashMap vacío: aquí el tamaño del hashmap es 16:

 HashMap map = new HashMap();

HashMap:


  • insertar pares Clave - Valor: agregue un par clave - valor al final de HashMap

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

Pasos:


  1. Calcule el valor clave {"vishal"}. Se generará como 118.


  2. Calcule el índice utilizando el método de index , que será 6.


  3. Crea un objeto nodo.


     { int hash = 118 // {"vishal"}  ,  //   Key Key key = {"vishal"} Integer value = 20 Node next = null }

  4. Coloque el objeto en posición con el índice 6, si el espacio es libre.



HashMap ahora se ve así:



  • agregando otro par clave-valor: ahora agregue otro par

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

Pasos:


  1. Calcule el valor clave {"sachin"}. Se generará como 115.


  2. Calcule el índice utilizando el método de index , que será 3.


  3. Crea un objeto nodo.


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

  4. Coloque el objeto en posición con el índice 3, si el espacio es libre.



HashMap ahora se ve así:



  • en caso de colisión: ahora agregue otro par

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

Pasos:


  1. Calcule el valor clave {"vaibhav"}. Se generará como 118.


  2. Calcule el índice utilizando el método de index , que será 6.


  3. Crea un objeto nodo.


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

  4. Coloque el objeto en posición con el índice 6, si el espacio es libre.


  5. En este caso, ya existe otro objeto en la posición con el índice 6, este caso se llama colisión.


  6. En este caso, comprueba con los métodos hashCode () y equals () que ambas claves son iguales.


  7. Si las claves son las mismas, reemplace el valor actual por uno nuevo.


  8. De lo contrario, vincule los objetos nuevos y antiguos utilizando la estructura de datos de "lista vinculada" especificando un enlace al siguiente objeto en el actual y guárdelos en el índice 6.



HashMap ahora se ve así:



[nota del autor de la traducción] La imagen está tomada del artículo original e inicialmente contiene un error. La referencia al siguiente objeto en el objeto visual con índice 6 no es nula, contiene un puntero al objeto vaibhav.


  • obtenemos el valor con la tecla sachin:

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

Pasos:


  1. Calcule el código hash del objeto {{sachin »}. Se generó como 115.


  2. Calcule el índice utilizando el método de index , que será 3.


  3. Vaya al índice 3 y compare la clave del primer elemento con el valor existente. Si son iguales, gire el valor; de lo contrario, verifique el siguiente elemento, si existe.


  4. En nuestro caso, se encuentra el elemento y el valor de retorno es 30.



  • obtenemos el valor por la clave vaibahv:

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

Pasos:


  1. Calcule el código hash del objeto {"vaibhav"}. Fue generado como 118.


  2. Calcule el índice utilizando el método de index , que será 6.


  3. Vaya al índice 6 y compare la clave del primer elemento con el valor existente. Si son iguales, gire el valor; de lo contrario, verifique el siguiente elemento, si existe.


  4. En este caso, no se encontró y el siguiente objeto de nodo no es nulo.


  5. Si el siguiente objeto de nodo es nulo, devuelva nulo.


  6. Si el siguiente objeto de nodo no es nulo, vaya a él y repita los primeros tres pasos hasta que se encuentre el elemento o el siguiente objeto de nodo sea nulo.



 // Java    //   HashMap import java.util.HashMap; class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key)obj).key); } } // Driver class public class GFG { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); } }

Conclusión


 hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40

Cambios en Java 8


Como ya sabemos en caso de colisiones, el objeto de nodo se almacena en la estructura de datos de "lista vinculada" y el método equals () se utiliza para comparar claves. Estas son comparaciones para encontrar la clave correcta en una lista vinculada: una operación lineal y, en el peor de los casos, la complejidad es O (n) .


Para solucionar este problema en Java 8, después de alcanzar un cierto umbral, se utilizan árboles equilibrados en lugar de listas vinculadas. Esto significa que el HashMap al principio guarda los objetos en una lista vinculada, pero después de que el número de elementos en el hash alcanza un cierto umbral, se produce una transición a árboles equilibrados. Lo que mejora el rendimiento en el peor de los casos de O (n) a O (log n).


Punto importante


  1. La complejidad de las operaciones get () y put () es casi constante hasta que se realiza el nuevo hash.
  2. En caso de colisiones, si los índices de dos o más objetos de nodo son iguales, los objetos de nodo se conectan mediante una lista vinculada, es decir. el enlace al segundo objeto de nodo se almacena en el primero, al tercero en el segundo, etc.
  3. Si la clave dada ya existe en HashMap, el valor se sobrescribe.
  4. El código hash nulo es 0.
  5. Cuando la clave obtiene un objeto, las transiciones a través de la lista vinculada ocurren hasta que se encuentra el objeto o el enlace al siguiente objeto es nulo.

Source: https://habr.com/ru/post/es421179/

More articles:


All Articles