Tablas hash y resolución de colisiones

Buscar en un arreglo desordenado cuesta recorrerlo entero; en uno ordenado, partirlo a la mitad varias veces. Una tabla hash promete algo mejor: calcular dónde está el dato y acceder directo, sin comparar con nadie. La promesa se cumple mientras las colisiones se mantengan bajo control.

De la clave a un índice

La idea es reducir la clave a un número y usarlo como índice. Una función de hash toma la clave y devuelve un entero; el resto de la división por el tamaño de la tabla da la posición:

Si la función reparte parejo, cada clave aterriza en un lugar distinto y leer o escribir cuesta $O(1)$. El arreglo dejó de recorrerse: se calcula.

Las colisiones son inevitables por conteo

El problema es inevitable por conteo: las claves posibles son muchísimas más que las $m$ posiciones, así que dos claves distintas van a compartir posición. Eso es una colisión, y no es un error de la función de hash sino una consecuencia del tamaño.

De hecho llegan antes de lo que la intuición sugiere: con una tabla de 365 posiciones alcanzan 23 claves al azar para que la probabilidad de colisión pase el 50%. Es la paradoja del cumpleaños. Una tabla hash no evita colisiones: las administra.

Encadenamiento: una lista por posición

La primera estrategia es el encadenamiento: cada posición guarda una lista con todas las claves que cayeron ahí. Insertar agrega a la lista; buscar recorre sólo esa lista y compara las claves completas, porque hashes iguales no significan claves iguales.

El costo de una operación es el largo de su lista. Con $n$ claves en $m$ posiciones, el promedio es el factor de carga $\alpha = n/m$: constante mientras la tabla crezca junto con los datos. En el peor caso, con todas las claves en la misma lista, degenera a $O(n)$.

Direccionamiento abierto: todo dentro del arreglo

La otra estrategia guarda todo dentro del arreglo, sin listas. Si la posición está ocupada, se prueba otra siguiendo una secuencia fija: la siguiente libre en sondeo lineal, saltos cuadráticos, o un segundo hash que define el paso.

El sondeo lineal aprovecha la caché porque recorre posiciones contiguas, pero forma grupos: un bloque ocupado atrae más choques y se alarga solo. El doble hashing dispersa mejor esos grupos a cambio de saltar por la memoria.

Borrar tiene una trampa

Borrar con direccionamiento abierto tiene una trampa. Si simplemente vaciamos la posición, cortamos la cadena de sondeo y una clave que estaba más adelante se vuelve inalcanzable: la búsqueda ve un hueco y se detiene antes de llegar.

La solución habitual es marcar la posición como borrada en vez de vaciarla. La búsqueda sigue de largo por esas marcas y la inserción las reutiliza. Acumular marcas degrada la tabla, así que conviene reconstruirla cada tanto.

Redimensionar cuando la carga sube

Cuando el factor de carga crece, todo se vuelve más lento: las listas se alargan y los sondeos recorren más posiciones. Por eso, al pasar un umbral, la tabla se agranda —típicamente al doble— y todas las claves se reubican con el nuevo módulo.

Rehashear cuesta $O(n)$, pero se paga cada vez que la cantidad de elementos se duplica. Ese costo repartido entre las inserciones intermedias da un costo amortizado constante, el mismo argumento que sostiene a los arreglos dinámicos.

Lo que una tabla hash no da

Lo que una tabla hash no da es orden. No hay recorrido de menor a mayor, ni mínimo, ni consultas por rango: el hash justamente destruye la relación entre claves parecidas. Para eso están los árboles de búsqueda.

También depende de que las claves usadas como índice no cambien después de insertarse, y de una función de hash que no sea predecible cuando las claves vienen de afuera: entradas elegidas para colisionar convierten el caso promedio en el peor caso.

Una tabla hash, escrita

Con encadenamiento, la tabla entera cabe en unas pocas líneas. Lo único que hace falta es una función que lleve claves a índices y un arreglo de cubetas.

class HashMap<V> {
  private buckets: Array<Array<[string, V]>>;
  private size = 0;

  constructor(private capacity = 8) {
    this.buckets = Array.from({ length: capacity }, () => []);
  }

  private indexFor(key: string): number {
    let hash = 2166136261;
    for (let position = 0; position < key.length; position += 1) {
      hash ^= key.charCodeAt(position);
      hash = Math.imul(hash, 16777619);
    }
    return Math.abs(hash) % this.capacity;
  }

  set(key: string, value: V): void {
    const bucket = this.buckets[this.indexFor(key)]!;
    const existing = bucket.find(([storedKey]) => storedKey === key);
    if (existing) {
      existing[1] = value; // la clave ya estaba: se reemplaza, no se agrega
      return;
    }
    bucket.push([key, value]);
    this.size += 1;
    if (this.size / this.capacity > 0.75) this.resize();
  }

  get(key: string): V | undefined {
    return this.buckets[this.indexFor(key)]!.find(([storedKey]) => storedKey === key)?.[1];
  }
}

Hay tres cosas en ese código que son toda la estructura. La primera: indexFor no guarda nada, calcula. Por eso get no recorre la tabla, va directo a una cubeta. La segunda: la cubeta guarda la clave junto al valor, y get la compara. Sin esa comparación, dos claves que caen en la misma cubeta serían indistinguibles, y por eso un hash igual no significa claves iguales. La tercera: set busca antes de agregar, y ahí está la unicidad de las claves.

Lo que la tabla no te da

Cierre

Una tabla hash cambia comparar por calcular, y paga ese cambio administrando colisiones: encadenamiento o direccionamiento abierto, borrado con marcas, redimensión por factor de carga. Cumplidas esas condiciones da acceso constante promedio; a cambio, entrega el orden.