HashMap
Estructura que implementa un array asociativo usando una función hash.
¿Qué es un HashMap?
Un HashMap es una estructura de datos que almacena pares clave-valor, lo que te permite recuperar valores mediante sus claves asociadas. Usa una función hash para calcular un índice en un arreglo de buckets o ranuras, desde donde se puede encontrar el valor deseado.
A diferencia de los arrays, donde los elementos se acceden mediante índices numéricos, los HashMaps te permiten usar cualquier tipo de dato como clave (cadenas, números, objetos) para acceder a los valores, lo que los hace muy versátiles para organizar y recuperar información.
Analogía del Mundo Real
Piensa en un HashMap como un sistema de catálogo de tarjetas de una biblioteca:
- Cada libro (valor) tiene un número de catálogo único (clave)
- El sistema de catálogo (función hash) te dice exactamente en qué estante está tu libro
- Puedes encontrar cualquier libro rápidamente sin buscar en toda la biblioteca
- Agregar o eliminar un libro es una operación simple
Otra analogía común es un diccionario, donde puedes buscar una palabra (clave) para encontrar su definición (valor).
Cómo Funciona Internamente un HashMap
-
Hashing: Cuando agregas un par clave-valor, la clave se pasa por una función hash que la convierte en un número entero (código hash).
-
Cálculo del índice: Este código hash se mapea a un índice en el arreglo subyacente (usualmente usando una operación módulo con el tamaño del arreglo).
-
Almacenamiento en buckets: El par clave-valor se almacena en el índice calculado.
-
Manejo de colisiones: Si dos claves diferentes se hashean al mismo índice (una colisión), el HashMap utiliza técnicas como encadenamiento (listas enlazadas en cada índice) o direccionamiento abierto para resolverlo.
-
Recuperación: Para obtener un valor, se aplica el mismo proceso de hashing a la clave para encontrar dónde está almacenado el valor.
Ejemplos de Código
// Creating a HashMap (using JavaScripts Map object)
const userMap = new Map();
// Adding key-value pairs
userMap.set('user123', { name: 'John Doe', role: 'Admin' });
userMap.set('user456', { name: 'Jane Smith', role: 'Editor' });
// Retrieving values
const user = userMap.get('user123');
console.log(user); // { name: 'John Doe', role: 'Admin' }
// Checking if a key exists
const hasUser = userMap.has('user789');
console.log(hasUser); // false
// Deleting a key-value pair
userMap.delete('user456');
// Iterating through all entries
for (const [key, value] of userMap) {
console.log(key, value);
}
// Getting the size
console.log(userMap.size); // 1Explicación Visual
Complejidad en Tiempo y Espacio
| Operación | Promedio | Peor Escenario |
|---|---|---|
| Acceso | O(1) | O(n) |
| Búsqueda | O(1) | O(n) |
| Inserción | O(1) | O(n) |
| Eliminación | O(1) | O(n) |
Donde n es el número de elementos en el HashMap.
El peor caso ocurre cuando hay colisiones, ocasionando que las operaciones se degraden a O(n).
Operaciones Comunes
- .set(key, value)Agrega un nuevo par clave-valor
- .get(key)Retorna el valor asociado a la clave
- .has(key)Verifica si una clave existe en el HashMap
- .delete(key)Elimina un par clave-valor
- .clear()Elimina todos los pares clave-valor
- .size()Retorna el número de pares clave-valor