Buscar una clave en un dict de Python con diez entradas tarda lo mismo que buscarla en uno con diez millones. No es casualidad de un lenguaje rápido. El dict de Python, el HashMap de Java y el Map de JavaScript son tablas hash, y todo su diseño existe para que búsqueda, inserción y borrado funcionen en O(1) de media. La notación Big O llama a esa búsqueda “tiempo constante”. Este es el mecanismo que se lo gana.

Cómo una tabla hash convierte una clave en un índice de array

Una tabla hash es un array más una función que convierte una clave en una posición de ese array.

1

índice del bucket = hash(clave) % número_de_buckets

hash() toma una clave de cualquier tamaño (una cadena, una tupla, un objeto) y devuelve un entero. Dentro de una misma ejecución del programa, la misma clave siempre produce el mismo entero, y una buena función hash reparte esos enteros de forma casi uniforme por todo su rango de salida. Tomas el entero módulo la longitud del array y obtienes un slot. Ahí guardas la clave y el valor. Una búsqueda posterior recalcula el mismo hash, llega al mismo slot y lee el valor. Sin recorrer nada, sin comparar con el resto de claves.

Todo lo demás en una tabla hash real —desde el manejo de colisiones hasta el resize y la secuencia exacta de sondeo— existe para que esa búsqueda de un solo paso siga funcionando mientras la tabla se llena.

Una versión mínima que ignora las colisiones:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TinyTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [None] * size

    def put(self, key, value):
        index = hash(key) % self.size
        self.buckets[index] = (key, value)

    def get(self, key):
        index = hash(key) % self.size
        if self.buckets[index] is None:
            raise KeyError(key)
        stored_key, value = self.buckets[index]
        if stored_key != key:
            raise KeyError(key)
        return value

1
2
3
4

>>> t = TinyTable()
>>> t.put("user:42", {"name": "Dana"})
>>> t.get("user:42")
{'name': 'Dana'}

Se rompe en cuanto dos claves distintas producen el mismo índice. hash("user:42") % 8 y hash("user:17") % 8 pueden dar ambos 3, y TinyTable solo tiene sitio para una: el segundo put sobrescribe al primero sin avisar. Eso es una colisión.

Cómo gestionan las colisiones las tablas hash: chaining vs. open addressing

Hay dos formas estándar de conservar ambas claves cuando caen en el mismo slot.

El chaining convierte cada bucket en un pequeño contenedor, normalmente una lista enlazada. Una colisión significa que el bucket guarda dos entradas en vez de una, y la búsqueda recorre esa lista hasta encontrar la clave que coincide.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ChainedTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[hash(key) % self.size]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

El HashMap de Java es una tabla con chaining. Cada bucket empieza como lista enlazada. Si un bucket acumula al menos 8 entradas y la tabla tiene al menos 64 buckets, ese bucket se convierte en un árbol rojo-negro (TREEIFY_THRESHOLD y MIN_TREEIFY_CAPACITY en el código del JDK), así que un recorrido O(n) en el peor caso de un bucket sobrecargado pasa a ser O(log n). Vuelve a ser lista si un resize lo deja con 6 entradas o menos.

El open addressing mantiene cada entrada directamente en el array, sin estructura secundaria ni punteros. Ante una colisión, sondea: prueba otro slot, según una regla fija, hasta encontrar uno vacío. El dict de CPython funciona así, y el comentario sobre la búsqueda en Objects/dictobject.c da el motivo: “Open addressing is preferred over chaining since the link overhead for chaining would be substantial.” CPython también evita el sondeo lineal puro, que se apelmaza cuando las claves llegan en un orden predecible. Cada paso de sondeo mezcla más bits del hash en el siguiente índice, así que dos claves que colisionan en sus bits bajos se separan unos sondeos después.

Las dos estrategias fallan de forma distinta. Una tabla con chaining que se llena se vuelve más lenta, y en el peor caso toda entrada termina en una sola lista larga. Una tabla con open addressing no tiene dónde meter una entrada cuando el array está lleno, así que tiene que hacer resize antes de llegar a eso.

Qué es el load factor y por qué la tabla hace resize antes de llenarse

El load factor es el número de entradas dividido entre el número de buckets. Ambas estrategias lo vigilan para decidir cuándo hacer resize, y Java y CPython eligen umbrales distintos.

El HashMap de Java hace resize cuando el número de entradas supera la capacidad multiplicada por el load factor. El Javadoc del constructor sin argumentos da los valores por defecto: 16 buckets, load factor 0,75, así que el primer resize se dispara en la entrada número 12. Un resize duplica aproximadamente el número de buckets y rehace el hash de todas las entradas existentes en el array nuevo. Por eso el Javadoc recomienda dimensionar el mapa de antemano con HashMap.newHashMap(expectedSize) (Java 19+) cuando sabes aproximadamente cuántas entradas tendrá: te ahorras los rehashes repetidos.

El dict de CPython hace resize más tarde y crece más rápido. El comentario USABLE_FRACTION del código dice que la tabla hace resize cuando está dos tercios llena, y GROWTH_RATE dimensiona la tabla nueva para unas tres veces el número actual de entradas vivas, no un simple duplicado.

Ninguno de los dos números es arbitrario. Un load factor cercano a 1 aprovecha el array al máximo pero vuelve más lenta cada operación a medida que los buckets se llenan; uno cercano a 0 desperdicia memoria en slots que nadie usa todavía. Ambos diseños se asientan entre 0,66 y 0,75, el punto donde la memoria extra deja de comprar sondeos mucho más cortos.

Por qué la búsqueda en una tabla hash es O(1) de media, no siempre

El tiempo constante se mantiene solo mientras los hashes reparten las claves de forma casi uniforme entre los buckets. Dos cosas lo rompen.

Una función hash mala o predecible. Si todas las claves que insertas van al mismo bucket, una tabla con chaining degenera en una única lista enlazada con búsqueda O(n), justo lo que la estructura existe para evitar. Esto pasa en producción. Un servidor que hace hash de entrada controlada por un atacante (nombres de campos de un formulario, cabeceras HTTP, claves JSON) con una función predecible queda expuesto a ataques de complejidad algorítmica: el atacante envía miles de claves construidas para colisionar y fuerza el peor comportamiento en cada petición. Python aleatoriza el hash de str y bytes por proceso desde la versión 3.3 (controlado por PYTHONHASHSEED) precisamente por esto. La misma cadena produce hashes distintos en dos ejecuciones del intérprete, así que nadie puede precalcular un conjunto de colisiones fuera de línea.

Modificar una clave después de insertarla. El bucket donde vive una clave se eligió según su hash, así que la tabla asume que ese hash nunca cambia. Python lo impone a nivel de tipo: los tipos mutables como list y dict ponen __hash__ en None, y usar uno como clave lanza TypeError: unhashable type: 'list' antes de que el error pueda ocurrir. Las tuplas y las cadenas son hashables porque son inmutables. Para una clase de clave personalizada, implementa __hash__ y __eq__ juntos y básalos solo en campos que nunca cambien. Si no, una clave editada “desaparece”: la entrada sigue en la tabla, en el bucket que señalaba su hash antiguo, pero la búsqueda mira en otro sitio.

Cuándo no usar una tabla hash

Una tabla hash responde rápido a una sola pregunta: ¿existe esta clave y cuál es su valor? Casi todo lo demás lo hace mal.

  • Consultas de rango y orden. “Todos los usuarios creados este mes” o “la siguiente clave después de esta” necesitan una estructura ordenada. Una tabla hash no tiene orden. El dict de CPython garantiza el orden de inserción desde la 3.7, pero eso es orden de iteración, no orden de clasificación, y no ayuda con “todo entre X e Y”. Esa consulta es el trabajo de un B-tree, por lo que la mayoría de bases de datos usan índices B-tree por defecto en vez de índices hash. Cómo funcionan los índices de base de datos trata la disyuntiva entre scan y seek que hay detrás de esa elección.
  • Coincidencia por prefijo o difusa. “Claves que empiezan por user:” significa revisar cada clave una por una. Un trie, o una estructura ordenada con búsqueda binaria, lo resuelve directamente.
  • Claves enteras pequeñas en un rango acotado. Si la clave ya es un día de la semana o una clase de código de estado HTTP, salta la función hash e indexa el array directamente. Una capa menos, ninguna colisión.

Cuando una tabla hash es la estructura correcta, casi nunca escribes una desde cero. dict, HashMap, Map y std::unordered_map ya están optimizadas y son correctas. También las usas indirectamente más de lo que crees: una función decorada con functools.lru_cache, que se trata en Decoradores de Python explicados, construye una clave a partir de los argumentos de la llamada y la busca en un dict.

Así que la decisión es corta. Si la operación es “busca esto por clave exacta”, usa la tabla hash integrada y no escribas la tuya. Si la pregunta implica orden, rangos o coincidencias parciales, elige desde el principio una estructura ordenada o un trie, porque ninguna función hash arregla una estructura que responde a la pregunta equivocada.

Artículos relacionados