Tabla hash (hash map)
Estructura de datos que asocia claves con valores en tiempo O(1) amortizado — el ladrillo detrás de dict/HashMap/object en casi todos los lenguajes.
Una función hash mapea la clave a un índice de cubeta. Las colisiones se resuelven por encadenamiento (una lista enlazada por cubeta — el HashMap de Java por defecto) o por direccionamiento abierto (sondeo lineal o cuadrático — dict de Python, map de Go, HashBrown de Rust). Se redimensiona cuando el factor de carga supera ~0,75.
En el peor caso es O(n) con una función hash mala. Los ataques HashDoS (2011) obligaron a todos los lenguajes a usar hashes con semilla (SipHash). El hashing Robin Hood y el hopscotch son variantes modernas con mejor localidad de caché.