Una HashMap es una de las estructuras de datos más comúnmente utilizadas en Java, y es conocida por su eficiencia. Los datos en una HashMap se almacenan en la forma de pares clave-valor.

En este artículo, les presentará las HashMaps en Java. Exploraremos las operaciones comunes de HashMap y luego profundizaremos en cómo opera internamente. Conocerán la función hash y cómo se calcula el índice. Finalmente, revisaremos las complejidades de tiempo de las operaciones y tocaremos brevemente el comportamiento en un entorno concurrente.

¿Qué es una HashMap en Java?

Una HashMap implementa la interfaz Map, que forma parte de la infraestructura de colecciones de Java. Se basa en el concepto de Hash.

La hashing es una técnica que transforma una entrada de tamaño arbitrario en una salida de tamaño fijo usando una función hash. La salida generada se denomina código hash y se representa por un valor entero en Java. Los códigos hash se utilizan para operaciones de búsqueda y almacenamiento eficientes en una HashMap.

Operaciones Comunes

Como vimos anteriormente, los datos en una HashMap se almacenan en la forma de pares clave-valor. La clave es un identificador único, y cada clave se asocia con un valor.

A continuación se muestran algunas operaciones comunes soportadas por una HashMap. Vamos a entender qué hacen estos métodos con algunos ejemplos de código sencillos:

Inserción

  • Este método inserta un nuevo par clave-valor en la HashMap.

  • El orden de inserción de los pares clave-valor no se mantiene.

  • Durante la inserción, si una clave ya está presente, el valor existente será reemplazado con el nuevo valor que se pasa.

  • Puede insertar solo una clave nula en el HashMap, pero puede tener múltiples valores nulos.

La firma del método para esta operación se proporciona a continuación, seguida de un ejemplo:

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

En el código anterior, tenemos un ejemplo de HashMap donde añadimos una clave de tipo String y un valor de tipo Integer.

Recuperación:

  • Obtiene el valor asociado con una clave dada.

  • Devuelve null si la clave no existe en el HashMap.

La firma del método para esta operación se proporciona a continuación, seguida de un ejemplo:

public V get(Object key)

Integer value = map.get("apple"); // devuelve 1

En el código anterior, estamos recuperando el valor asociado con la clave apple.

Otras operaciones comunes incluyen:

  • remove: Elimina el par clave-valor para la clave especificada. Devuelve null si no se encuentra la clave.

  • containsKey: Comprueba si una clave específica está presente en el HashMap.

  • containsValue: Comprueba si el valor especificado está presente en el HashMap.

Estructura interna de un HashMap

Internamente, un HashMap utiliza un arreglo de cubos o bins. Cada cubo es una lista enlazada de tipo Node, que se utiliza para representar el par clave-valor del HashMap.

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Aquí puede ver la estructura de la clase Node que se utiliza para almacenar los pares clave-valor del HashMap.

La clase Node tiene los siguientes campos:

  • hash: Se refiere al hashCode de la clave.

  • key: Se refiere a la clave del par clave-valor.

  • value: Se refiere al valor asociado con la clave.

  • next: Actúa como referencia al siguiente nodo.

El HashMap se basa fundamentalmente en una implementación de tabla hash, y su rendimiento depende de dos parámetros clave: la capacidad inicial y el factor de carga. Las original javadocs de la clase Hash table definen estos dos parámetros de la siguiente manera:

  • La capacidad es el número de cubos en la tabla hash, y la capacidad inicial es simplemente la capacidad en el momento en que se crea la tabla hash.

  • El factor de carga es una medida de cuán lleno se permite que la tabla hash se haya antes de que su capacidad se incremente automáticamente.

Vamos a intentar comprender cómo funcionan las operaciones básicas, put y get, en un HashMap.

Función hash

Durante la inserción (put) de un par clave-valor, el HashMap primero calcula el código hash de la clave. La función hash luego calcula un número entero para la clave. Las clases pueden usar el método hashCode de la clase Object o anular este método y proporcionar su propia implementación. (Lea sobre el contrato del código hash aquí). El código hash luego se realiza una operación de XOR (eXclusive OR) con sus 16 bits superiores (h >>> 16) para lograr una distribución más uniforme.

El XOR es una operación bit a bit que compara dos bits, resultando en 1 si los bits son diferentes y 0 si son iguales. En este contexto, realizar una operación bit a bit de XOR entre el código hash y sus 16 bits superiores (obtenidos utilizando el operador de desplazamiento derecho no signado >>>) ayuda a mezclar los bits, llevando a un código hash más uniformemente distribuido.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Arriba, puede ver el método estático de hash de la clase HashMap.

La idea es tener un código hash único para cada clave, pero la función hash podría producir el mismo código hash para claves diferentes. Esto lleva a una situación conocida como colisión. Vamos a ver cómo manejar las colisiones en la sección siguiente.

Calculo de índice

Una vez que se genera el código hash de una clave, el HashMap calcula un índice dentro del array de buckets para determinar dónde se almacenará el par clave-valor. Esto se hace utilizando una operación de AND bit a bit, que es una manera eficiente de calcular el módulo cuando la longitud del array es un número potencia de dos.

int index = (n - 1) & hash;

Aquí, estamos calculando el índice donde n es la longitud del arreglo de cubetas.

Una vez que se calcula el índice, la clave se almacena en ese índice en el arreglo de cubetas. Sin embargo, si varias claves terminan teniendo el mismo índice, causa una colisión. En dicho escenario, el HashMap lo maneja de una de dos maneras:

  • Encadenamiento/Enlazado: Cada cubeta en el arreglo es una lista enlazada de nodos. Si una clave ya existe en un índice particular y otra clave se hashea al mismo índice, se añade a la lista.

  • Arbolización: Si el número de nodos excede un cierto umbral, la lista enlazada se convierte en un árbol (Esto se introdujo en Java 8).

static final int TREEIFY_THRESHOLD = 8;

Este es el umbral que determina la arbolización.

Por lo tanto, es esencial tener una buena función de hash que distribuya uniformemente las claves a través de las cubetas y minimice las chances de colisiones.

Las operaciones de recuperación (get) y eliminación (remove) funcionan de forma similar a la operación de inserción (put). Esto es cómo:

  • Recuperación (get): Calcula el código hash usando la función de hash -> calcula el índice usando el código hash -> atraviesa la lista enlazada o árbol para encontrar el nodo con la clave coincidente.

  • Eliminación (remove): Computa el código hash usando la función hash -> calcula el índice usando el código hash -> elimina el nodo de la lista enlazada o el árbol.

Complejidad Temporal

Las operaciones básicas de un HashMap, como put, get y remove, normalmente ofrecen un tiempo de ejecución constante de O(1), asumiendo que las claves están distribuidas uniformemente. En casos donde la distribución de las claves es pobre y ocurren muchos conflictos, estas operaciones pueden degradar a una complejidad de tiempo lineal de O(n).

Bajo la transformación en árbol, donde las largas cadenas de conflictos se convierten en árboles balanceados, las operaciones de búsqueda pueden mejorar a una eficiencia de tiempo logarítmica de O(log n).

Sincronización

La implementación de HashMap no es sincronizada. Si varias threads acceden a una instancia de HashMap concurrente y iteran sobre el mapa, y si cualquiera de las threads realiza una modificación estructural (como agregar o eliminar una asociación clave-valor) en el mapa, se produce una ConcurrentModificationException.

Para evitar esto, puedes crear una instancia segura para subprocesos usando el método Collections.synchronizedMap.

Conclusión

En resumen, comprender el funcionamiento interno de un HashMap es fundamental para que los desarrolladores tomen decisiones informadas. Saber cómo se asigna una clave, cómo ocurren las colisiones y cómo pueden evitarse te ayuda a usar el HashMap de manera eficiente y efectiva.