Cuando escribes localStorage.getItem("token"), el navegador busca por clave de forma directa, sin recorrer todo. Esa idea de "dame el valor de esta clave" sin pasar por toda la estructura es lo que hace un hashmap.
En los artículos anteriores vimos arrays y strings. Ambos son secuencias: para encontrar algo, recorres elemento por elemento, y eso es O(n). Los hashmaps resuelven ese problema de una forma bastante elegante.
Lo que encontrarás en este artículo:
- Qué es un hashmap y por qué importa
- Qué hace una función hash y qué propiedades tiene
- Cómo funciona por debajo: buckets, colisiones y cómo se resuelven
- Load factor y rehashing
- Big O y por qué el O(1) tiene un asterisco
1. ¿Qué es un hashmap?
Un hashmap almacena pares clave-valor. Tú le das una clave, él te devuelve el valor asociado.
Piénsalo como un casillero con etiquetas. Cada casillero tiene una etiqueta (la clave) y adentro hay algo guardado (el valor). Para abrir el casillero de "token", no revisas todos los casilleros uno por uno, vas directo al que tiene esa etiqueta.
Eso es lo que diferencia a un hashmap de un array. Los arrays buscan por índice numérico: array[0], array[5]. Los hashmaps buscan por cualquier clave: "nombre", "email", "token". Y el tiempo de búsqueda es prácticamente el mismo sin importar cuántos pares haya guardados.
En distintos lenguajes lo conoces con nombres diferentes, aunque todos hacen lo mismo:
| Lenguaje | Nombre |
|---|---|
| Python | dict |
| JavaScript | Map |
| Java | HashMap |
| Go | map |
En JavaScript se usa así:
const mapa = new Map();
mapa.set("token", "abc123");
mapa.set("userId", 42);
console.log(mapa.get("token")); // "abc123"
2. ¿Qué hace la función hash?
¿Cómo hace el hashmap para ir directo al valor sin recorrer todo? Por debajo, un hashmap vive sobre un array, y los arrays solo entienden índices numéricos. Entonces necesitamos convertir la clave "token" en un número. Eso pasa en dos pasos.
Primero, la función hash toma la clave y devuelve un hash code, que es un número (puede ser muy grande):
hash("token") → 8472361
hash("nombre") → 23847
hash("email") → 91234
Después, ese número se reduce al rango de buckets disponibles. Si el array tiene 8 buckets, lo más común es aplicar módulo:
8472361 % 8 = 1
23847 % 8 = 7
91234 % 8 = 3
Ese resultado sí es el índice del bucket donde se guarda el par. Por eso los tamaños del array casi siempre son potencias de 2.
Para que una función hash sea útil, necesita tres propiedades:
Determinista. La misma clave siempre produce el mismo número. Si hash("token") hoy devuelve 1, mañana también devuelve 1. Sin esto, nunca encontrarías lo que guardaste.
Distribución uniforme. Los resultados deben repartirse de forma pareja entre todos los buckets disponibles. Si todos los valores caen en el mismo índice, el hashmap pierde su ventaja.
Rápida de calcular. La función hash se ejecuta en cada lectura y escritura. Si fuera lenta, arruinaría el O(1).
Nota: la función hash de un hashmap no es lo mismo que el hashing criptográfico (SHA-256, bcrypt). El criptográfico está diseñado para ser difícil de revertir y resistente a ataques, mientras que el de un hashmap solo necesita ser rápido y distribuir bien.
3. ¿Cómo funciona un hashmap por debajo?
Ya sabemos que el hashmap vive sobre un array y que la función hash, junto con el módulo, convierte claves en índices. Veamos qué pasa en la práctica.
Buckets
Cada posición del array interno se llama bucket. El hashmap empieza con un tamaño fijo, generalmente una potencia de 2 (8, 16, 32...). Cuando guardas un par clave-valor, el índice resultante decide en qué bucket cae.
Colisiones
El espacio de claves posibles es enorme (cualquier string, número, objeto), pero el número de buckets es finito, así que tarde o temprano dos claves distintas van a caer en el mismo bucket. Puede pasar porque la función hash devolvió el mismo número, o porque devolvió números distintos que al aplicar el módulo cayeron en el mismo índice. Eso es una colisión, y manejarla bien es parte de cualquier implementación seria de hashmap.
hash("token") % 8 = 1
hash("rol") % 8 = 1 ← colisión
Chaining (encadenamiento)
Una estrategia clásica es que cada bucket no guarde un solo par, sino una lista de todos los pares que cayeron ahí. Cuando hay colisión, el nuevo par se agrega a la lista del bucket.
Para buscar, vas al bucket correcto y recorres la lista hasta encontrar la clave exacta.
Open addressing (direccionamiento abierto)
La otra estrategia es que si el bucket está ocupado, buscas el siguiente disponible. No hay listas, todos los pares viven directamente en el array.
Hay varias formas de "buscar el siguiente":
- Linear probing: revisa el siguiente bucket, luego el siguiente, y así.
- Quadratic probing: salta de forma cuadrática (1, 4, 9, 16...) para evitar agrupar colisiones.
- Double hashing: aplica una segunda función hash para calcular el salto.
4. ¿Cuándo crece un hashmap? Load factor y rehashing
Hay un número que el hashmap monitorea constantemente: el load factor.
load factor = elementos guardados / número de buckets
Si tienes 8 buckets y 6 elementos guardados, tu load factor es 0.75. Cuando ese número supera cierto umbral (0.75 es el valor típico), el hashmap sabe que está demasiado lleno y que las colisiones van a empezar a afectar el rendimiento.
Cuando eso pasa, hace rehashing: crea un array interno más grande (generalmente el doble) y redistribuye los pares existentes. Como numBuckets cambió, el mismo hash code aplicado al módulo cae en un índice distinto, así que cada par puede terminar en otro bucket.
5. ¿Cuál es el Big O de un hashmap?
| Operación | Caso promedio | Peor caso |
|---|---|---|
set(k, v) |
O(1)* | O(n) |
get(k) |
O(1) | O(n) |
delete(k) |
O(1) | O(n) |
has(k) |
O(1) | O(n) |
* Amortizado. Ocasionalmente O(n) cuando ocurre un rehashing.
El peor caso O(n) existe, pero es teórico en la práctica. Ocurre cuando todas las claves caen en el mismo bucket, y como dentro de ese bucket toca recorrer todos los pares para encontrar el correcto, la búsqueda termina siendo lineal. Con una buena función hash y un load factor controlado, eso no pasa.
Con implementaciones modernas estás casi siempre en O(1), y esa es la razón por la que los hashmaps son la primera herramienta que buscas cuando necesitas búsquedas rápidas. Buscar en un array es O(n) porque tienes que recorrerlo, buscar en un hashmap con la clave es O(1), y esa diferencia se vuelve enorme cuando tienes miles o millones de elementos.
La próxima vez que uses localStorage.getItem("token"), ya sabes qué está pasando por debajo.
Si el artículo te sirvió, deja un ❤️ y nos vemos en el siguiente. 🙌🏻
Top comments (0)