No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Construyendo una Hash Table

11/29
Recursos

Aportes 27

Preguntas 10

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

驴Qu茅 es un hash?

Seg煤n la definici贸n de Kaspersky:
.
鈥淯na funci贸n criptogr谩fica hash- usualmente conocida como 鈥渉ash鈥- 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);

Cuando hago backend y necesito hashes aleatorios uso dos

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));

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

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

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 = [ [鈥榗elular鈥橾,[鈥榩c鈥橾,[鈥榖alon鈥橾]. 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 鈥淒iego鈥 tendriamos en la posici贸n del hash de 鈥淒iego鈥 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 馃槂

En JavaScript, el objeto 鈥淢ap鈥 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!