HashMap es una clase que implementa la interfaz Map de Java Collections Framework. La característica más importante de un HashMap es que tiene un rendimiento de tiempo constante para la recuperación e inserción . Los dos factores que dictan el rendimiento de un HashMap son:
- Capacidad inicial
- Factor de carga
Antes de explicar qué es el Load Factor de un HashMap, es fundamental entender su estructura.
Un HashMap tiene Nodes que contienen el par de valores clave como un Node en un mapa. HashMap tiene cubos que contienen los Nodes, un cubo puede contener más de un Node. La estructura básica de un HashMap es la siguiente:
Esquema de la estructura de HashMap
Índice : es el valor entero obtenido después de realizar la operación AND bit a bit sobre el valor del hash de la clave y el tamaño de la array menos uno.
Índice = código hash (clave) & (Tamaño de array – 1)
donde hashcode es una función predefinida que devuelve el valor entero del hash de la clave y ArraySize es el número de cubos en HashMap.
Cubo : es una estructura LinkedList de Nodes.
Node : Es la unidad elemental de un HashMap. Contiene el par clave-valor y un enlace al siguiente Node.
La sintaxis para declarar un objeto HashMap es la siguiente:
HashMap objectName = new HashMap(int initialCapacity, float loadFactor)
Capacidad inicial
La capacidad inicial es esencialmente la cantidad de cubos en HashMap que, de forma predeterminada, es 2 4 = 16 . Un buen algoritmo HashMap distribuirá la misma cantidad de elementos a todos los cubos.
Digamos que tenemos 16 elementos, entonces cada depósito tendrá 1 Node, la búsqueda de cualquier elemento se logrará con 1 búsqueda. Si tenemos 32 elementos, cada cubo tendrá 2 Nodes, la búsqueda de cualquier elemento se logrará con 2 búsquedas. De manera similar, si tenemos 64 elementos, cada cubo tendrá 4 Nodes, la búsqueda de cualquier elemento se logrará con 4 búsquedas y así sucesivamente.
Como puede observar, cuando el número de elementos duplica el número de incrementos de búsqueda en 1, lo cual es bueno para el rendimiento.
Pero, ¿qué sucede cuando el número de elementos llega a un valor muy alto, digamos 10 000? En ese caso, necesitaremos 625 búsquedas. De manera similar, si el número de elementos es 10,00,000, necesitaremos 62,500 búsquedas. Una cantidad tan alta de búsquedas degradará el rendimiento de HashMap. Aquí es donde entra en juego el factor de carga.
Factor de carga
El factor de carga es un umbral, si la relación del elemento actual por la capacidad inicial cruza este umbral, la capacidad aumenta para que la complejidad operativa del HashMap permanezca en O(1). El significado de complejidad operativa de O(1) significa que las operaciones de recuperación e inserción toman un tiempo constante.
El factor de carga predeterminado de un HashMap es 0.75f .
¿Cómo decidimos cuándo aumentar la capacidad?
Tomemos un ejemplo, dado que la capacidad inicial por defecto es 16, supongamos que tenemos 16 cubos en este momento.
Insertamos el primer elemento, el factor de carga actual será 1/16 = 0.0625. La verificación es 0.0625 > 0.75 ? La respuesta es No, por lo tanto no aumentamos la capacidad.
A continuación insertamos el segundo elemento, el factor de carga actual será 2/16 = 0,125. La verificación es 0.125 > 0.75 ? La respuesta es No, por lo tanto no aumentamos la capacidad.
De manera similar, para el tercer elemento, el factor de carga = 3/16 = 0,1875 no es mayor que 0,75, sin cambios en la capacidad.
4º elemento, factor de carga = 4/16 = 0,25 no es mayor que 0,75, sin cambios en la capacidad.
Quinto elemento, factor de carga = 5/16 = 0,3125 no es mayor que 0,75, sin cambios en la capacidad.
Sexto elemento, factor de carga = 6/16 = 0,375 no es mayor que 0,75, sin cambios en la capacidad.
7º elemento, factor de carga = 7/16 = 0,4375 no es mayor que 0,75, sin cambios en la capacidad.
Octavo elemento, factor de carga = 8/16 = 0,5 no es mayor que 0,75, sin cambios en la capacidad.
9º elemento, factor de carga = 9/16 = 0,5625 no es mayor que 0,75, sin cambios en la capacidad.
Décimo elemento, factor de carga = 10/16 = 0,625 no es mayor que 0,75, sin cambios en la capacidad.
Elemento 11, factor de carga = 11/16 = 0,6875 no es mayor que 0,75, sin cambios en la capacidad.
Elemento 12, factor de carga = 12/16 = 0,75 es igual a 0,75, todavía no hay cambios en la capacidad.
Elemento 13, factor de carga = 13/16 = 0,8125 es mayor que 0,75, al insertar el elemento 13 duplicamos la capacidad.
Ahora la capacidad es de 32.
De manera similar, cada vez que una inserción cruza el factor de carga de 0,75, la capacidad se duplica para un rendimiento de tiempo constante de las operaciones get() { recuperación } y put() { inserción }.
Publicación traducida automáticamente
Artículo escrito por ManasiKirloskar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA