Tabla Hash (Hash Table)

Hash Table, Map, HashMap, Dictionary y Asociative son todos nombres para la misma estructura de datos. Es una de las estructuras de datos más comúnmente utilizadas.

Es una estructura de datos que implementa el tipo de dato abstracto llamado diccionario. Esta asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos almacenados a partir de una clave generada. Funciona transformando la clave con una función hash en un hash, un número que identifica la posición donde la tabla hash localiza el valor deseado.

Las tablas hash se suelen implementar sobre vectores de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Aquí te dejo un ejemplo básico de cómo se podría implementar una tabla hash en JavaScript:

class HashTable {
    constructor() {
        this.table = {};
    }

    // Agrega un elemento a la tabla hash
    put(key, value) {
        this.table[key] = value;
    }

    // Obtiene un elemento de la tabla hash
    get(key) {
        return this.table[key];
    }

    // Elimina un elemento de la tabla hash
    remove(key) {
        delete this.table[key];
    }

    // Imprime los elementos de la tabla hash
    printTable() {
        for (let key in this.table) {
            if (this.table.hasOwnProperty(key)) {
                console.log(key + " -> " + this.table[key]);
            }
        }
    }
}

// Usando la tabla hash
var hashTable = new HashTable();

hashTable.put("name", "John");
hashTable.put("age", 30);
hashTable.put("city", "New York");

hashTable.printTable(); // imprime name -> John, age -> 30, city -> New York
console.log(hashTable.get("name")); // imprime John

hashTable.remove("name");
hashTable.printTable(); // imprime age -> 30, city -> New York

En este código, la clase HashTable tiene métodos para agregar un elemento a la tabla hash (put), obtener un elemento de la tabla hash (get), eliminar un elemento de la tabla hash (remove) e imprimir los elementos de la tabla hash (printTable).

Las tablas hash se utilizan en diversos contextos, como por ejemplo:

1. En bases de datos para la indexación.
2. En estructuras de datos basadas en disco.
3. En algunos lenguajes de programación como Python y JavaScript, se usa para implementar objetos.
4. Para el mapeo de caché para un acceso rápido a los datos.
5. Para la verificación de contraseña.
6. Se usa en criptografía como un resumen de mensaje.

Enlaces de interés

• Wiki
• Microsoft Learn

Videos

Practicas

Preguntas

Retos de programación

// Completa la implementación de una tabla hash simple
class HashTable {
constructor(size = 10) {
  this.buckets = Array(size).fill(null).map(() => []);
  this.size = size;
}

// Función hash simple
hash(key) {
  let hash = 0;
  for (let char of key) {
    hash += char.charCodeAt(0);
  }
  return hash % this.size;
}

// Agrega un par clave-valor
set(key, value) {
  const idx = this.hash(key);
  // Completa aquí para manejar colisiones usando encadenamiento
  // Utiliza idx para acceder al bucket correspondiente
  // y agrega el par clave-valor usando push al bucket
}

// Obtiene el valor asociado a una clave
get(key) {
  const idx = this.hash(key);
  // Completa aquí para buscar el valor en el bucket correspondiente
}
}

function main(params) {
  // Crea una instancia de la tabla hash
  const table = new HashTable();
  
  // Agrega pares clave-valor a la tabla hash
  params.forEach((param, index) => {
      if (index % 2 === 0 && params[index + 1] !== undefined) {
      table.set(param, params[index + 1]);
      }
  });
  
  // Devuelve el valor asociado a la primera clave
  return table.get(params[0]); 
}

Aqui se mostraran tus resultados