¿Qué es una tabla hash?

Una tabla hash (o matriz asociativa, diccionario) es una estructura de datos que implementa la interfaz de matriz asociativa, es decir, permite almacenar pares "clave-valor" y realizar búsquedas rápidas del valor mediante la clave.

El principio de funcionamiento se basa en el uso de una función hash, que transforma la clave en un índice (hash) dentro del array (o cubo).

Operaciones principales:

1. Inserción: Se calcula el hash de la clave, y el par "clave-valor" se coloca en el cubo correspondiente.
2. Eliminación: Se calcula el hash de la clave, se encuentra el cubo correspondiente, y se elimina el par.
3. Búsqueda: Se calcula el hash de la clave, se encuentra el cubo correspondiente, y se busca el par con la clave buscada.

Las tablas hash proporcionan en promedio un alto rendimiento para las operaciones de inserción, eliminación y búsqueda (idealmente $O(1)$). Sin embargo, en el peor de los casos (cuando hay muchas colisiones, es decir, diferentes claves que se transforman en el mismo índice), el rendimiento puede disminuir a $O(n)$.

Existen varias estrategias para resolver colisiones:

• Método de encadenamiento (Separate Chaining): En cada cubo se almacena una lista (por ejemplo, una lista enlazada) de elementos que tienen el mismo hash.
• Dirección abierta (Open Addressing): Cuando ocurre una colisión, la búsqueda de un espacio libre se realiza mediante un algoritmo predefinido (sondeo lineal, cuadrático, etc.).

Ejemplo conceptual (simplificado):

// Ejemplo de función hash simplificada
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Transformación a entero de 32 bits
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Método de encadenamiento
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Verificar si la clave ya existe para actualizar el valor
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Clave no encontrada
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Eliminado con éxito
      }
    }
    return false; // Clave no encontrada
  }
}

// Uso
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

En JavaScript, los objetos ({}) y los mapas (Map) son ejemplos de implementaciones de tablas hash. Map suele ser preferido, ya que soporta claves de cualquier tipo y mantiene el orden de inserción.

Propiedades de una buena función hash:

• Cálculo rápido.
• Distribución uniforme de los hashes para diferentes claves.
• Minimización de colisiones.