Funciones hash y estrategia de colisiones

Qué cubre este capítulo

El capítulo anterior construyó una tabla hash y apenas saludó de lejos a la función hash, que es la que hace el trabajo pesado. Este capítulo la mira de frente, porque una tabla hash nunca es mejor que la función que reparte las llaves entre sus buckets. Un buen hash dispersa las llaves de forma uniforme y las búsquedas se quedan en O(1); uno malo las amontona y la tabla, sin avisar, se degrada a un recorrido lineal. Vamos a construir varias funciones hash reales y una deliberadamente mala, y a medir qué tan parejo reparte cada una un diccionario de palabras — porque "repartir parejo" es toda la especificación.

Un poco de historia

Las funciones hash se han estudiado con tanta seriedad como cualquier otro algoritmo. Donald Knuth le dedicó buena parte del tercer volumen de The Art of Computer Programming (1973), analizando el método multiplicativo — multiplicar la llave por una fracción de la razón áurea y quedarse con la parte fraccionaria — que hasta la fecha lleva su nombre. El hash polinomial de strings de este capítulo es el mismo que String.hashCode de Java usa desde hace décadas. FNV, otro de los que veremos aquí, lo diseñaron Glenn Fowler, Landon Curt Noll y Kiem-Phong Vo en 1991, y se aprecia por ser rápido y tener buena avalancha. Y el hash que Python usa de verdad para strings, SipHash, se publicó en 2012 por Jean-Philippe Aumasson y Daniel J. Bernstein justamente para impedir que un atacante fabricara llaves que colisionaran — una defensa contra el ataque de denegación de servicio del que advertía el capítulo anterior. Setenta años después, la gente sigue diseñando funciones hash, porque el balance entre velocidad, distribución y seguridad nunca termina de resolverse.

La intuición

Una función hash tiene un solo trabajo: tomar una llave y producir un entero bien repartido en su rango, para que al plegarlo en buckets las llaves caigan por todos lados en vez de amontonarse. Eso se logra mezclando: cada parte de la llave tiene que influir en el resultado, y cambios chiquitos en la llave deben revolver por completo la salida.

El modo de falla es hashear solo una parte de la llave. Imagínate un hash que nada más mira la primera letra de una palabra. Es rápido y determinista, pero las palabras en inglés no se reparten parejo entre primeras letras — muchas más empiezan con s o con c que con x o z — así que los buckets de las letras comunes se desbordan mientras otros quedan vacíos. No es un ejemplo forzado; es la forma de todo hash malo de la vida real: ignora información de la llave, y entonces la estructura de los datos se filtra directo hacia buckets desbalanceados.

Complejidad y calidad

Calcular un hash cuesta $O(k)$ para una llave de longitud k — tocas cada byte, que es exactamente la razón por la que mezclar toda la llave sale barato. Ese costo se paga en cada búsqueda, inserción y borrado, así que un hash tiene que ser rápido; por eso las tablas hash usan hashes no criptográficos baratos y no SHA-256.

Pero la métrica que más importa aquí no es la velocidad, sino la distribución. La forma de medirla es hashear un conjunto real de llaves en buckets y ver qué tanto se alejan las cargas de un reparto perfectamente parejo, que es lo que captura el estadístico chi-cuadrada (más bajo es más uniforme). La gráfica hashea un diccionario de 180 palabras en 16 buckets con cada función:

Los cuatro hashes buenos dan barras más o menos planas — cada bucket cerca del ideal de 11 palabras. El hash de la primera letra parece un skyline: su peor bucket guarda 51 de las 180 palabras mientras 11 de los 16 buckets quedan completamente vacíos. Su chi-cuadrada es 509 contra el 15 de FNV-1a — una diferencia de treinta veces en qué tan desbalanceada quedaría la tabla. Una tabla hash construida sobre ese hash de primera letra ya no es una tabla hash; es una lista ligada con pasos extra.

En qué es buena y en qué no

Los hashes que quieres para una tabla — polinomial, FNV, SipHash — son todos rápidos, todos mezclan la llave completa y todos distribuyen llaves del mundo real casi uniformemente. Ese es el punto dulce: baratos para correrlos en cada operación, buenos para que las colisiones sigan siendo raras. Para una tabla hash, agarra el que te da tu lenguaje (hash() en Python) y no te pongas a hacer el tuyo a menos que estés en un lenguaje de más bajo nivel que no traiga uno.

Lo que ninguno de estos es, es seguro. Un hash rápido es fácil de aplicar ingeniería inversa y de falsificar, así que nunca debe usarse donde un adversario podría explotar colisiones predecibles o fingir un digest — ese es el trabajo de un hash criptográfico. Y al revés está igual de mal: un hash criptográfico en una tabla hash es un bug de rendimiento, ciclos desperdiciados en seguridad que no necesitas.

Los datos, o las entradas

Las llaves son un diccionario de 180 palabras reales en inglés — el tipo de datos que un corrector ortográfico o un índice de búsqueda hashea de verdad — elegidas porque sus primeras letras siguen la frecuencia del inglés. Ese sesgo es invisible para un hash que mezcla la palabra completa y catastrófico para uno que solo mira la primera letra, que es precisamente la diferencia que mide el capítulo. La animación usa las primeras 40 de esas palabras para que veas llenarse los buckets en tiempo real.

Constrúyelo, una función a la vez

El hash polinomial multiplica el acumulado por un primo antes de sumar cada carácter, así que la posición de un carácter afecta el resultado — abc y cba salen distintos:

def poly_hash(s, mod=2 ** 32):
    """Polynomial hash: h = h*31 + c for each character. The classic string hash
    (it's Java's String.hashCode). Multiplying by a prime before adding the next
    character mixes position into the result, so 'abc' and 'cba' land apart."""
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % mod
    return h

FNV-1a mezcla con xor y luego multiplicación por cada byte, lo que da una avalancha fuerte — un bit de entrada volteado cambia como la mitad de los bits de salida:

def fnv1a(s, mod=2 ** 32):
    """FNV-1a: for each byte, xor it in then multiply by a large prime. Strong
    avalanche — flipping one input bit flips about half the output bits — and
    fast, which is why it's a popular non-cryptographic hash."""
    h = 2166136261
    for ch in s:
        h = ((h ^ ord(ch)) * 16777619) % mod
    return h

Y aquí está el villano — el hash que solo mira el primer carácter y tira el resto de la llave a la basura:

def bad_hash(s, mod=2 ** 32):
    """A deliberately bad hash: it looks at only the FIRST character and ignores
    the rest of the key. On real data this clusters hard — English words are
    dominated by a handful of starting letters — so most keys pile into a few
    buckets and the rest sit empty. The lesson: a hash must mix the WHOLE key."""
    return (ord(s[0]) if s else 0) % mod

Míralo funcionar

Dos heatmaps, ambos llenando 16 buckets conforme llegan las mismas 40 palabras. La fila de arriba es FNV-1a; la de abajo es el hash de primera letra. Fíjate cómo se separan: FNV-1a se queda en un azul frío y parejo — cada bucket ganando palabras más o menos al mismo ritmo — mientras que el hash de primera letra prende unos cuantos buckets en rojo furioso y deja el resto a oscuras, porque todas las palabras que empiezan con las mismas letras comunes se apilan en las mismas casillas. Mismas palabras, mismo número de buckets; la única diferencia es si el hash miró la llave completa:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero trae los tres hashes de arriba. La pestaña de librería es lo que te da Python: hash(), el SipHash rápido que usa el dict, y el SHA-256 de hashlib para cuando necesitas fuerza criptográfica.

"""Hash functions — the piece the last chapter took for granted.

A hash table is only as good as the function spreading keys across its buckets. A
good hash scatters keys uniformly, so buckets stay balanced and lookups stay O(1);
a bad one clusters them, and the table degrades toward a linear scan. This chapter
builds a few real hash functions and one deliberately bad one, and measures how
evenly each spreads a set of words — because "spreads evenly" is the entire job.
"""


# region: poly_hash
def poly_hash(s, mod=2 ** 32):
    """Polynomial hash: h = h*31 + c for each character. The classic string hash
    (it's Java's String.hashCode). Multiplying by a prime before adding the next
    character mixes position into the result, so 'abc' and 'cba' land apart."""
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % mod
    return h
# endregion


# region: fnv1a
def fnv1a(s, mod=2 ** 32):
    """FNV-1a: for each byte, xor it in then multiply by a large prime. Strong
    avalanche — flipping one input bit flips about half the output bits — and
    fast, which is why it's a popular non-cryptographic hash."""
    h = 2166136261
    for ch in s:
        h = ((h ^ ord(ch)) * 16777619) % mod
    return h
# endregion


# region: bad_hash
def bad_hash(s, mod=2 ** 32):
    """A deliberately bad hash: it looks at only the FIRST character and ignores
    the rest of the key. On real data this clusters hard — English words are
    dominated by a handful of starting letters — so most keys pile into a few
    buckets and the rest sit empty. The lesson: a hash must mix the WHOLE key."""
    return (ord(s[0]) if s else 0) % mod
# endregion


def bucket_of(hash_value, num_buckets):
    """Fold a hash value into a bucket index — the modulo the table applies."""
    return hash_value % num_buckets

"""Python already gives you two kinds of hash, at opposite ends of the trade-off.

`hash()` is the fast, non-cryptographic hash the built-in dict uses. For strings
it's SipHash, seeded with a per-process random key so an attacker can't predict
collisions. `hashlib` gives cryptographic hashes (SHA-256, etc.) — far slower, but
with the best possible distribution and designed so you can't reverse or forge them.

For a hash table you want the first. This chapter's face-off measures how well our
hand-written hashes distribute keys compared to Python's built-in `hash`.
"""
import hashlib


# region: python_hash
def python_hash(s, mod=2 ** 32):
    """Python's built-in hash() — SipHash for strings, randomized per process to
    resist algorithmic-complexity attacks. This is what `dict` uses."""
    return hash(s) % mod
# endregion


# region: sha256_hash
def sha256_hash(s, mod=2 ** 32):
    """A cryptographic hash reduced to an integer. Overkill (and slow) for a hash
    table, but the gold standard for uniform distribution — a useful yardstick."""
    return int(hashlib.sha256(s.encode()).hexdigest(), 16) % mod
# endregion

Desde cero vs librería

Este duelo es de calidad, no de velocidad, así que la comparación es la gráfica de distribución de arriba — y nuestros hashes polinomial y FNV-1a se defienden bien contra el hash integrado de Python: los tres caen casi uniformes (chi-cuadradas de 18, 15 y 10 contra el ideal). Ese es el resultado tranquilizador: un hash escrito a mano con criterio compite de verdad con el de la librería estándar en distribución, porque mezclar bien no es difícil una vez que sabes que hay que mezclar la llave completa. Donde gana la librería es en lo que no se ve en una gráfica de distribución — la semilla aleatoria por proceso de SipHash, que el nuestro no tiene (o sea, el nuestro sería vulnerable a un ataque de colisiones), y una implementación en C más rápida que nuestro loop de Python. Usa hash(); construye estos para entender qué lo hace confiable.

Dónde te lo vas a encontrar de verdad

Dependes de una función hash cada vez que usas un dict, un set o un índice de base de datos — es la capa invisible debajo de todo lo que listó el capítulo anterior. Más allá de las tablas, los hashes están en todos lados: el almacenamiento direccionado por contenido y Git nombran objetos por su hash; los sistemas distribuidos rutean llaves a servidores con consistent hashing; los filtros de Bloom (un capítulo más adelante) usan varios hashes a la vez; los checksums y la deduplicación comparan hashes en lugar de archivos completos. Y los primos criptográficos protegen tus contraseñas, firman tus actualizaciones de software y anclan cada blockchain. La elección del hash — rápido versus seguro, y qué tan bien mezcla — es una decisión escondida dentro de todos ellos.

Puntos clave

Una función hash mapea una llave a un entero, y lo único que la hace buena para una tabla hash es la distribución uniforme: tiene que mezclar la llave completa para que la estructura de tus datos no sobreviva hasta convertirse en buckets desbalanceados. Calcularla es $O(k)$ en la longitud de la llave, y se paga en cada operación, así que tiene que ser rápida — por eso las tablas usan hashes no criptográficos como FNV, polinomial y SipHash, y guardan los criptográficos lentos para seguridad.

Con la función hash entendida, al nivel de hashing le queda una estructura por construir encima. Los sets y multisets son tablas hash que guardan solo llaves (o llaves con contadores), y convierten "¿ya vi esto?" y "¿cuántos hay de cada uno?" en preguntas O(1) — el tema del siguiente capítulo.