Internals de CPython: la tabla hash compacta del dict

Cuando escribes d["key"] = value, Python no ejecuta magia: ejecuta aritmética de punteros sobre dos arrays contiguos en memoria. Entender eso cambia cómo razonas sobre rendimiento, restricciones de claves y el orden de inserción que tanto sorprendió en Python 3.6.

La representación interna: dos arrays, no uno

Antes de CPython 3.6, un dict era una tabla hash clásica: un único array disperso donde cada slot contenía directamente el hash, la clave y el valor. Si declarabas un dict con 5 elementos, el array interno podía tener 8 slots y 3 de ellos estaban vacíos — la memoria de esos slots vacíos era inevitable para mantener la tasa de colisiones bajo control.

Raymond Hettinger propuso en 2012 (implementado en 3.6) lo que ahora se llama la tabla hash compacta: separar la estructura en dos arrays con responsabilidades distintas.

El indices array es un array de enteros pequeños (1, 2 o 4 bytes dependiendo del tamaño del dict) que actúa como tabla de dispersión pura. La mayoría de sus posiciones contienen -1 (“vacío”). Los no-vacíos son índices enteros apuntando al segundo array.

El entries array es un array denso y ordenado de tripletas (hash, key, value). Cada nueva inserción ocupa la siguiente posición libre al final — de ahí el orden de inserción garantizado, no como efecto secundario sino como consecuencia estructural inevitable.

indices:  [-1, 2, -1, 0, -1, -1, 1, -1]   ← 8 slots, solo 3 usados
entries:  [(h0, "a", 1),                   ← posición 0
           (h1, "b", 2),                   ← posición 1
           (h2, "c", 3)]                   ← posición 2

El ahorro de memoria es real: los slots vacíos del indices array son enteros de 1 byte, no tripletas de objetos Python. Para dicts pequeños la diferencia puede ser 3×.

El rol de __hash__ y __eq__

Cuando Python busca una clave, ejecuta este proceso:

1. Llama a hash(key) → obtiene un entero. Para strings, CPython tiene una implementación en C con randomización por proceso (SipHash-1-3 desde 3.6); para enteros, el hash es el entero módulo un primo.
2. Calcula slot = hash & (len(indices) - 1) — operación de máscara de bits, posible porque el tamaño del indices array siempre es potencia de 2.
3. Lee indices[slot]. Si es -1, la clave no existe. Si es i, lee entries[i].
4. Compara primero los hashes enteros (barato) y luego llama a key.__eq__(entries[i].key) (potencialmente caro).
5. Si hay colisión — dos claves distintas con el mismo slot calculado — CPython usa open addressing con perturbación: slot = (5*slot + 1 + perturb) & mask, donde perturb se va desplazando. Esto garantiza que se visiten todos los slots antes de concluir que no hay espacio.

La perturbación es crucial porque garantiza que claves con los mismos bits bajos no colisionen indefinidamente.

Por qué las listas no pueden ser claves

Una clave válida requiere que su hash sea estable durante toda su vida útil. Si hash(k) cambia después de insertar k en el dict, la búsqueda calculará un slot distinto al de la inserción y nunca encontrará la entrada — corrupción silenciosa.

Las listas son mutables: append, pop, __setitem__ cambian su contenido. CPython podría haber calculado el hash en el momento de inserción e ignorado los cambios posteriores, pero entonces d[["a"]] y d[["a"]] podrían apuntar al mismo slot aunque entre medias hayas modificado la lista — invariante imposible de mantener. La solución es que list directamente no implementa __hash__ (lo establece a None), y Python lanza TypeError antes de intentar nada.

Puedes crear clases mutables hashables implementando __hash__ y __eq__ — pero es tu responsabilidad garantizar que el hash no cambie mientras el objeto sea clave de algún dict. Si lo cambias, el dict queda corrupto en silencio.

Factor de carga y redimensionamiento

CPython mantiene el factor de carga (elementos usados / tamaño del indices array) por debajo de 2/3. Cuando una inserción supera ese umbral, el dict se redimensiona.

El redimensionamiento no es un simple realloc: se construye un nuevo indices array con el doble de slots, y todas las entradas del entries array se reinsertan recalculando sus slots en la nueva máscara. El entries array en sí se copia compacto — sin huecos de entradas borradas.

Las borrados merecen mención aparte. Cuando eliminas una clave, CPython no pone -1 en el slot del indices array (eso rompería las cadenas de perturbación de claves que colisionaron). Pone un valor especial DUMMY que significa “hueco, pero sigue buscando”. Los DUMMYs sí se eliminan en el siguiente redimensionamiento.

Código: observando las entrañas

import sys
import ctypes

# CPython expone la estructura interna vía el módulo privado _testinternalcapi
# en builds de debug, pero podemos observar comportamiento real sin él.

def dict_growth_trace():
    """
    Demuestra cuándo CPython redimensiona el dict midiendo
    sys.getsizeof en cada inserción.
    """
    d = {}
    prev_size = sys.getsizeof(d)
    resize_points = []

    for i in range(40):
        d[i] = i
        current_size = sys.getsizeof(d)
        if current_size != prev_size:
            resize_points.append((i, prev_size, current_size))
            prev_size = current_size

    return resize_points


def hash_collision_demo():
    """
    En Python, hash(n) == n para enteros pequeños.
    Podemos forzar colisiones en el indices array con claves
    cuyo hash comparte los mismos bits bajos dado un tamaño concreto.
    """
    # Con un dict de 8 slots, la máscara es 0b111 (7).
    # Claves 0 y 8 mapean al mismo slot inicial: 0 & 7 == 0, 8 & 7 == 0.
    d = {}
    d[0] = "zero"
    d[8] = "eight"   # colisiona con 0 en el slot inicial; CPython lo resuelve
    d[16] = "sixteen" # también slot 0 inicialmente

    # Las tres claves coexisten porque la perturbación las separa.
    assert d[0] == "zero"
    assert d[8] == "eight"
    assert d[16] == "sixteen"

    return d


class BadKey:
    """
    Clase que viola el contrato de hashabilidad: cambia su hash.
    Ilustra la corrupción silenciosa que Python evita en listas.
    """
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        # El hash depende del estado mutable — contrato roto.
        return hash(self.value)

    def __eq__(self, other):
        return isinstance(other, BadKey) and self.value == other.value


def corrupt_dict_demo():
    k = BadKey(42)
    d = {k: "answer"}

    # El dict encontró k en el slot correcto para hash(42).
    assert d[k] == "answer"

    # Mutamos el objeto: ahora hash(k) devuelve algo distinto.
    k.value = 99

    # La búsqueda calcula el slot para hash(99), no encuentra nada.
    try:
        _ = d[k]
    except KeyError:
        print("Clave perdida: el hash cambió tras la inserción")

    # La entrada sigue en entries[], CPython no la borró,
    # pero ya es inaccesible por hash lookup normal.
    print(f"Entradas en el dict (len): {len(d)}")  # imprime 1 — está pero no se puede alcanzar


if __name__ == "__main__":
    print("Puntos de redimensionamiento (elemento, tamaño_antes, tamaño_después):")
    for point in dict_growth_trace():
        print(f"  inserción #{point[0]:2d}: {point[1]} → {point[2]} bytes")

    print("\nColisiones resueltas correctamente:")
    print(hash_collision_demo())

    print("\nDemo de corrupción por hash mutable:")
    corrupt_dict_demo()

Lo que el código te está mostrando

dict_growth_trace hace visible algo que normalmente es invisible: el dict no crece linealmente. Verás saltos en los bytes reportados exactamente cuando el factor de carga supera 2/3. Los tamaños siguen potencias de 2 en el indices array (8 → 16 → 32 → …), pero sys.getsizeof reporta el tamaño total del objeto PyDictObject incluyendo ambos arrays y el overhead del struct.

hash_collision_demo es importante porque desmitifica las colisiones: no son errores ni excepciones, son el camino normal. CPython las resuelve silenciosamente con la perturbación. El rendimiento degrada con muchas colisiones, pero con un __hash__ razonablemente distribuido el caso promedio es O(1).

corrupt_dict_demo con BadKey reproduce exactamente el motivo por el que list.__hash__ = None. La entrada no desaparece del entries array — sigue ocupando memoria, el len() la cuenta — pero es unreachable mediante lookups. En producción esto sería un memory leak semántico silencioso.

La separación entries/indices también explica por qué iterar un dict mientras lo modificas lanza RuntimeError: CPython mantiene un contador de versión (ma_version_tag) que la capa de iteración verifica en cada __next__. Si detecta que el entries array fue modificado (cualquier inserción o borrado cambia el tag), aborta inmediatamente en lugar de darte resultados indefinidos.

Errores que debes conocer

Error: usar un objeto como clave dict e implementar __hash__ sin implementar __eq__, o viceversa.

# ❌ Wrong
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    # __hash__ heredado de object usa id() — dos Point "iguales"
    # son claves distintas en el dict

p1 = Point(1, 2)
p2 = Point(1, 2)
d = {p1: "a", p2: "b"}
print(len(d))  # 2 — p1 y p2 son claves distintas aunque p1 == p2

# ✅ Right
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))  # hash consistente con __eq__

p1 = Point(1, 2)
p2 = Point(1, 2)
d = {p1: "a", p2: "b"}
print(len(d))  # 1 — correctamente unificados

Cuando defines __eq__, Python pone __hash__ a None automáticamente para forzarte a ser explícito: el data model exige que a == b implique hash(a) == hash(b).

Error: asumir que el redimensionamiento es barato porque ocurre pocas veces.

# ❌ Wrong — construir un dict grande con inserciones individuales en un loop crítico
def build_index(records):
    index = {}
    for r in records:
        index[r.id] = r  # redimensiona varias veces durante el proceso
    return index

# ✅ Right — pre-poblar desde un iterable evita redimensionamientos intermedios
# dict() con un generador calcula el tamaño óptimo inicial si puede
def build_index(records):
    return {r.id: r for r in records}
    # alternativa si necesitas control explícito: dict.fromkeys() para claves conocidas

El dict comprehension no es solo azúcar sintáctico: CPython puede optimizar la construcción inicial mejor que inserciones sucesivas, y el entries array se construye compacto desde el principio sin DUMMYs acumulados de redimensionamientos previos.

N° 44