Tablas hash

Con 47 guardado en una tabla de 7 cubetas, la computadora va directo a la cubeta 47 mod 7 = 5 en lugar de buscar en toda la tabla.

Convertir una clave en una posición

Hasta ahora, encontrar un valor significaba buscar: hasta n pasos en un arreglo sin ordenar o en una lista enlazada. Pero los arreglos pueden llegar a cualquier posición en un paso. ¿Y si la propia clave te dijera la posición? Si tus claves fueran números enteros pequeños, digamos números de estudiante del 0 al 99, podrías tener un arreglo de 100 celdas y guardar al estudiante k en la celda k. Las notas del MIT lo llaman arreglo de acceso directo. Falla cuando las claves posibles son enormes, como números de teléfono o palabras, porque no puedes permitirte una celda para cada clave posible.

Una función hash lo resuelve comprimiendo cualquier clave en un rango pequeño de posiciones, de 0 a m − 1. Una sencilla para números enteros es h(k) = k mod m, el residuo de dividir entre m. El arreglo de m celdas es la tabla hash, y a sus celdas se les suele llamar cubetas (buckets). Para guardar 47 con m = 7, calcula 47 mod 7 = 5 y ponlo en la cubeta 5. Para encontrar 47 después, calcula lo mismo y mira solo en la cubeta 5.

Colisiones y encadenamiento

Hay un problema. Con 7 cubetas y más de 7 claves posibles, algunas claves tienen que compartir cubeta: 12, 33 y 47 dan todas residuo 5. Esto se llama colisión, y las notas del MIT señalan que no se puede evitar, por el principio del palomar. El remedio habitual es el encadenamiento: cada cubeta contiene una pequeña lista, una cadena, con todas las claves que fueron a parar ahí. Encontrar 47 cuesta entonces 1 paso por el hash más una comparación por cada clave revisada en la cadena 5. Si 12 y 33 están delante, son 1 + 3 = 4 pasos.

¿Qué largo tienen las cadenas? Si las claves se reparten de manera uniforme, cada cadena tiene unas n/m claves, un número llamado factor de carga. Mantén m más o menos tan grande como n y las cadenas siguen cortas, así que buscar, insertar y eliminar llevan en promedio un número constante de pasos. El peligro es un mal reparto. Si todas las claves van a la misma cubeta, una sola cadena contiene las n claves y la tabla no es mejor que una lista enlazada. En el laboratorio, pon 7 cubetas e inserta 14, 21 y 28: todas caen en la cubeta 0.

Tablas hash en JavaScript

Rara vez escribirás tú mismo una tabla hash, porque JavaScript tiene Map y Set. La especificación de ECMAScript dice que "deben implementarse usando tablas hash u otros mecanismos que, en promedio, ofrezcan tiempos de acceso sublineales respecto al número de elementos". Dicho de otro modo, map.get(key) y set.has(x) deben ser más rápidos que buscar en toda la colección. MDN agrega que un Map conserva las claves en el orden de inserción y, a diferencia de un objeto normal, no contiene claves predeterminadas que puedan chocar con las tuyas.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, sin recorrer la lista
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true