Java Academy · Lección

Cómo funciona HashMap

Buckets, hashing y colisiones

Cómo funciona HashMap es una lección gratuita de Java Academy en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Java Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Java Academy incluye 4 lecciones en total.

Qué almacena HashMap

Un HashMap almacena pares clave-valor y ofrece búsquedas, inserciones y eliminaciones en O(1) en promedio.

Internamente mantiene un array llamado table. Cada posición de este array se denomina bucket.

La clave determina en qué cubeta se coloca una entrada.
El valor es lo que obtiene al buscar la clave.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Calcular el hash de la clave

Cuando llama a put(key, value), el mapa llama a key.hashCode() para obtener un int.

HashMap después redistribuye esos bits mediante una función interna, de modo que incluso los códigos hash deficientes se distribuyan entre las cubetas.

El número final se reduce mediante hash & (table.length - 1) para obtener el índice de una cubeta.
La longitud de la tabla siempre es una potencia de dos, por lo que la máscara funciona.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Las cubetas en acción

Cada cubeta puede contener más de una entrada. Cuando dos claves se asignan a la misma cubeta, se produce una colisión.

Las colisiones son normales y esperables. HashMap las gestiona encadenando las entradas dentro de la cubeta.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Colisiones y encadenamiento

Antes de Java 8, todas las entradas que colisionaban se almacenaban en una lista simplemente enlazada dentro de la cubeta.

La búsqueda recorre la lista y llama a equals() hasta encontrar la clave correspondiente.

Pocas colisiones: el rendimiento sigue siendo, en la práctica, O(1).
Muchas colisiones en una cubeta: el rendimiento se aproxima a O(n) para esa cubeta.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Por qué colisionan FB y Ea

Las cadenas "FB" y "Ea" tienen el mismo hashCode() en Java. Este es un ejemplo clásico de colisión.

Aunque tengan códigos hash idénticos, el mapa las mantiene separadas porque equals() las distingue dentro de la cubeta.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Factor de carga

El factor de carga controla cuánto se llena la tabla antes de que crezca. El valor predeterminado es 0.75.

Con una capacidad de 16 y un factor de carga de 0.75, el redimensionamiento se activa al llegar a 12 entradas.
Un factor de carga menor desperdicia memoria, pero reduce las colisiones.
Un factor de carga mayor ahorra memoria, pero aumenta las colisiones.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Redimensionar la tabla

Cuando el número de entradas supera capacity * loadFactor, la tabla duplica su tamaño.

Cada entrada existente vuelve a calcular su hash y se coloca en la tabla nueva y más grande. Esta operación es costosa, por lo que dimensionar previamente la tabla es importante para mapas grandes.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Dimensionar previamente para mejorar el rendimiento

Si sabe aproximadamente cuántas entradas va a almacenar, indique una capacidad inicial para evitar redimensionamientos repetidos.

Regla práctica: capacidad inicial = expectedSize / 0.75 + 1.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Claves y valores null

HashMap permite una clave null y varios valores null.

La clave null siempre se coloca en la cubeta 0 (su hash se considera 0).
Use getOrDefault para evitar la ambigüedad entre una clave inexistente y un valor null.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

El orden de iteración no está garantizado

HashMap no ofrece ninguna garantía sobre el orden de iteración. El orden depende de los códigos hash y de la distribución de las cubetas.

Si necesita un orden predecible, use LinkedHashMap (orden de inserción) o TreeMap (orden de clasificación).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

La ruta de get(), resumida

Una búsqueda sigue estos pasos:

Calcular hashCode() y distribuir los bits.
Aplicar una máscara para encontrar el índice del bucket.
Recorrer el bucket comparando las claves con equals().
Devolver el valor coincidente o null.

Un buen hashCode junto con un equals correcto mantiene rápidos todos los pasos.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Comprobación rápida

Compruebe su comprensión de cómo HashMap encuentra un bucket.

Repaso

Ha aprendido cómo funciona HashMap internamente:

Las claves se convierten en hashes y se asignan a buckets.
Las colisiones se gestionan encadenando las entradas en un bucket.
El factor de carga (0.75) activa la duplicación y el rehashing.
Dimensionar previamente evita redimensionamientos costosos, y el orden de iteración no está garantizado.

A continuación, verá por qué hashCode por sí solo no basta sin un equals correcto.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Preguntas frecuentes

¿La lección «Cómo funciona HashMap» es gratis?

Sí — el texto completo de «Cómo funciona HashMap» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Java Academy, actualiza a CoddyKit PRO. El curso de Java Academy incluye 4 lecciones en total.

¿Qué aprenderé en «Cómo funciona HashMap»?

Buckets, hashing y colisiones Practicas Java Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Java Academy?

No se requiere experiencia previa. Java Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.

¿Cuánto tiempo toma la lección «Cómo funciona HashMap»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Java Academy?

Sí. Cada lección de Java Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

← Volver a Java Academy