Tablas hash: encadenamiento y direccionamiento abierto

Qué cubre este capítulo

Un array te da acceso O(1) — pero solo por índice entero. La tabla hash extiende ese superpoder a cualquier llave: un string, una tupla, cualquier cosa hasheable. Pasa la llave por una función hash para obtener un entero, redúcelo a un bucket, y puedes encontrarla de nuevo en tiempo constante en promedio. Todo el juego está en manejar las colisiones, cuando dos llaves quieren el mismo bucket, y este capítulo construye las dos respuestas clásicas lado a lado — encadenamiento separado y direccionamiento abierto — y luego pone a ambas a competir contra el dict que reimplementan.

Un poco de historia

El hashing se inventó en IBM a principios de los años cincuenta. Hans Peter Luhn describió la idea de hashear llaves hacia buckets con encadenamiento en un memo interno en 1953 — el mismo Luhn que inventó el checksum de tu tarjeta de crédito. El direccionamiento abierto llegó casi de inmediato: un equipo que incluía a Gene Amdahl lo desarrolló en 1954 mientras construía el ensamblador de la IBM 701, porque la máquina no tenía memoria de sobra para cadenas y necesitaban que todo viviera en una sola tabla. Así que las dos técnicas de este capítulo tienen setenta años y nacieron con un año de diferencia, del mismo problema — encontrar un valor por su llave sin escanear — y de la misma restricción: memoria escasa. Todo diccionario, índice de base de datos y cache desde entonces desciende de ese trabajo.

La intuición

Imagina que quieres guardar un valor bajo la llave "banana". No puedes indexar un array con un string. Entonces fabricas un índice: le pasas "banana" a una función hash, que lo revuelve en algún entero, y tomas ese entero módulo el número de buckets. Ya tienes un slot. Guardas el par ahí; para buscarlo después, hasheas la llave otra vez y vas directo al mismo slot. Sin escanear — calculas la ubicación.

El problema es que llaves distintas pueden caer en el mismo bucket. No es un accidente raro; con menos buckets que llaves posibles, está garantizado. Hay dos formas de lidiar con eso. El encadenamiento separado mantiene una pequeña lista en cada bucket y ahí agrega las que colisionan — al buscar una llave, solo recorres esa lista corta. El direccionamiento abierto guarda todo en la tabla misma: si tu slot está ocupado, avanzas al siguiente libre, y para encontrar la llave después repites el mismo recorrido. El encadenamiento es más simple y tolerante; el direccionamiento abierto es más rápido y más amigable con el cache, pero más exigente en cuanto a mantenerse suficientemente vacío.

Complejidad: cómo escala

Sea $\alpha = n / m$ el factor de carga — n elementos en m buckets. Con una buena función hash que reparta las llaves de manera uniforme, el encadenamiento separado da una longitud de cadena esperada de exactamente $\alpha$, así que una búsqueda promedio hace $O(1 + \alpha)$ de trabajo. Mantén $\alpha$ por debajo de una constante (nosotros redimensionamos en 0.75) y eso es $O(1)$. El direccionamiento abierto con probing lineal es un poco peor conforme la tabla se llena — el número esperado de probes para una búsqueda exitosa es de aproximadamente

y por eso necesita un factor de carga más bajo (nosotros redimensionamos en 0.5): en $\alpha = 0.9$ son más de cinco probes por búsqueda, y explota cuando $\alpha \to 1$. El peor caso de cualquiera de los dos es $O(n)$ — todas las llaves colisionando en un solo bucket — pero con un hash decente y un factor de carga acotado eso prácticamente nunca ocurre. La gráfica empírica de abajo mete llaves y las lee todas de vuelta:

Las tres líneas son rectas — trabajo total lineal, o sea O(1) por operación — que es justo el punto: mete diez veces más llaves, espera diez veces más tiempo, nunca más que eso.

Para qué sirve, para qué no

La tabla hash es el caballo de batalla de la programación práctica. Cuando tu patrón de acceso es "encuentra el valor de esta llave", nada le gana al O(1) promedio, y las llaves pueden ser cualquier cosa hasheable. Así se construye un cache, un índice, un set, un conteo de frecuencias, un deduplicador — la mayoría de los próximos capítulos y la mitad del código del mundo real se apoyan en ella.

Lo que sacrifica es el orden. Una tabla hash dispersa las llaves según su hash, así que no tiene noción de menor, mayor, siguiente ni rango — iterarla produce las llaves en un orden revuelto (o de inserción), nunca ordenado. Si necesitas "todas las llaves entre X y Y" o "la llave más pequeña", lo que quieres es un árbol, no una tabla hash. Y el O(1) es un promedio: descansa sobre una buena función hash y un factor de carga acotado.

Los datos, o las entradas

El enfrentamiento inserta un conjunto grande de llaves enteras distintas y luego las busca todas de vuelta — la carga pura de put y luego get donde se ve el comportamiento O(1) por operación. La animación usa una tabla diminuta de ocho buckets y seis llaves elegidas a mano, de las cuales tres (3, 11 y 19) hashean deliberadamente al mismo bucket, para que veas formarse una cadena de colisiones.

Constrúyela, una función a la vez

Todo empieza por convertir una llave en un índice de bucket — hash, luego módulo:

def _index(self, key):
    """Map a key to a bucket: hash it to an integer, fold into [0, capacity)
    with a modulo. A good hash spreads keys evenly so buckets stay balanced."""
    return hash(key) % self._cap

Put va al bucket de la llave, actualiza en su lugar si la llave ya está, y si no, la agrega — y hace crecer la tabla cuando el factor de carga cruza 0.75 para que las cadenas se mantengan cortas:

def put(self, key, value):
    """O(1) average: go straight to the key's bucket, update in place if the
    key is already there, else append. Grow when the load factor (items per
    bucket) crosses 0.75 so the chains never get long."""
    bucket = self._buckets[self._index(key)]
    for i, (k, _) in enumerate(bucket):
        if k == key:
            bucket[i] = (key, value)
            return
    bucket.append((key, value))
    self._n += 1
    if self._n > 0.75 * self._cap:
        self._resize(self._cap * 2)

Get es la recompensa: hashea hacia el bucket y escanea solo ese bucket, que contiene O(1) elementos mientras el factor de carga esté acotado:

def get(self, key, default=None):
    """O(1) average: hash to the bucket and scan only that bucket. While the
    load factor is bounded the bucket holds O(1) items, so this is constant."""
    for k, v in self._buckets[self._index(key)]:
        if k == key:
            return v
    return default

Resize es la parte que mantiene put en O(1) amortizado — más buckets, rehashear todo, y es raro porque duplicamos, así que se amortiza exactamente igual que en el array dinámico:

def _resize(self, new_cap):
    """O(n): allocate more buckets and rehash every entry into them. Doubling
    makes this rare, so it amortizes away — the same argument as the dynamic
    array, and the reason average put stays O(1)."""
    old = self._buckets
    self._cap = new_cap
    self._buckets = [[] for _ in range(new_cap)]
    self._n = 0
    for bucket in old:
        for k, v in bucket:
            self.put(k, v)

El direccionamiento abierto reemplaza las cadenas con probing. En lugar de una lista por bucket, un solo array plano; en una colisión, avanzas hasta el siguiente slot libre:

def _slot(self, key):
    """Linear probing: start at hash(key); if that slot holds a different key,
    step to the next one, wrapping around, until we find the key or an empty
    slot. Every collision just walks forward in the same array."""
    i = hash(key) % self._cap
    while self._keys[i] is not self._EMPTY and self._keys[i] != key:
        i = (i + 1) % self._cap
    return i

Míralo funcionar

Aquí está el encadenamiento separado llenando una tabla de ocho buckets. Cada fila es un bucket; cada frame hashea una llave y la deposita. Fíjate en el bucket 3: las llaves 3, 11 y 19 hashean todas hacia él (las tres son 3 mod 8), así que se apilan en una cadena de tres mientras los demás buckets guardan una cada uno. Una búsqueda de 19 hashearía al bucket 3 y recorrería esa cadena corta — tres comparaciones, no un escaneo de toda la tabla. Eso es una colisión, resuelta:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña from-scratch tiene ambas tablas: encadenamiento separado y direccionamiento abierto. La pestaña de librería es dict, que es en sí mismo una tabla hash de direccionamiento abierto fuertemente optimizada y escrita en C — la estructura exacta que estás construyendo, y la que realmente vas a usar.

"""A hash table — the structure that makes lookup by key O(1) on average.

Arrays give O(1) access by integer index. A hash table extends that to any key:
run the key through a hash function to get an integer, fold it into a bucket
index, and store it there. The catch is collisions — two keys landing in the same
bucket — and the two classic ways to handle them are the two implementations here:
separate chaining (a list per bucket) and open addressing (probe for the next
free slot). Both keep lookups O(1) as long as the table isn't too full.
"""


class HashTable:
    """Separate chaining: each bucket holds a small list of (key, value) pairs.
    Collisions extend the list; a bounded load factor keeps every list short."""

    def __init__(self, capacity=8):
        self._cap = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._n = 0

    # region: hash
    def _index(self, key):
        """Map a key to a bucket: hash it to an integer, fold into [0, capacity)
        with a modulo. A good hash spreads keys evenly so buckets stay balanced."""
        return hash(key) % self._cap
    # endregion

    # region: put
    def put(self, key, value):
        """O(1) average: go straight to the key's bucket, update in place if the
        key is already there, else append. Grow when the load factor (items per
        bucket) crosses 0.75 so the chains never get long."""
        bucket = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self._n += 1
        if self._n > 0.75 * self._cap:
            self._resize(self._cap * 2)
    # endregion

    # region: get
    def get(self, key, default=None):
        """O(1) average: hash to the bucket and scan only that bucket. While the
        load factor is bounded the bucket holds O(1) items, so this is constant."""
        for k, v in self._buckets[self._index(key)]:
            if k == key:
                return v
        return default
    # endregion

    # region: delete
    def delete(self, key):
        """O(1) average: find the key in its bucket and drop it."""
        bucket = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._n -= 1
                return True
        return False
    # endregion

    # region: resize
    def _resize(self, new_cap):
        """O(n): allocate more buckets and rehash every entry into them. Doubling
        makes this rare, so it amortizes away — the same argument as the dynamic
        array, and the reason average put stays O(1)."""
        old = self._buckets
        self._cap = new_cap
        self._buckets = [[] for _ in range(new_cap)]
        self._n = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)
    # endregion

    def __len__(self):
        return self._n

    def load_factor(self):
        return self._n / self._cap

    def buckets_snapshot(self):
        return [list(b) for b in self._buckets]


class OpenAddressingHashTable:
    """Open addressing: no chains — every entry lives in the table itself. On a
    collision, probe linearly to the next slot. Better cache behaviour (one array,
    no pointer-chasing) but it demands a lower load factor to stay fast."""

    _EMPTY = object()

    def __init__(self, capacity=8):
        self._cap = capacity
        self._keys = [self._EMPTY] * capacity
        self._vals = [None] * capacity
        self._n = 0

    # region: probe
    def _slot(self, key):
        """Linear probing: start at hash(key); if that slot holds a different key,
        step to the next one, wrapping around, until we find the key or an empty
        slot. Every collision just walks forward in the same array."""
        i = hash(key) % self._cap
        while self._keys[i] is not self._EMPTY and self._keys[i] != key:
            i = (i + 1) % self._cap
        return i
    # endregion

    def put(self, key, value):
        if self._n > 0.5 * self._cap:      # keep it half-empty: probing degrades fast
            self._resize(self._cap * 2)
        i = self._slot(key)
        if self._keys[i] is self._EMPTY:
            self._n += 1
        self._keys[i] = key
        self._vals[i] = value

    def get(self, key, default=None):
        i = self._slot(key)
        return self._vals[i] if self._keys[i] == key else default

    def _resize(self, new_cap):
        items = [(k, v) for k, v in zip(self._keys, self._vals) if k is not self._EMPTY]
        self._cap = new_cap
        self._keys = [self._EMPTY] * new_cap
        self._vals = [None] * new_cap
        self._n = 0
        for k, v in items:
            self.put(k, v)

    def __len__(self):
        return self._n

"""Python's `dict` is a hash table — one of the most heavily optimized in any
language. It uses open addressing (a variant called perturbation probing) with a
compact, insertion-ordered layout, all in C. Every time you write `d[key] = value`
you're using exactly the structure this chapter builds.

So the face-off is our hash table against the `dict` it reimplements, on the same
put-then-get workload.
"""


# region: dict_build
def build_dict(pairs):
    """Insert (key, value) pairs into a dict — the O(1)-average put."""
    d = {}
    for k, v in pairs:
        d[k] = v
    return d
# endregion


# region: dict_get
def get_all_dict(d, keys):
    """Look up every key — the O(1)-average get."""
    total = 0
    for k in keys:
        v = d.get(k)
        if v is not None:
            total += v
    return total
# endregion

Desde cero vs librería

Las tres son O(1) por operación, así que esta es una historia sobre la constante — y la constante es grande, porque una tabla hash hace trabajo real por operación (hashear, indexar, comparar) y la nuestra lo hace en Python. Meter y leer 160000 llaves le tomó a nuestra tabla con encadenamiento unos 278 ms, a nuestra tabla de direccionamiento abierto unos 165 ms, y al dict unos 18 ms. Vale la pena leer dos cosas ahí. Primero, el direccionamiento abierto le gana al encadenamiento incluso en Python puro — un solo array plano sin objetos lista por bucket significa mucha menos asignación de memoria y un comportamiento de cache mucho más amigable, que es exactamente por lo que las tablas hash reales (incluido dict) usan direccionamiento abierto. Segundo, el dict está otro orden de magnitud más allá de ambas, porque es C haciendo lo que nosotros hacemos en bytecode interpretado. Nunca enviarías a producción ninguna de las nuestras; las construyes para saber lo que cuesta d[key] y por qué normalmente es gratis.

Dónde te la vas a encontrar de verdad

Te encuentras una tabla hash cada vez que escribes {} o set(). Es el dict que guarda los atributos de tus objetos, el índice que hace rápido un WHERE key = ? en la base de datos, el cache frente a una API lenta, el set seen que deduplica un stream, el contador que cuenta frecuencias de palabras. Es la tabla de símbolos de todo compilador y la tabla de ruteo de todo router. Cuando un problema se reduce a "¿ya vi esto antes?" o "¿cuál es el valor de esta llave?", la respuesta es casi siempre una tabla hash, y la razón de que sea la respuesta correcta es el O(1) que este capítulo se gana.

Conclusiones

Una tabla hash mapea llaves a buckets con una función hash, dando get, put y delete en $O(1)$ promedio — siempre que mantengas acotado el factor de carga, que es para lo que sirve el resize. Las colisiones son inevitables y se manejan de dos formas: encadenamiento (una lista por bucket, tolerante y simple) o direccionamiento abierto (probing en un solo array, más rápido y amigable con el cache, la elección de las implementaciones reales). El costo que pagas es el orden: una tabla hash no tiene ninguno.

Ese último punto prepara el resto del nivel y lo que sigue. El próximo capítulo mira con más detalle la función hash en sí — lo que este capítulo dio por sentado — porque una tabla es tan buena como el hash que reparte las llaves sobre ella. Y cuando sí necesites orden junto con búsqueda rápida, los capítulos de árboles más adelante te lo devuelven, al precio de O(log n) en lugar de O(1).