Construyendo una Hash Table

¿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.

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 😃

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”.

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

Les recomiendo este video:
https://www.youtube.com/watch?v=LluB6jU-SwY

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

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!