¿Qué es una tabla hash?

Una tabla hash, o matriz asociativa, es una estructura de datos que implementa la interfaz de matriz asociativa, es decir, relaciona claves con valores. Utiliza una función hash para calcular un índice, o "hash", de la cubeta o ranura donde debe estar el valor buscado.

Componentes principales:

Clave: Identificador único del elemento.
Valor: Datos asociados a la clave.
Función hash: Convierte la clave en un valor numérico (hash), que se usa para determinar el índice de la cubeta.
Cubetas (Buckets): Array donde se almacenan pares clave-valor.
Manejo de colisiones: Mecanismo para resolver situaciones en las que diferentes claves generan el mismo hash (y, por lo tanto, apuntan a la misma cubeta). Métodos comunes:
- Encadenamiento: Cada cubeta almacena una lista (por ejemplo, lista enlazada) de elementos cuyos hashes apuntan a esa cubeta.
- Dirección abierta: En caso de colisión, se busca la siguiente cubeta libre usando algoritmos como hashing lineal, cuadrático o doble hashing.

Principio de funcionamiento:

Inserción: La función hash se aplica a la clave para obtener el hash. El hash se usa para determinar el índice de la cubeta. La pareja clave-valor se almacena en esa cubeta. En caso de colisión, se aplica el método de manejo de colisiones.

// Ejemplo de inserción en una tabla hash (encadenamiento)
function insert(key, value) {
  const hash = hashFunction(key); // Calculamos el hash
  const bucketIndex = hash % tableSize; // Determinamos el índice de la cubeta

  if (!buckets[bucketIndex]) {
    buckets[bucketIndex] = []; // Creamos la lista si aún no existe
  }
  buckets[bucketIndex].push({ key, value }); // Añadimos el par a la lista
}

Búsqueda: La función hash se aplica a la clave para obtener el hash. El hash se usa para determinar el índice de la cubeta. Luego, en esa cubeta, se busca el elemento con la clave dada. En el método de encadenamiento, se busca en la lista dentro de la cubeta. En dirección abierta, se verifican otras cubetas secuencialmente hasta encontrar el elemento o determinar que no existe.

// Ejemplo de búsqueda en una tabla hash (encadenamiento)
function searchAndDelete(key) {
  const hash = hashFunction(key); // Calculamos el hash
  const bucketIndex = hash % tableSize; // Determinamos el índice de la cubeta

  if (buckets[bucketIndex]) {
    // Buscamos en la lista de la cubeta
    for (let i = 0; i < buckets[bucketIndex].length; i++) {
      if (buckets[bucketIndex][i].key === key) {
        const value = buckets[bucketIndex][i].value;
        // buckets[bucketIndex].splice(i, 1); // Para eliminar si es necesario
        return value; // Devolvemos el valor
      }
    }
  }
  return undefined; // No se encontró el elemento
}

Ventajas:

Alta velocidad en operaciones de inserción, búsqueda y eliminación en promedio (O(1)).
Uso eficiente de memoria en comparación con un array de direcciones directas (si las claves están dispersas).

Desventajas:

El rendimiento puede disminuir en caso de muchas colisiones (en el peor caso O(n)).
No mantiene el orden de inserción de los elementos.
Requiere una buena función hash para distribuir las claves uniformemente.

En JavaScript, las tablas hash se implementan mediante el objeto incorporado Map y, históricamente, Object. Map es preferido, ya que permite usar cualquier tipo de dato como clave y mantiene el orden de inserción. Object convierte todas las claves en cadenas.