You don't have access to this class

Keep learning! Join and start boosting your career

Aprovecha el precio especial y haz tu profesión a prueba de IA

Antes: $249

Currency
$209
Suscríbete

Termina en:

1 Días
4 Hrs
56 Min
10 Seg

Construyendo una Hash Table

11/29
Resources

How to build a hash table in JavaScript?

Hash tables are a powerful and versatile data structure used extensively in programming. They are essentially an object that generates a hash to efficiently store and search data. In this guide, we will explore how to build a hash table in JavaScript, highlighting key steps and essential concepts.

Where do we start?

The first step in creating a hash table is to define the class in JavaScript. Within this class, we must include a constructor that initializes the size of the hash table. This translates into the number of "buckets" or compartments that will be available to store data. Here is an example of what this looks like in code:

 {class HashTable { constructor(size) { this.data = new Array(size); }}

In this case, the array created has 50 spaces, allowing you to store data efficiently.

How is a hash function implemented?

The hash function is a critical piece in generating a unique identifier for each piece of data we want to store. Although, in a real project, a hash function is rarely implemented from scratch, for learning purposes, you can build a simple one that generates a random number related to the key entered:

hashFunc(key) { let hash = 0; for (let i = 0; i < key.length;  i++) { hash = (hash + key.charCodeAt(i) * i) % this.data.length; } return hash;}

It is important to remember that, in most applications, already existing hash functions that are robust and optimized are used.

How to add elements in the hash table?

The set method is key to adding elements to the hash table. This function takes two important parameters: the key and the value. It uses the key to generate a hash that will indicate the location of the value within the hash table:

set(key, value) { const address = this.hashFunc(key); if (!this.data[address]) { this.data[address] = []; } this.data[address].push([key, value]); return this.data;}

This method handles collisions efficiently. If two different keys generate the same hash, the value is placed in a sublist of the corresponding bucket, preserving both entries.

What happens during a collision?

A collision occurs when two different keys generate the same hash. In this scenario, it is crucial to handle the collision to avoid data loss. By implementing the use of chained lists (sublists within a bucket), we ensure that each entry is properly preserved:

set(key, value) { const address = this.hashFunc(key); if (!this.data[address]) { this.data[address] = []; } this.data[address].push([key, value]);}

In this way, each bucket can contain multiple key-value pairs, ensuring that information is not overwritten.

How does it behave when interacting with the JavaScript terminal?

In the development environment, we can test the performance of our hash table. We start by testing if the buckets are created correctly:

const myHashTable = new HashTable(50);

Subsequently, we store exemplary data:

myHashTable.set('Diego', 1990);myHashTable.set('Mariana', 1998);myHashTable.set('Alejandra', 2000);

We verify the integrity of our system by observing that each data is stored without being overwritten. In the face of collisions, we see that the chained list mechanism works perfectly.

Now, you have a solid understanding of how to build a hash table in JavaScript. As you progress, you will see how concepts such as storage efficiency and collision handling are applicable in multiple contexts in software development. Keep learning and experimenting!

Contributions 29

Questions 11

Sort by:

Want to see more contributions, questions and answers from the community?

¿Qué es un hash?

Según la definición de Kaspersky:
.
“Una función criptográfica hash- usualmente conocida como “hash”- es un algoritmo matemático que transforma cualquier bloque arbitrario de datos en una nueva serie de caracteres con una longitud fija. Independientemente de la longitud de los datos de entrada, el valor hash de salida tendrá siempre la misma longitud.”
.
En pocas palabras, un hash es un string aleatorio que se genera a partir de un string que le pasamos nosotros, este string que se genera tendrá una longitud fija, no importa si el string que nosotros le pasamos es muy largo.
.
El hash se suele usar mucho al momento de encriptar contraseñas, y la forma de calcularlos es mediante un algoritmo matemático 😉

**La clase inicializada ** 🤓🤓

class HashTable{
    constructor(size){
        this.data = new Array(size);
    }
    hashMethod(key){
        let hash = 0;
        for(let i = 0; i < key.length;i++){
            hash = (hash + key.charCodeAt(i)*i) % this.data.length;
        }
        return hash;
    }
}
const myHashTable = new HashTable(50);

Compañeros, les comparto este vídeo que explica muy bien lo que es un hash y con ejemplos para no dejar dudas. Espero lo disfruten.
https://www.youtube.com/watch?v=GctssJjiqG4

estuve mirando un video que dice que el Hash Table es el que se utililiza para detectar canciones solo con escucharlas. Interpreta las ondas en codigo binario y de esa manera las encuentra las canciones. increible ¿no?

👩‍💻 Código de la clase

class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }
  hashMethod(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }
  set(key, value) {
    const address = this.hashMethod(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }
}

const myHashTable = new HashTable(50);
myHashTable.set('Diego', 1990);
myHashTable.set('Mariana', 1998);
console.log(myHashTable.set('Alejandra', 2000));

Las hash table ya estan implementadas en JavaScript con la palabra reservada Map
para mas informacion sobre la misma aqui les dejo un link

En el minuto 10:08 es en el 41, no en el 30. Nose si le servirá a alguien pero es bueno aclararlo!

Acá hay un recurso que puede ayudar a complementar la clase.
https://www.youtube.com/watch?v=0M_kIqhwbFo

Hola! Cree una breve explicacion de como funciona una de las partes mas importantes de la funcion! Espero que les guste!

Esta es la parte mas importante:

set(key,value){
        const address = this.hashMethod(key);
        if(!this.data[address]) {
            this.data[address] = [];
        } 
        this.data[address].push([key,value]);
        return this.data;
    }
}

  1. const address = this.hashMethod(key); creamos una direccion random con el hash method.
  2. if(!this.data[address]) Esto es una de las cosas mas importantes, lo que compruebo con esto es asi: (!this.data[address]). BIEN, esto es asi:
  3. voy a traer el array = this.data, y voy a comprobar si hay un addres(una posicion) libre,por ahora el array se ve asi posicion:[ ] Entonces, posicion = address. digo,che, ya hay un address con este valor? si no lo hay, agragame al array una clave valor, asi todo queda asi: address[key,value] ahora, si justo dio la casualidad de que esta direccion(address) este ocupada, hagamos que el array se vea asi: addres[ [key,value],[key,value] ] esto hace referncia a una colision. Es cecir, en el codigo, esta es la dolicion: this.data[address].push([key,value]); La colicion surge siempre y cuando, ya el array que la direccion(address) por la funcion hash, me dijo que ponga mi data ,YA ESTABA OCUPADO.
  4. Explicacion mas clara de como funciona el if(!this.data[address]). Para entender esto hay que entender que this.data, es lo mismo que decir const array = []. y que el address que se me da no es un dato dentro de el array, el address que se me da, es una POSICION/DIRECCION para encontrar un array con o sin datos. por lo tanto, cuanto hacemos esto this.data[address], lo que hacemos en pasos sencillos es esto: const array = [ [‘celular’],[‘pc’],[‘balon’]]. this.data[address] es literalmente lo mismo que decir: array[0] esta ocupado?Si o no? si no lo esta,ocupalo, si lo esta, hacele un push y mete otro dato.
<h4>Esta estructura de datos es perfecta para resolver problemas que tengan que ver con búsquedas.</h4>

Las hash tienen distintos métodos, entre ellos están

  • insert: que inserta un elemento en la tabla.
  • search: buscar un elemento por key
  • delete: borra un elemento

El problema de las hash
La colicion: en ocaciones puede ocurrir que cuando pasemos por la hash function un key distinto a todos los key anteriores, nos puede retornar un hash repetido. Eso hace que tengamos dos elementos guardados con el mismo hash, y como te estas imagianando eso es un problema bastante feo y adivina, no hay manera de evitar esto.
Pero la colision se puede tratar, y la manera de hacerlo es curiosamente con otra estructura de datos, las linked list (listas enlazada)

no le entiendo mucho, les recomiendo ver 6 ESTRUCTURAS de DATOS que todo INGENIERO debería CONOCER
en el canal de betatech, esta mas claro ahi

No deberiamos en el metodo set buscar si la key ya estaba en el array de colisiones y remplazar ese indice?

En caso contrario si, por ejemplo, llamo el método set 50 con la key “Diego” tendriamos en la posición del hash de “Diego” 50 elementos. Yo se que podríamos en este escenario sencillamente escoger la ultima ocurrencia de la llave, pero seria bastante menos eficiente, no?

Existen múltiples algoritmos para generar hashes. Una de las características esperadas de los algoritmos de dichos algoritmos es que no exija mucha capacidad de cómputo y que la probabilidad de colisión sea lo más baja posible.

Uno de los algoritmos más utilizado es el SHA.

Importante de la función hash en esta implementación, es que tiene que generar números, aunque se repitan, en el rango de valores validos de los indices, en el ejemplo de 0-49, y se logro, si lo observan cuando hace la operacion %(modulo) entre la longitud del array, saludos 😃

Modifiqué un poco el código de la clase y creé dos métodos nuevos (viewHashes y viewBuckets) para poder ver a través de la consola con mayor facilidad cómo se están guardando los valores dentro de la HashTable, je je. Les comparto aquí el código y cómo se muestra en la consola ✨ Código 📝: ![](https://i.imgur.com/t3dk3Wq.png) Consola 📺: ![](https://i.imgur.com/NyOPmiL.png)

En la clase pasada un compañero (Hugo Andrés Marrugo Polo) dejó este recurso y me parece que la función hash que Diego ha diseñado es similar a la se explica en el vídeo: https://www.youtube.com/watch?v=9tZsDJ3JBUA

Voy a intentar leer hashMethod(key):

  • Está compuesto por la variable hash que empieza en cero, un bucle que la modifica y un return que la devuelve. La key se le pasa por parámetro, en el caso de “Diego”: 1990, la key es “Diego”
    hashMethod(key){
        let hash = 0
        for( ){
           
        }
        return hash
    }
  • El bucle recorre cada letra del string key desde la posición 0 hasta su longitud. En el caso de “Diego” desde 0 hasta la posición [5] (aunque ahí no hay nada 🤷🏼‍♀️)
    hashMethod(key){
        let hash = 0;
        for(let i = 0; i < key.length;i++){
        }
        return hash;
    }
  • La variable hash guarda el módulo o resto de cierto número dividido entre la longitud del array. En este caso, si ese cierto número es 51, la variable hash será 1 (el resto o módulo de dividir 51 / 50)
    hashMethod(key){
        let hash = 0;
        for(let i = 0; i < key.length;i++){
            hash = ( x ) % this.data.length;
        }
        return hash;
    }
  • Ese cierto número se calcula sumando el valor que en ese momento tenga la variable hash a otro número.
    hashMethod(key){
        let hash = 0;
        for(let i = 0; i < key.length;i++){
            hash = (hash + y) % this.data.length;
        }
        return hash;
    }
  • Y ese otro número es el producto del código Unicode de cada carácter multiplicado por su posición en el key. En “Diego”, la “D” mayúscula en Unicode es 0044 (si no lo he buscado mal), pero ocupa la posición [ 0 ] así que es 0.

  • Cuando pasemos a la “i”, aunque la variable hash seguirá valiendo 0, ocupará la posición 1, por lo que la multiplicación no nos volverá a dar 0.

    hashMethod(key){
        let hash = 0;
        for(let i = 0; i < key.length;i++){
            hash = (hash + key.charCodeAt(i)*i) % this.data.length;
        }
        return hash;
    }
  • Ese número calculado será el hash, el índice en la Hash Table que asociemos a “Diego”.
Si seteas muchas veces diferentes valores con el mismo key, deberíamos sobreescribir el valor guardado. Creo que nos falta agregar ese paso en el `set()` ```js set(key, value) { const address = this.hashMethod(key) if (!this.data\[address]) { this.data\[address] = \[] } const currentEntry = this.data\[address].find((item) => item\[0] === key) if (currentEntry) { currentEntry\[1] = value return this.data } this.data\[address].push(\[key, value]) return this.data } ```

En JavaScript, el objeto “Map” se utiliza para implementar una tabla hash. Un Map es similar a un objeto normal en JavaScript, pero tiene algunas características adicionales que lo hacen útil para almacenar pares clave-valor. Algunas de las principales características de los Map son:

Las claves pueden ser cualquier tipo de valor, incluidos objetos y tipos primitivos.
Los valores pueden ser cualquier tipo de valor.
Los Map tienen un orden de inserción, es decir, los elementos se mantienen en el orden en que se agregaron.
Los Map tienen métodos como set(), get(), has() y delete() que permiten agregar, obtener, verificar y eliminar entradas.

let studentGrades = new Map();
studentGrades.set("Alice", "A");
studentGrades.set("Bob", "B");
console.log(studentGrades.get("Alice")); // Output: A
console.log(studentGrades.has("Charlie")); // Output: false
studentGrades.delete("Bob");
console.log(studentGrades.size); // Output: 1

En este caso el primer valor del hash retornado por el hashMethod siempre sera cero =)

se puede utilizar como alguna clave binaria buena clase

Les recomiendo que bajen esta app de android:

Algorithms: Explained and Animated

Te explica con animaciones todas las estructuras de datos que se ven en este curso, tiene versión de paga, pero vale la pena para desbloquear todas las animaciones 😄

/*Como nuestra funcion hash genera el mismo valor ante mismos keys, podemos aprovhar eso y verificar nuestro valores insertados, llamandolos por el key o el valor del hash*/
class HashTable {
    constructor(size) {
        this.data = new Array(size)
    }
    hashMethod(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * i) % this.data.length;
        }
        return hash
    }
    set(key, value) {
        const address = this.hashMethod(key)
        if (!this.data[address]) {
            this.data[address] = []
        }
        this.data[address].push([key, value])
        return this.data
    }
}

//Generamos 50 buckets
const myHashTable = new HashTable(50)
console.log(myHashTable)
myHashTable.set("Diego", 1990)
myHashTable.set("Mariana", 1998)
myHashTable.set("Alejandra", 2000)
const address = myHashTable.hashMethod("Diego")
console.log(myHashTable.data[address])
console.log(myHashTable.data[10])
console.log(myHashTable)



EStá muy interesante esta estructura de datos

Comparto codigo:

class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }
  hashMethod(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }
  set(key, value) {
    const address = this.hashMethod(key);
    if(!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }
}

const myHashTable = new HashTable(50);

<h3>wao</h3>

CONSTRUYENDO UNA HASH TABLE

Una hashtable es un objeto en el cual nosotros generamos un hash atraves de la funcion de hash para poder guardar el valor de forma random en ciertos espacios que tenemos disponibles en nuestra hash table, pueden existir ciertas colisiones.

//Todo lo que implementamos desde el costructor y el metodo hashMetod
  //Es una hash function que nunca tendremos que aplicarla en codigo
    //Ya que podremos usarla de otras fuente y no hay necesidad de construirla

class HastTable{

  constructor(size){

    this.data = new Array(size);

  }

  //Con esta funcion estamos generando un numero random que es desde 0 al  60535
  hashMethod(key){

    let hash = 0;
    for(let i = 0; i < key.lenght; i++){

      hash = (hash + key.charCodeAt(i) * 1) % this.data.length;

    }
    return hash;
  }
  set(key,value){

    const address = this.hashMethod(key);

    //Con esto le estamos diciendo que si ya existeuna direccion con informacion 
      //No reescribas si mas bien agrega otro array a esa posicion y ya despues poder tener acceso
       // a esa informacion
    if(!this.data[address]){
      this.data[address] = [];

    }
    this.data[address].push(key,value);
    return this.data;
  }
}


//Generamos la instancia de mi clase hasttable y le estoy diciendo que necesito
  //50 espacios libres para la hashtable
    //Para tener espacios libres y empiece a guardar informacion ahi

const myHashTable = new HastTable(50);
myHashTable.set('Diego', 1990);
myHashTable.set('Mariana', 1998);
console.log(myHashTable.set('Alejandra', 2000));

Les dejo mi repo de github por si a alguien le sirve yo estoy implementando las estrucuturas de datos con python repo

Gran clase!