Saltearse al contenido

set y tablas hash

Un set es la tabla hash del capítulo anterior sin la columna de valores. Eso lo hace un 11 % más compacto por entrada y, sobre todo, le da una propiedad que ninguna otra estructura tiene: las operaciones de conjuntos se ejecutan en C, no en un bucle de Python.

Un set responde «¿está?» en 30 nanosegundos y no promete ningún orden.

Un set de cuatro elementos en una tabla de ocho huecos
4 ocupados · 4 libres hash 16 B 16 B hash 16 B hash 16 B 16 B 16 B hash 16 B 16 B = 16 B por hueco · 60 % de carga

La tabla se redimensiona cuando llega al 60 % de ocupación. Un set de 4 en 8 huecos está al límite: la quinta inserción duplica la tabla y reubica todo.

Ese 60 % es la razón de que un set de un millón de elementos ocupe más que un millón por 16 bytes por hueco: hay huecos vacíos de sobra para que el sondeo encuentre rápido. El coste es memoria; el beneficio, búsqueda constante.

1 000 elementos
Estructura Memoria Por entrada
dict 36.1 KB 36.9 B
set 32.2 KB 32.8 B
frozenset 32.2 KB 32.8 B

python mediciones/02-11-coste.py

Intersección de dos conjuntos de 100 000
Forma Tiempo
a & b 1.89 ms
[x for x in a if x in b] 2.94 ms

python mediciones/02-05-07-dict-set-orden.py

Sólo 1,6 veces, y conviene entender por qué no es más: la comprensión también usa la búsqueda hash de b por elemento. La ventaja de & es que evita el intérprete por iteración y crea el resultado con el tamaño ya calculado.

Donde la diferencia es enorme es cuando una de las dos partes es una lista: x in lista es O(n) y a & set(lista) convierte el problema en O(n) total en lugar de O(n × m).

a = {1, 2, 3}
b = {3, 4}
a | b # unión
a & b # intersección
a - b # diferencia
a ^ b # diferencia simétrica
a <= b # subconjunto

Un set es mutable y por tanto no es hashable: no puede estar dentro de otro set ni ser clave de un dict. frozenset sí:

grupos = {
frozenset({"ana", "luis"}): "equipo A",
frozenset({"eva", "marco"}): "equipo B",
}

Es la forma canónica de usar una combinación de elementos como clave, sin importar el orden en que lleguen.

  • Con pocos elementos. Por debajo de cien, x in lista es más rápido porque no hay coste de construcción de la tabla.
  • Cuando el orden importa de verdad. Un set para recorrer en orden es un error de diseño; usa una lista o un dict.
  • Cuando necesitas el valor asociado. Eso es un dict, no un set de tuplas.
  • Cuando los elementos no son hashables. Listas de listas, diccionarios, objetos mutables: no entran.

Tienes dos listas de 50 000 correos y necesitas: (a) los que están en ambas, (b) los que sólo están en la primera, (c) los nuevos conservando el orden de llegada. Escribe las tres operaciones y di cuál es el coste de cada una.

Solución
viejos = [f"user{i}@mail.com" for i in range(5)]
nuevos = [f"user{i}@mail.com" for i in range(3, 8)]
print(len(viejos), len(nuevos))
conj_viejos = set(viejos)
conj_nuevos = set(nuevos)
en_ambas = conj_viejos & conj_nuevos # (a)
solo_viejos = conj_viejos - conj_nuevos # (b)
nuevos_ordenados = [e for e in nuevos if e not in conj_viejos] # (c)

Costes: construir los dos conjuntos es O(n + m); la unión (a) es O(n + m) y la diferencia (b) recorre el conjunto izquierdo, O(n); (c) es O(m) con búsqueda constante.

El detalle importante es (c): se recorre nuevos en orden y se consulta el conjunto, en lugar de hacer set(nuevos) - conj_viejos, que perdería el orden. El conjunto se usa como índice, no como resultado.

Si hiciera falta conservar duplicados dentro de nuevos, la comprensión los mantiene; el set no.

  • Ramalho, L. Fluent Python, 2ª ed. Capítulo 3: conjuntos y tablas hash.
  • CPython 3.13: Objects/setobject.c (set_add_entry, factor de carga).
  • Mediciones: mediciones/02-05-07-dict-set-orden.py.
  • 05 · dict por dentro: la misma tabla con valores.
  • 09 · Hashabilidad (Parte I): el contrato que un set exige.
  • 10 · collections completo: Counter y ChainMap sobre estas bases.