Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 13/32

The hash function and the buckets

✕
1/8

A drawer for each key

Searching an array is O(n): you have to check one by one. A hash table pulls a trick: from the key itself it computes which drawer it goes in. That computation is the hash function, and the drawers are called buckets.

The function below is a toy: it walks through the letters and mixes them into a number, which at the end gets trimmed with % so it lands between 0 and the number of buckets. The key point is that the same key always gives the same number: so to find "mango" you don't check anything, you just compute its bucket again.

leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • Each fruit lands in a bucket between 0 and 7.
  • "mango" gives the same number both times: the function has no randomness and no memory.
  • "mango" and "guayaba" both land in bucket 2. Keep that in mind for the next card.
  • Change the 8 to 16 and run it again: the buckets change, because they depend on the table's size.
The whole lesson on one page

A drawer for each key

Searching an array is O(n): you have to check one by one. A hash table pulls a trick: from the key itself it computes which drawer it goes in. That computation is the hash function, and the drawers are called buckets.

The function below is a toy: it walks through the letters and mixes them into a number, which at the end gets trimmed with % so it lands between 0 and the number of buckets. The key point is that the same key always gives the same number: so to find "mango" you don't check anything, you just compute its bucket again.

function hash(clave, tam) {
  let h = 0;
  for (const letra of clave) {
    h = (h * 31 + letra.charCodeAt(0)) % tam;
  }
  return h;
}

for (const fruta of ["mango", "guayaba", "tuna", "lima"]) {
  console.log(fruta, "-> bucket", hash(fruta, 8));
}
console.log("mango again ->", hash("mango", 8));
  • Each fruit lands in a bucket between 0 and 7.
  • "mango" gives the same number both times: the function has no randomness and no memory.
  • "mango" and "guayaba" both land in bucket 2. Keep that in mind for the next card.
  • Change the 8 to 16 and run it again: the buckets change, because they depend on the table's size.

Collisions: two keys, one drawer

There are tons of possible keys and few buckets, so sooner or later two keys land in the same drawer. That's a collision, and it's not a bug: you have to plan for it.

The most common approach is chaining: each bucket is a little list of [key, value] pairs. To search, you compute the bucket and only check that little list, which usually holds one or two items.

0tuna1lima2mangoguayaba3
class TablaHash {
  constructor(tam = 4) {
    this.tam = tam;
    this.cubetas = Array.from({ length: tam }, () => []);
  }
  hash(clave) {
    let h = 0;
    for (const letra of clave) h = (h * 31 + letra.charCodeAt(0)) % this.tam;
    return h;
  }
  poner(clave, valor) {
    const cubeta = this.cubetas[this.hash(clave)];
    const par = cubeta.find((p) => p[0] === clave);
    if (par) par[1] = valor;          // already there: update it
    else cubeta.push([clave, valor]); // new: end of its bucket
  }
  obtener(clave) {
    const cubeta = this.cubetas[this.hash(clave)];
    const par = cubeta.find((p) => p[0] === clave);
    return par ? par[1] : undefined;
  }
}

const precios = new TablaHash(4);
precios.poner("mango", 25);
precios.poner("guayaba", 30);
precios.poner("tuna", 18);
precios.poner("lima", 12);
precios.poner("mango", 28);
console.log(precios.obtener("mango"));
console.log(precios.obtener("kiwi"));
console.log(precios.cubetas);
  • "mango" is 28: the second poner updated the pair instead of duplicating it.
  • "kiwi" isn't there and comes out undefined.
  • The last line shows the four buckets inside, just like the drawing: the third one (bucket 2) holds "mango" and "guayaba", the collision from the previous card. The last one is empty.

Load factor: growing in time

If you put a thousand keys in four buckets, each little list will hold about 250 and searching is slow again. So you watch the load factor: items divided by buckets. When it passes some limit (many implementations use 0.75), the table doubles its buckets and re-places everything (that's called a *rehash*).

Rehashing costs O(n), but it happens so rarely that, spread across all insertions, it comes out O(1) on average. The worst case is still O(n): if the hash function is bad and everything lands in the same bucket, the table is an array in disguise. Below, a good function is compared with one that only looks at the word's length.

function buena(clave, tam) {
  let h = 0;
  for (const letra of clave) h = (h * 31 + letra.charCodeAt(0)) % tam;
  return h;
}
function mala(clave, tam) {
  return clave.length % tam;   // only looks at how many letters it has
}

function peorCubeta(funcion, claves, tam) {
  const cuenta = new Array(tam).fill(0);
  for (const c of claves) cuenta[funcion(c, tam)]++;
  return Math.max(...cuenta);
}

// 1000 four-letter keys: "c000", "c001", ...
const claves = [];
for (let i = 0; i < 1000; i++) claves.push("c" + String(i).padStart(3, "0"));

console.log("good: fullest bucket holds", peorCubeta(buena, claves, 1024));
console.log("bad:  fullest bucket holds", peorCubeta(mala, claves, 1024));
console.log("load factor:", 1000 / 1024);
  • With the good function, the fullest bucket holds 5 keys: searching is still almost instant.
  • With the bad one, all 1000 keys are 4 letters long and all land in the same bucket: searching is O(n).
  • The load factor is 0.98: above 0.75, so a real table would already have doubled its buckets.