Data Structure & Algorithms
Funcionamiento de hash functions y hash tables: colisiones, chaining, open addressing, load factor, rehashing y costos promedio o amortizados.
Una hash table transforma una clave en una posición aproximada mediante una hash function. Su objetivo es localizar datos sin recorrer toda la colección.
key ─hash→ integer ─indexing→ bucketVarias claves pueden producir el mismo bucket. Eso se llama collision y no es un error excepcional: toda implementación debe resolverlo.
Una hash function determinista debe producir el mismo hash para la misma clave durante la vida de la tabla.
Una buena función para una tabla busca:
No debe confundirse con hashing criptográfico. Una tabla necesita distribución y velocidad; contraseñas necesitan resistencia a ataques y funciones deliberadamente costosas.
Si la tabla tiene capacity buckets:
index = normalize(hash) mod capacityEl hash puede ser negativo en algunos lenguajes, así que debe normalizarse.
Cambiar capacity cambia los índices, por eso rehashing debe redistribuir entradas.
function hashString(key: string): number {
let hash = 2166136261;
for (let index = 0; index < key.length; index += 1) {
hash ^= key.charCodeAt(index);
hash = Math.imul(hash, 16777619);
}
return hash >>> 0;
}Es una variante educativa inspirada en FNV-1a sobre unidades UTF-16. No es criptográfica y no pretende reemplazar el hashing interno del runtime.
charCodeAt procesa code units. Strings con representaciones Unicode distintas producen hashes distintos salvo que normalices antes.
Por el principio del palomar, un dominio de claves grande mapeado a una cantidad finita de buckets tendrá colisiones.
"cat" ─┐
├→ bucket 4
"act" ─┘La pregunta no es cómo evitarlas por completo, sino cómo mantener su costo controlado.
Cada bucket contiene una colección de entradas.
0 → []
1 → [(A, 10), (B, 20)]
2 → [(C, 30)]type Entry<K, V> = {
key: K;
value: V;
};
class ChainedHashMap<V> {
private buckets: Array<Array<Entry<string, V>>>;
private count = 0;
constructor(capacity = 8) {
if (capacity <= 0) throw new RangeError("capacity must be positive");
this.buckets = Array.from({ length: capacity }, () => []);
}
get size(): number {
return this.count;
}
set(key: string, value: V): void {
const bucket = this.bucketFor(key);
const existing = bucket.find((entry) => entry.key === key);
if (existing) {
existing.value = value;
return;
}
bucket.push({ key, value });
this.count += 1;
if (this.loadFactor() > 0.75) {
this.resize(this.buckets.length * 2);
}
}
get(key: string): V | undefined {
const entry = this.bucketFor(key).find((candidate) => candidate.key === key);
return entry?.value;
}
has(key: string): boolean {
return this.bucketFor(key).some((entry) => entry.key === key);
}
delete(key: string): boolean {
const bucket = this.bucketFor(key);
const index = bucket.findIndex((entry) => entry.key === key);
if (index === -1) return false;
bucket.splice(index, 1);
this.count -= 1;
return true;
}
private bucketFor(key: string): Array<Entry<string, V>> {
const index = hashString(key) % this.buckets.length;
return this.buckets[index];
}
private loadFactor(): number {
return this.count / this.buckets.length;
}
private resize(capacity: number): void {
const entries = this.buckets.flat();
this.buckets = Array.from({ length: capacity }, () => []);
this.count = 0;
for (const entry of entries) {
this.set(entry.key, entry.value);
}
}
}Esta implementación enseña estructura, no producción. find, splice, flat y el rehash recursivo mediante set tienen costos y decisiones que una biblioteca madura optimiza.
Sea:
n: entradas;m: buckets;α = n/m: load factor.Con distribución uniforme, el tamaño esperado de una cadena es α:
O(1 + α);O(1) amortizado;O(n) si todas las claves colisionan.Mantener α acotado mediante resize conserva el promedio cercano a constante.
Todas las entradas viven directamente en el array. Ante una colisión, se prueban otras posiciones.
index, index + 1, index + 2, ...Ventajas:
Problema: primary clustering, bloques largos de posiciones ocupadas.
Prueba desplazamientos cuadráticos. Reduce clustering primario, pero necesita una política compatible con la capacidad para garantizar que encuentre posiciones.
Usa una segunda hash function como tamaño de salto. Puede distribuir mejor, pero exige que el salto recorra la tabla de manera adecuada.
No puedes convertir una posición eliminada directamente en “vacía”. Una búsqueda que depende de la cadena de probes podría terminar antes de llegar a una clave posterior.
Usa un marcador tombstone:
EMPTY → nunca se ocupó; búsqueda puede terminar
DELETED → se ocupó; búsqueda debe continuar
OCCUPIED → contiene entradaDemasiados tombstones degradan rendimiento y pueden justificar rehashing.
α = entries / bucketsEn chaining puede superar 1. En open addressing debe ser menor que 1 y el rendimiento empeora al acercarse a la capacidad.
El umbral exacto es una decisión de implementación. Un valor como 0.75 equilibra memoria y longitud esperada de búsquedas, pero no es una ley universal.
Cuando crece la tabla:
Copiar entradas sin recalcular índices es incorrecto porque el módulo cambió.
Una operación de resize cuesta O(n), pero ocurre ocasionalmente. Distribuido sobre muchas inserciones, set puede ser O(1) amortizado.
Si la capacidad se duplica:
1 + 2 + 4 + 8 + ... + n < 2nEl trabajo total de rehashing durante n inserciones es O(n). Sumado a inserciones normales, el promedio amortizado es constante.
Una inserción individual todavía puede costar O(n) cuando dispara resize.
Regla:
Si dos claves se consideran iguales, deben producir el mismo hash.
Lo contrario no es necesario: claves distintas pueden colisionar.
Si la igualdad depende de id, el hash también debe derivarse de id. Mutar campos usados por hash mientras una clave está almacenada puede volverla inencontrable en lenguajes con custom keys.
Un atacante puede enviar claves diseñadas para colisionar y degradar operaciones a O(n). Runtimes y frameworks pueden usar semillas aleatorias, funciones resistentes o estructuras alternativas en buckets.
Esto importa en endpoints públicos, headers, parámetros y parsers, no solo en entrevistas.
Que Map de JavaScript preserve orden de inserción no significa que una hash table genérica esté ordenada por clave. El orden observable es una garantía específica de la API, no una propiedad natural del hashing.
| Necesidad | Hash table | BST balanceado |
|---|---|---|
| Lookup por clave | O(1) promedio | O(log n) garantizado |
| Orden de claves | No natural | Sí |
| Consultas de rango | Ineficientes | O(log n + k) |
| Mínimo/máximo | O(n) | O(log n) |
| Peor caso adversarial | Puede ser O(n) | O(log n) si balanceado |
Si las claves son enteros densos y pequeños, un array puede ser mejor:
const counts = Array(maxValue + 1).fill(0);Lookup verdadero por índice O(1), menor overhead y buena localidad. La hash table aporta flexibilidad para dominios dispersos o tipos de clave más generales.
size;undefined almacenado;O(1) garantizado.get(key) !== undefined para has cuando undefined es valor válido.O(1) no significa peor caso O(1).¿Por qué duplicar la capacidad obliga a recalcular la posición de todas las entradas?
Porque el índice suele depender de hash mod capacity. Al cambiar la capacidad, el mismo hash puede corresponder a otro bucket. Copiar la entrada en el índice antiguo rompería futuras búsquedas.