Uso de Hashmaps en JavaScript: Mapeo de Keys a Values en Estructuras de Datos

¿Qué son los Hashmaps?

Los hashmaps son una estructura de datos que almacena pares clave-valor, donde cada clave es única y se mapea a un valor. La clave se usa para indexar el valor, permitiendo una recuperación rápida del valor asociado. Los hashmaps usan una función hash para calcular un índice para almacenar y recuperar valores. La función hash toma la clave como entrada y genera un código hash único, que luego se usa para determinar el índice donde se almacenará el valor en el array o bucket.

Hashmaps vs Objetos de JavaScript

Los objetos de JavaScript también pueden almacenar pares clave-valor, similar a los hashmaps. Sin embargo, los hashmaps ofrecen ventajas sobre los objetos:

1. Tipos de Clave: Los hashmaps permiten usar cualquier tipo de dato como clave, incluyendo objetos, arrays y funciones. Los objetos de JavaScript están limitados a usar solo strings y símbolos como claves.

   const hashmap = new Map();
   hashmap.set({ name: 'John' }, 25);
   hashmap.set([1, 2, 3], 'array');
   
   const obj = {};
   obj[{ name: 'John' }] = 25; // Inválido: Los objetos no pueden usarse como claves en objetos

2. Mantenimiento del Orden: Los hashmaps mantienen el orden de inserción de los elementos, lo que significa que el orden en el que se agregan los pares clave-valor al hashmap se preserva. Los objetos de JavaScript no garantizan ningún orden de sus propiedades.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   hashmap.set('c', 3);
   console.log(Array.from(hashmap.keys())); // Salida: ['a', 'b', 'c']
   
   const obj = { a: 1, b: 2, c: 3 };
   console.log(Object.keys(obj)); // Salida: ['a', 'b', 'c'] (No garantizado)

3. Seguimiento del Tamaño: Los hashmaps proporcionan métodos como size() para obtener el número de elementos almacenados en el hashmap. Con los objetos de JavaScript, necesitarías llevar un seguimiento manual del número de propiedades o usar Object.keys(obj).length para determinar el tamaño.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   console.log(hashmap.size); // Salida: 2
   
   const obj = { a: 1, b: 2 };
   console.log(Object.keys(obj).length); // Salida: 2

Complejidad Temporal de las Operaciones de Hashmap

Una de las principales ventajas de los hashmaps es su complejidad temporal para las operaciones básicas. Los hashmaps proporcionan una complejidad temporal constante, denotada como O(1), para las siguientes operaciones:

1. Inserción: Agregar un nuevo par clave-valor al hashmap es una operación O(1). La función hash se usa para calcular el índice, y el par clave-valor se almacena en ese índice en el array o bucket.

2. Eliminación: Eliminar un par clave-valor del hashmap también es una operación O(1). La función hash se usa para localizar el índice donde se almacena el par clave-valor, y luego se elimina de ese índice.

3. Búsqueda: Recuperar el valor asociado con una clave dada es una operación O(1). La función hash se usa para calcular el índice basado en la clave, y el valor puede ser accedido en ese índice.

const cache = new Map();

function fetchData(key) {
  if (cache.has(key)) {
    return cache.get(key); // Recuperar datos del caché (búsqueda O(1))
  } else {
    const data = fetchFromAPI(key); // Obtener datos de la API
    cache.set(key, data); // Almacenar datos en caché (inserción O(1))
    return data;
  }
}

Creando un Hashmap

Para crear un nuevo hashmap, usa el constructor new Map(). Esto crea un hashmap vacío para almacenar pares clave-valor.

const myHashmap = new Map();

Por ejemplo, para crear un hashmap para almacenar datos de estudiantes:

const studentMap = new Map();

Agregando Pares Clave-Valor

Para agregar un nuevo par clave-valor al hashmap, usa el método set(). Toma dos argumentos: la clave y el valor.

myHashmap.set('name', 'John');
myHashmap.set('age', 25);

En el ejemplo anterior, agregamos dos pares clave-valor al myHashmap: 'name' se mapea a 'John' y 'age' se mapea a 25.

Agreguemos algunos datos de estudiantes a nuestro studentMap:

studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

Obteniendo Valores

Para obtener el valor de una clave dada, usa el método get(). Toma la clave como argumento y devuelve el valor.

const name = myHashmap.get('name');
console.log(name); // Salida: 'John'

En este ejemplo, obtenemos el valor para la clave 'name' del myHashmap, que es 'John'.

Para obtener los datos de un estudiante específico de studentMap:

const student = studentMap.get('2');
console.log(student); // Salida: { name: 'Alice', age: 22, major: 'Mathematics' }

Verificando la Existencia de una Clave

Para verificar si una clave existe en el hashmap, usa el método has(). Toma la clave como argumento y devuelve un valor booleano.

const hasAge = myHashmap.has('age');
console.log(hasAge); // Salida: true

Aquí, verificamos si la clave 'age' existe en el myHashmap usando el método has(), que devuelve true.

Verificando si un estudiante con ID '4' existe en studentMap:

const hasStudent = studentMap.has('4');
console.log(hasStudent); // Salida: false

Eliminando Pares Clave-Valor

Para eliminar un par clave-valor del hashmap, usa el método delete(). Toma la clave como argumento y elimina el par clave-valor del hashmap.

myHashmap.delete('age');
console.log(myHashmap.has('age')); // Salida: false

En este ejemplo, eliminamos el par clave-valor con la clave 'age' del myHashmap usando el método delete(). Después de la eliminación, has('age') devuelve false.

Eliminando un estudiante de studentMap:

studentMap.delete('1');
console.log(studentMap.has('1')); // Salida: false

Obteniendo el Tamaño del Hashmap

Para obtener el número de pares clave-valor en el hashmap, usa la propiedad size. Devuelve el tamaño del hashmap.

console.log(myHashmap.size); // Salida: 1

Aquí, accedemos a la propiedad size del myHashmap, que devuelve 1, indicando que hay un par clave-valor en el hashmap.

Obteniendo el número de estudiantes en studentMap:

console.log(studentMap.size); // Salida: 2

Resumen de Operaciones de Hashmap

Estas son las operaciones básicas que puedes realizar en un hashmap usando el objeto Map de JavaScript. El objeto Map proporciona una forma de trabajar con pares clave-valor y ofrece métodos para manipular y acceder a los datos en el hashmap.

El objeto Map mantiene el orden de los pares clave-valor, lo que significa que cuando iteras sobre el hashmap usando métodos como forEach() o el bucle for...of, los pares clave-valor se accederán en el orden en que fueron agregados.

El Método forEach()

El método forEach() está integrado en el objeto Map. Te permite iterar sobre cada par clave-valor en el hashmap. Usa una función callback que se ejecuta para cada par.

La función callback recibe tres parámetros:

1. value: El valor del par actual.
2. key: La clave del par actual.
3. map: El hashmap sobre el que se llamó forEach().

const shoppingCart = new Map();
shoppingCart.set('shirt', 25);
shoppingCart.set('pants', 50);
shoppingCart.set('shoes', 75);

let totalPrice = 0;

shoppingCart.forEach((price) => {
  totalPrice += price;
});

console.log(`Total Price: $${totalPrice}`);

Total Price: $150

El Bucle for...of

También puedes usar un bucle for...of para iterar sobre un hashmap. El bucle for...of funciona con objetos iterables como arrays, strings y maps.

Cuando usas for...of con un hashmap, cada bucle devuelve un array con el par [key, value].

Visualizando la Iteración de Hashmap

Aquí hay un diagrama que muestra cómo funciona iterar sobre un hashmap:

El diagrama muestra el hashmap e iterar sobre cada par clave-valor. Para cada par, lo procesamos según lo que necesitemos hacer, como cálculos, comparaciones u otras operaciones.

Tanto forEach() como for...of te permiten iterar sobre los pares clave-valor de un hashmap en JavaScript. Cuál uses depende de tus necesidades específicas. forEach() es bueno cuando quieres hacer algo para cada par, mientras que for...of es útil cuando necesitas tanto las claves como los valores en cada bucle.

Ten en cuenta que el orden de iteración en un hashmap se basa en el orden en que se agregaron los pares. El objeto Map de JavaScript mantiene este orden.

Iterar sobre hashmaps es común cuando trabajas con pares clave-valor, y JavaScript tiene estos métodos para hacerlo más fácil y rápido. Para más información sobre objetos Map e iteración, consulta los MDN Web Docs.

¿Qué son las Colisiones?

En un hashmap, las colisiones ocurren cuando dos o más claves se hashean al mismo índice. Esto significa que múltiples pares clave-valor necesitan ser almacenados en la misma posición en el array o bucket. Si no se manejan bien, las colisiones pueden llevar a la sobrescritura de datos o lentitud en la recuperación de valores.

Aquí hay un ejemplo de una colisión en un hashmap:

En este ejemplo, tanto las claves 'John' como 'Alice' se hashean al mismo índice (Índice0), causando una colisión.

Si las colisiones no se corrigen, estos problemas pueden ocurrir:

1. Sobrescritura de Datos: Si un nuevo par clave-valor se hashea al mismo índice que un par existente, el par existente podría ser sobrescrito, causando pérdida de datos.

2. Recuperación Lenta: Cuando ocurren colisiones, encontrar valores se vuelve más lento ya que el hashmap necesita hacer más pasos para encontrar el valor correcto entre los pares colisionados.

Para solucionar estos problemas, los hashmaps usan técnicas de manejo de colisiones.

Formas de Manejar Colisiones

Hay dos formas principales de manejar colisiones en hashmaps:

1. Encadenamiento Separado

• Cada índice del array o bucket del hashmap almacena una lista enlazada de pares clave-valor.
• Cuando ocurre una colisión, el nuevo par clave-valor se agrega a la lista enlazada en ese índice.
• Encontrar un valor significa recorrer la lista enlazada en el índice hasheado para encontrar el par clave-valor deseado.

2. Direccionamiento Abierto

• El direccionamiento abierto no usa listas enlazadas para manejar colisiones. En cambio, busca el siguiente índice libre en el array cuando ocurre una colisión.
• Hay diferentes formas de encontrar el siguiente índice, como sondeo lineal, sondeo cuadrático y hashing doble.
• Cuando ocurre una colisión, el hashmap usa la forma de sondeo para encontrar el siguiente espacio vacío en el array para almacenar el par clave-valor.

Mejores Prácticas para Usar Hashmaps

1. Elige una buena función hash que reduzca colisiones y distribuya claves uniformemente.
2. Piensa en el número esperado de elementos y el rendimiento deseado al elegir el tamaño inicial del hashmap.
3. Sé consciente de cómo las colisiones pueden afectar la velocidad de las operaciones del hashmap, especialmente con muchas colisiones.
4. Usa encadenamiento separado o direccionamiento abierto según lo que tu aplicación necesite, considerando aspectos como el uso de memoria y la velocidad de recuperación.