Hash tables en JavaScript
Contenido del curso
Hash tables en JavaScript
Contenido del curso
¿Qué es una hash table?
Las hash tables son estructuras de datos que permiten almacenar pares clave-valor y acceder a ellos de manera eficiente. La idea detrás de las hash tables es usar una función matemática llamada "función hash" para asignar a cada clave un índice en un arreglo.
El funcionamiento de las hash tables se basa en dos componentes: la función hash y los buckets. La función hash es una función matemática que recibe una clave y la convierte en un índice en el arreglo. Los buckets son celdas en el arreglo donde se almacenan los valores. Cada bucket está asociado a una clave y contiene un valor.
La función hash es importante porque debe asegurarse de que la misma clave siempre produzca el mismo índice, de lo contrario, se perderá la capacidad de acceder a un valor rápidamente. Además, la función hash debe ser lo suficientemente eficiente para procesar un gran número de claves.
Las operaciones más comunes en una Hash Table son la inserción, búsqueda y eliminación de elementos.
Complejidad algorítmica
Si medimos la complejidad de los métodos de la hash table con Big o notation, podremos notar que es de lo más eficiente. Debido a que siempre se mantiene constante.
| Algoritmo | Big o notation |
|---|---|
| Inserción | O(1) |
| Búsqueda | O(1) |
| Eliminación | O(1) |
Hay distintas formas de crear e implementar una hash table en JavaScript, por lo que a continuación te enseñaré una manera para crear una con todos sus métodos.
class HashTable { constructor(size) { // Dentro del constructor se inicializa un array con un tamaño arbitrario // Para asignarlo como el tamaño total de buckets en nuestra hashTable this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(key) { // Esta función toma una "key" (puede ser una cadena, número, etc.) // Para poder calcular el índice del bucket donde el valor será almacenado let total = 0; // En este caso el algoritmo para crear un hash es muy sencillo // Para calcular el hash, se suman los valores ASCII de cada caracter de la key // y se toma el resto de la división de esta suma entre el total de buckets. for (let i = 0; i < key.length; i++) { total += key.charCodeAt(i); } return total % this.numBuckets; } insert(key, value) { // Este método toma una key y un value, y los almacena en la hash table // Primero se calcula el índice usando la función hash let index = this.hash(key); // si ese bucket no existe, se inicializa como un array vacío. if (!this.buckets[index]){ this.buckets[index] = []; } // Luego se agrega un arreglo con la key y el value al bucket this.buckets[index].push([key, value]); } get(key) { // Esta función toma una key y retorna el valor almacenado en la hash table // Primero se calcula el índice usando la función hash let index = this.hash(key); // si ese bucket no existe, se retorna null. if (!this.buckets[index]){ return null } // Si el bucket existe, se recorre el array en busca de un arreglo // que tenga la key especificada for (let i = 0; i < this.buckets[index].length; i++) { // Si se encuentra ese bucket, se retorna su value correspondiente. if (this.buckets[index][i][0] === key) { return this.buckets[index][i][1]; } } //Si no se encuentra la key, se retorna null. return null; } retrieveAll() { // Esta función retorna un array con todos los valores almacenados // Se recorren todos los buckets y, si existen, se agrega cada value a un array let allValues = []; for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { allValues.push(this.buckets[i][j][1]); } } } // Para finalmente retornarlo. return allValues; } }
Los ejemplos de uso de las hash tables son muy variados. Por ejemplo, se pueden usar para implementar cachés, para hacer búsquedas en grandes cantidades de datos, para implementar diccionarios y mucho más.
Carina Payleman
Fabrizio López
Nicolas Martinez
HERNANDO RAMIREZ
Leonardo de los angeles Espinoza Hernandez
HERNANDO RAMIREZ
Algunos usos prácticos de las hash tables del desarrollo web: .
Por lo que veo en el código, un índice (hash) puede contener más de un valor. ¿En la práctica no se supone que un hash es único? en el método get, por ejemplo, cuando busca por key, siempre devolvería el primer valor, ya que todos los elementos dentro tendrían que tener el mismo key, ¿no?
En una tabla hash, cada clave debería tener un hash único y distinto, lo que significa que cada índice en la tabla hash debería contener solo un valor. Sin embargo, en la práctica, es posible que dos claves diferentes produzcan el mismo hash debido a la función hash utilizada, lo que se conoce como colisión de hash. En este caso, es posible que un índice contenga más de un valor, lo que se llama una lista de colisión. Cuando se busca por una clave en la tabla hash y hay una lista de colisión, el método get devolverá el primer valor que se agregó a la lista de colisión. Es importante tener en cuenta la posibilidad de colisiones de hash al diseñar e implementar una tabla hash y manejar adecuadamente las listas de colisión en caso de que ocurran.
si se implementa ese codigo sale error, lo pueden corregir?
¡Hola @hramirezpa!
¿Qué tipo de error te genera? Los métodos los probamos y no obtuvimos algún error, si nos puedes dejar a detalle que es lo que pasa podemos arreglarlo lo más pronto posible
Hola Leo, bueno no se si es error o inconsistencia o la tabla almacena mas de una vez la misma llave, ejemplo:
const test = new HashTable(10) test.insert("uno", 1) test.insert("dos", 2) test.insert("tres", 3) // Envio la misma información: test.insert("uno", 1) test.insert("dos", 2) console.log(test.retrieveAll()) //Resultado: (5) [2, 3, 2, 1, 1]
Pense que esta clase permitia almacenar solo una clave-valor, por favor me aclara? Muchas gracias
