← Estructuras de datos desde cero · Lección 13/32

La función hash y las cubetas

1/8

Un cajón para cada clave

Buscar en un arreglo es O(n): hay que revisar uno por uno. La tabla hash hace un truco: con la clave misma calcula en qué cajón va. Ese cálculo es la función hash, y los cajones se llaman cubetas.

La función de abajo es de juguete: recorre las letras y las va mezclando en un número, que al final se recorta con % para que caiga entre 0 y el número de cubetas. Lo importante es que la misma clave siempre da el mismo número: por eso, para buscar «mango», no hay que revisar nada, sólo volver a calcular su cubeta.

leccion.js

1function hash(clave, tam) {
2  let h = 0;
3  for (const letra of clave) {
4    h = (h * 31 + letra.charCodeAt(0)) % tam;
5  }
6  return h;
7}
8
9for (const fruta of ["mango", "guayaba", "tuna", "lima"]) {
10  console.log(fruta, "-> cubeta", hash(fruta, 8));
11}
12console.log("mango otra vez ->", hash("mango", 8));

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

Cada fruta cae en una cubeta entre 0 y 7.
«mango» da el mismo número las dos veces: la función no tiene azar ni memoria.
«mango» y «guayaba» caen las dos en la cubeta 2. Guarda eso para la siguiente tarjeta.
Cambia el 8 por 16 y vuelve a correrlo: las cubetas cambian, porque dependen del tamaño de la tabla.

Toda la lección en una página

Un cajón para cada clave

1function hash(clave, tam) {
2  let h = 0;
3  for (const letra of clave) {
4    h = (h * 31 + letra.charCodeAt(0)) % tam;
5  }
6  return h;
7}
8
9for (const fruta of ["mango", "guayaba", "tuna", "lima"]) {
10  console.log(fruta, "-> cubeta", hash(fruta, 8));
11}
12console.log("mango otra vez ->", hash("mango", 8));

Cada fruta cae en una cubeta entre 0 y 7.
«mango» da el mismo número las dos veces: la función no tiene azar ni memoria.
«mango» y «guayaba» caen las dos en la cubeta 2. Guarda eso para la siguiente tarjeta.
Cambia el 8 por 16 y vuelve a correrlo: las cubetas cambian, porque dependen del tamaño de la tabla.

Colisiones: dos claves, un cajón

Hay muchísimas claves posibles y pocas cubetas, así que tarde o temprano dos claves caen en el mismo cajón. Eso es una colisión, y no es un error: hay que planearla.

La forma más común es el encadenamiento: cada cubeta es una listita de pares [clave, valor]. Para buscar, se calcula la cubeta y sólo se revisa esa listita, que normalmente tiene uno o dos elementos.

1class TablaHash {
2  constructor(tam = 4) {
3    this.tam = tam;
4    this.cubetas = Array.from({ length: tam }, () => []);
5  }
6  hash(clave) {
7    let h = 0;
8    for (const letra of clave) h = (h * 31 + letra.charCodeAt(0)) % this.tam;
9    return h;
10  }
11  poner(clave, valor) {
12    const cubeta = this.cubetas[this.hash(clave)];
13    const par = cubeta.find((p) => p[0] === clave);
14    if (par) par[1] = valor;          // ya estaba: se actualiza
15    else cubeta.push([clave, valor]); // nueva: al final de su cubeta
16  }
17  obtener(clave) {
18    const cubeta = this.cubetas[this.hash(clave)];
19    const par = cubeta.find((p) => p[0] === clave);
20    return par ? par[1] : undefined;
21  }
22}
23
24const precios = new TablaHash(4);
25precios.poner("mango", 25);
26precios.poner("guayaba", 30);
27precios.poner("tuna", 18);
28precios.poner("lima", 12);
29precios.poner("mango", 28);
30console.log(precios.obtener("mango"));
31console.log(precios.obtener("kiwi"));
32console.log(precios.cubetas);

«mango» vale 28: el segundo poner actualizó el par en vez de duplicarlo.
«kiwi» no está y sale undefined.
En la última línea se ven las cuatro cubetas por dentro, igual que en el dibujo: la tercera (la 2) tiene a «mango» y «guayaba», la colisión de la tarjeta anterior. La última quedó vacía.

Factor de carga: crecer a tiempo

Si metes mil claves en cuatro cubetas, cada listita tendrá unas 250 y buscar vuelve a ser lento. Por eso se vigila el factor de carga: elementos entre cubetas. Cuando pasa de cierto límite (muchas implementaciones usan 0.75), la tabla duplica sus cubetas y vuelve a acomodar todo (eso se llama *rehash*).

Rehacer cuesta O(n), pero pasa tan pocas veces que, repartido entre todas las inserciones, sale O(1) en promedio. El peor caso sigue siendo O(n): si la función hash es mala y todo cae en la misma cubeta, la tabla es un arreglo disfrazado. Abajo se compara una función buena con una que sólo mira el largo de la palabra.

1function buena(clave, tam) {
2  let h = 0;
3  for (const letra of clave) h = (h * 31 + letra.charCodeAt(0)) % tam;
4  return h;
5}
6function mala(clave, tam) {
7  return clave.length % tam;   // sólo mira cuántas letras tiene
8}
9
10function peorCubeta(funcion, claves, tam) {
11  const cuenta = new Array(tam).fill(0);
12  for (const c of claves) cuenta[funcion(c, tam)]++;
13  return Math.max(...cuenta);
14}
15
16// 1000 claves de 4 letras: "c000", "c001", ...
17const claves = [];
18for (let i = 0; i < 1000; i++) claves.push("c" + String(i).padStart(3, "0"));
19
20console.log("buena: la cubeta más llena tiene", peorCubeta(buena, claves, 1024));
21console.log("mala:  la cubeta más llena tiene", peorCubeta(mala, claves, 1024));
22console.log("factor de carga:", 1000 / 1024);

Con la función buena, la cubeta más llena tiene 5 claves: buscar sigue siendo casi inmediato.
Con la mala, las 1000 claves miden 4 letras y caen todas en la misma cubeta: buscar es O(n).
El factor de carga es 0.98: pasa de 0.75, así que una tabla real ya habría duplicado sus cubetas.