Comment la structure de données HashMap est-elle…

HashMap en Java se basa en principios de hashing. Almacena pares de "clave-valor".

Estructura interna:

Array de buckets (contenedores). Cada bucket es una lista enlazada (o un árbol, desde Java 8, cuando hay muchas colisiones).
Al agregar un elemento (put):
1. Se calcula el código hash de la clave (key.hashCode()).
2. El código hash se modifica para una mejor distribución (hash).
3. Usando el hash modificado y el tamaño del array de buckets, se calcula el índice del bucket donde se colocará el elemento (hash & (tamaño_del_array - 1)).
4. El elemento (par "clave-valor" en forma de objeto Node) se coloca en ese bucket. Si el bucket ya contiene elementos, el nuevo elemento se añade al inicio de la lista enlazada o árbol.
5. Al agregar, se verifica si la clave ya existe: se usa el método equals() para comparar las claves dentro del bucket. Si la clave se encuentra, se actualiza el valor.
Al obtener un elemento (get):
1. También se calcula el índice del bucket por la clave.
2. Dentro del bucket, se busca el elemento por la clave, usando los métodos hashCode() y equals().
3. Se devuelve el valor asociado.

Organización:

Colisiones: Si varias claves tienen el mismo código hash y caen en un mismo bucket, los elementos se almacenan en forma de lista enlazada. Desde Java 8, cuando el número de elementos en un bucket supera un umbral (usualmente 8), la lista enlazada se transforma en un árbol para búsquedas más rápidas (O(log n) en lugar de O(n)).
Redimensionamiento: Cuando el número de elementos supera el "factor de carga" (load factor * capacity), HashMap aumenta el tamaño del array interno de buckets (usualmente al doble) y vuelve a hashear todos los elementos. Es una operación costosa (O(n)).
Parámetros:
- capacity: tamaño inicial del array de buckets (por defecto 16).
- load factor: umbral de carga (por defecto 0.75). Define cuándo se realiza el redimensionamiento.

Por qué son importantes hashCode() y equals():

La correcta operación de HashMap depende de la correcta implementación de estos métodos.
Si equals() devuelve true para dos objetos, entonces hashCode() debe devolver el mismo valor.
Una implementación incorrecta puede hacer que los elementos no se encuentren (get devolverá null), incluso si fueron añadidos.

Ejemplo de estructura Node:

// Solo interno
static class Node<K,V> implements Map.Entry<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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

HashMap offre une insertion, une récupération et une suppression rapides (en moyenne O(1)) lorsque la distribution des hashes est uniforme. En cas de fortes collisions, l'opération peut devenir O(n) ou O(log n) avec des arbres.

Il n'est pas thread-safe. Pour une utilisation dans des environnements concurrents, il faut utiliser ConcurrentHashMap ou Collections.synchronizedMap(new HashMap<...>(...)).

Comment la structure de données HashMap est-elle organisée en Java?