Códigos hash y funciones hash

En resumen: Un código hash es un número que se calcula a partir de una clave; Map y Set lo usan para elegir la cubeta donde buscar, así que encuentran una clave rápido incluso entre un millón.

Problema

El asiento se vendió dos veces

La taquilla del teatro guarda los asientos vendidos en un diccionario: asiento → nombre del cliente. Un asiento es una clase con una fila y un número:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12), "María");

console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Iván");
console.log(bookings.size);

Salida

undefined
1
2

María compró el asiento 5/12, pero get con el mismo asiento devuelve undefined. Después Iván compra el mismo asiento, y el diccionario ahora tiene dos claves 5/12. ¿Por qué?

La idea

Hash: un número a partir de la clave

Un Map no compara la clave con todas las demás. Calcula un número entero a partir de la clave, y con él sabe dónde buscar. Ese número se llama hash (código hash). JavaScript no lo muestra: lo calcula el motor, y no hay ninguna función que lo devuelva. Para ver cómo funciona, aquí tienes una función hash para texto. La fórmula es la misma que en Java:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}

console.log(hashOf("María"));
console.log(hashOf("María"));
console.log(hashOf("Mario"));
console.log(hashOf("maría"));

Salida

74117842
74117842
74113764
103670514

• El mismo texto da el mismo número, siempre.
• Un cambio pequeño da otro número: "María", "Mario" y "maría" son tres hashes distintos.
• Un hash se calcula rápido, sin importar cuántas claves haya en el diccionario.
• charCodeAt(i) es el código del carácter. | 0 mantiene el resultado como un entero de 32 bits, como int en Java. Si crece demasiado, da la vuelta y puede volverse negativo.

Un Map usa su propia función hash, no esta. Pero la idea es la misma.

El método que produce el número se llama función hash.

Más precisamente, para curiosos

• La fórmula es s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], donde s[i] es el código de cada carácter. El bucle la calcula multiplicando por 31 en cada paso y sumando el código siguiente.

• Las funciones hash criptográficas, como SHA-256, son otra cosa. Dan un resultado largo, y en la práctica es imposible encontrar dos textos con el mismo hash. Por eso se usan para comprobar que un archivo no fue alterado y para guardar contraseñas. hashOf() sirve para búsquedas rápidas y no da esa protección.

Míralo

Las cubetas

Por dentro, un Map es un array de cubetas. El número de cubeta de una clave es el resto de dividir el hash entre el número de cubetas. Aquí el hash sale de hashOf, porque el que usa un Map no se ve:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}

const keys = ["Clara", "Luis", "Iván", "Rosa"];
const buckets = 8;
for (const key of keys) {
  const hash = hashOf(key);
  const index = ((hash % buckets) + buckets) % buckets;
  console.log(`${key} -> ${hash} -> cubeta ${index}`);
}

Paso a paso, en palabras

1. Cuatro claves y ocho cubetas vacías, numeradas del 0 al 7.
2. hashOf("Clara") es 65190183. El resto de dividir entre 8 es 7: esa es la cubeta.
3. "Luis" da 2379923, cubeta 3.
4. "Iván" da 2295226, cubeta 2.
5. "Rosa" también cae en la cubeta 3: una colisión. Las dos claves están en una misma cubeta: "Rosa" cuelga detrás de "Luis" como una cadena.
6. Se busca "Rosa": el mismo número, la misma cubeta 3. === con "Luis": no. Con "Rosa": sí.

• set calcula la cubeta y guarda ahí el par. get calcula la misma cubeta y busca solo en ella. Por eso es rápido incluso con un millón de claves.
• % en JavaScript, igual que en Java, puede dar un número negativo: -7 % 8 es -7. Por eso se escribe ((hash % buckets) + buckets) % buckets: así el resto nunca es negativo. Un número de cubeta no puede ser negativo.
• "Luis" y "Rosa" cayeron en la cubeta 3. Esto se llama colisión. De eso trata la siguiente tarjeta.

Más precisamente, para curiosos

• Cómo calcula exactamente un Map la cubeta depende del motor (V8 en Chrome y Node, otro en Firefox). El estándar del lenguaje solo dice que una búsqueda debe ser, en promedio, más rápida que recorrerlo todo.

console.log(-7 % 8, ((-7 % 8) + 8) % 8);

Salida

-7 1

Pruébalo

¿Qué cubeta?

En tu propia tabla hash, el hash de un número entero suele ser el propio número. Los números de pedido van a un diccionario con 4 cubetas.

¿Qué imprimirá el programa?

const orderIds = [6, 10, 13, 21];
for (const id of orderIds) {
  console.log(`${id} -> cubeta ${id % 4}`);
}

Respuesta

6 -> cubeta 6
10 -> cubeta 10
13 -> cubeta 13
21 -> cubeta 21

6 -> cubeta 2
10 -> cubeta 2
13 -> cubeta 1
21 -> cubeta 1

6 -> cubeta 2
10 -> cubeta 0
13 -> cubeta 1
21 -> cubeta 3

6 -> cubeta 1
10 -> cubeta 2
13 -> cubeta 3
21 -> cubeta 4

Comprobar

La idea

Colisión: el hash encuentra la cubeta, la comparación encuentra la clave

Claves distintas pueden tener el mismo hash. Con hashOf, igual que con hashCode en Java, el ejemplo más conocido es:

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}

console.log(hashOf("Aa"), hashOf("BB"));

const codes = new Map();
codes.set("Aa", 1);
codes.set("BB", 2);
console.log(codes.get("Aa"), codes.get("BB"));

Salida

2112 2112
1 2

Un Map guarda las dos claves y no las confunde. Tiene su propia función hash, y con ella las colisiones ocurren con otras claves, pero está preparado para ellas. Una cubeta guarda varios pares, y get compara la clave con cada uno hasta encontrar la que busca.

Así que los dos pasos funcionan así:

1. El hash dice en qué cubeta buscar.
2. La comparación dice cuál de las claves de la cubeta es la que buscas.

Ahora queda claro qué pasó con el asiento del teatro. Un Map compara las claves casi como ===: el texto y los números por valor, pero los objetos por referencia. Los dos objetos new Seat(5, 12) son dos objetos distintos, así que también son dos claves distintas. Una clave que es el mismo objeto sí se encuentra:

const seat = new Seat(5, 12);
const bookings = new Map();
bookings.set(seat, "María");
console.log(bookings.get(seat));

Salida

María

La idea

Sin equals ni hashCode: una clave de texto

En Java y Python, la clase dice cuándo dos objetos son iguales (equals, __eq__) y cuál es su hash (hashCode, __hash__). En JavaScript no hay forma de hacerlo. Map y Set comparan los objetos por referencia y no llaman a tus métodos. Aunque escribas equals, el Map no lo mira:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }

  equals(other) {
    return other instanceof Seat && this.row === other.row && this.number === other.number;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12), "María");

console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Iván");
console.log(bookings.size);

Salida

undefined
1
2

La solución habitual es que la clave sea texto, construido con los campos que dicen qué asiento es. El texto se compara por valor:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }

  key() {
    return `${this.row}/${this.number}`;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12).key(), "María");

console.log(bookings.get(new Seat(5, 12).key()));
console.log(bookings.size);
bookings.set(new Seat(5, 12).key(), "Iván");
console.log(bookings.size);

Salida

María
1
1

Las reglas para una clave de texto son las mismas que el contrato de Java:

• Dos objetos que son el mismo asiento dan la misma clave. Siempre.
• Dos objetos distintos dan claves distintas. Para eso está la barra entre los campos.
• En la clave van solo los campos que hacen que dos objetos sean el mismo.

Más precisamente, para curiosos

• Sin separador, las claves se confunden: el asiento 51/2 y el asiento 5/12 dan los dos "512".

console.log(`${51}${2}`, `${5}${12}`, `${51}/${2}` === `${5}/${12}`);

Salida

512 512 false

• Si también necesitas el propio objeto, guárdalo como valor: bookings.set(seat.key(), { seat, name: "María" }).

Pruébalo

Encuentra el error

El catálogo guarda los productos en un Map con una clave de texto. Dos productos con el mismo código son el mismo producto, aunque el precio haya cambiado. Pero has con el precio nuevo devuelve false:

const catalog = new Map();
const old = new Product("A-100", 25.0);
catalog.set(old.key(), old);
// El precio bajó, pero es el mismo producto.
console.log(catalog.has(new Product("A-100", 19.9).key()));

Salida

false

¿En qué línea de la clase está el error?

Elige la línea con el error.

1class Product {2 constructor(code, price) {3 this.code = code;4 this.price = price;5 }67 key() {8 return `${this.code}/${this.price}`;9 }10}

Comprobar

La idea

Las cubetas se llenan

Cuando hay muchos pares, las cubetas se alargan y las búsquedas se vuelven lentas. Por eso un Map crece:

• Por dentro, un Map también tiene que crear más cubetas cuando se llena, y repartir de nuevo las claves para seguir siendo rápido.
• Cuándo exactamente y cuánto depende del motor, y el programa no lo puede ver.
• Por eso, en promedio, set y get son rápidos, pero de vez en cuando un set tarda más.

También hay una trampa. Una clave no debe cambiar mientras está en un diccionario o en un conjunto:

const seat = new Seat(5, 12);
const sold = new Set();
sold.add(seat.key());

seat.number = 13;
console.log(sold.has(seat.key()));
console.log(sold.has(new Seat(5, 12).key()));
console.log(sold.size);

Salida

false
true
1

Aquí la trampa es otra. El conjunto guarda el texto "5/12", y este no cambia junto con el objeto. Después de seat.number = 13, la clave de seat es "5/13" y no se encuentra, mientras que "5/12" sigue en el conjunto, para un asiento que ya no está vendido a nadie. Una clave de texto es una foto del objeto en el momento de add. Por eso conviene que los campos con los que se forma la clave no cambien.

Más precisamente, para curiosos

• Una clave que es el propio objeto no pierde el objeto cuando este cambia: el Map lo encuentra por referencia. Pero entonces new Seat(5, 12) es otra clave. Hay que elegir entre «el mismo objeto» y «los mismos valores».

Ejercicio

Tus propias claves

Resuelve las tareas en tu editor.

1. Una clave para una persona. Una clase Person con nombre, apellido y edad, y un método key() que forma una clave de texto con los tres campos. Crea dos veces a Iván Pérez con 30 años y una vez con 31. Imprime las claves y cuántas personas distintas quedan en un Map con key() como clave.

Salida

Iván/Pérez/30
Iván/Pérez/30
Iván/Pérez/31
Personas distintas: 2

2. El robot del almacén. El robot empieza en la celda (0, 0) y hace los movimientos NNEESWWN: N es arriba (y + 1), S es abajo, E es a la derecha (x + 1), W es a la izquierda (W de west, oeste en inglés). ¿Cuántas celdas distintas visitó, contando la inicial? Si guardas objetos de esta clase en un Set, el programa dice 9, pero debería decir 7. Corrígelo:

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

Salida

Movimientos: 8
Celdas distintas: 7

3. El hash de un archivo. Una función hashFileContent(filePath) lee el archivo y devuelve el hash de su contenido como texto hexadecimal. Usa SHA-256 del módulo incorporado node:crypto: createHash("sha256").update(content).digest("hex"). Escribe tres informes: a.txt y b.txt con «Informe de octubre: 1250 €», y c.txt con «Informe de octubre: 1260 €». Compara sus hashes. Hashes distintos significan archivos distintos, y hashes SHA-256 iguales significan, en la práctica, archivos iguales.

Salida

a.txt: a7c494bfd367dcfa0a42a273ad6d6d1e5886537b8abf228413732e2a7d29fc8a
b.txt: a7c494bfd367dcfa0a42a273ad6d6d1e5886537b8abf228413732e2a7d29fc8a
c.txt: 55326c55a315a74bbe791da3c40262c0e4186a48b0d4c098801c64390993b9b1
a y b: iguales
a y c: distintos

Más tareas

• Tu propia tabla hash. Una continuación de la tabla de usuarios de la lección anterior, esta vez sin Map. Crea un array de 8 cubetas, cada una un array de pares de nombre de usuario y correo. La función hash es la suma de los códigos de los caracteres del nombre (charCodeAt). Escribe add, get y un método que imprima cuántos pares hay en cada cubeta.
• Un ID a partir de un correo. generateUserId(email) devuelve "U" y los primeros 8 caracteres del SHA-256 del correo en minúsculas. ¿El ID es el mismo para Ivan@Example.com y ivan@example.com? ¿Pueden dos correos distintos recibir el mismo ID? ¿Cómo lo averiguarías?
• Contar colisiones. Calcula la cubeta de las claves user1 … user1000 con hashOf de la lección para 16, 64 y 1024 cubetas, y cuenta cuántas claves caen en una cubeta que ya tiene una clave.
• La caja de zapatos. Una clase Box con ancho, alto y profundidad. Dos cajas son la misma si sus medidas son iguales, en el mismo orden. Escribe key(), y comprueba las cajas 30×20×10 y 10×20×30 en un Set.

Test

Ponte a prueba

1. ¿Por qué get en un Map es rápido incluso con un millón de claves?

Un Map mantiene las claves ordenadas y busca por mitadesUn Map es una tabla hash: a partir de la clave calcula en qué cubeta buscarUn Map recorre las claves muy rápido

2. Dos claves distintas tienen el mismo hash. ¿Qué pasa?

La segunda borra la primeraEl Map lanza un errorLas dos quedan en una misma cubeta, y al comparar las claves se distinguen

3. La clave es un objeto: bookings.set(new Seat(5, 12), "María"). ¿Qué devuelve bookings.get(new Seat(5, 12))?

"María"undefined: un Map compara los objetos por referencia, y este es otro objetoLanza un error

4. Le das a Seat un método equals(other) que compara la fila y el número. ¿Lo usará el Map?

No: Map y Set no llaman a tus métodos, y no hay forma de darles otra comparaciónSí, un Map llama a equals si existeSolo si Set también lo tiene

5. La clave del asiento es el texto ${row}/${number}. ¿Para qué hace falta la barra?

Sin ella, el asiento 51/2 y el asiento 5/12 dan la misma clave, "512"Para búsquedas más rápidasUn Map no acepta texto sin símbolos

6. El key() de un producto es ${code}/${price}, y el producto es el mismo con otro precio. ¿Qué está mal?

La clave tiene un campo que no dice qué producto es: con un precio nuevo la clave es distinta, y el producto no se encuentraEl precio debería ir primeroNada

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Archivos · Arrays: push, splice y sort · Pila, cola y lista enlazada · Map y Set
• Continúa en: Datos, switch y desestructuración · Tabla hash · Contraseñas · Dependencias: el código ajeno que ejecuta el tuyo
• Ejercicios sobre el tema: Colecciones