¿Cómo se implementa set ()?

Cuando la gente dice que los conjuntos tienen verificación de membresía O(1), están hablando del caso promedio. En el caso worst (cuando todos los valores hash chocan) la comprobación de pertenencia es O(n). Ver la wiki de Python sobre la complejidad del tiempo.

El artículo de Wikipedia dice que la mejor caso complejidad de tiempo para una tabla hash que no cambia de tamaño es O(1 + k/n). Este resultado no se aplica directamente a los conjuntos de Python, ya que los conjuntos de Python utilizan una tabla hash que cambia de tamaño.

Un poco más adelante en el artículo de Wikipedia dice que para el caso promedio, y asumiendo una función hash uniforme simple, la complejidad temporal es O(1/(1-k/n)), donde k/n puede estar limitada por una constante c<1.

Big-O se refiere solo al comportamiento asintótico como n → ∞. Puesto que k / n puede estar limitado por una constante, cindependiente de n ,

O(1/(1-k/n)) no es mayor que O(1/(1-c)) que es equivalente a O(constant) = O(1).

Así que asumiendo simple hash uniforme, en promedio, la verificación de membresía para conjuntos de Python es O(1).

Creo que es un error común, set lookup (o hashtable para el caso) no son O(1).
de la Wikipedia

En el modelo más simple, la función hash está completamente sin especificar y la tabla no cambia de tamaño. Para la mejor elección posible de la función hash, una tabla de tamaño n con direccionamiento abierto no tiene colisiones y soporta hasta n elementos, con una sola comparación para una búsqueda exitosa, y una tabla de tamaño n con cadenas y teclas k tiene el máximo mínimo (0, k-n) colisiones y O(1 + k/n) comparaciones para la búsqueda. Para la peor opción de función hash, cada inserción causa una colisión, y las tablas hash degeneran en búsqueda lineal, con Ω(k) comparaciones amortizadas por inserción y hasta k comparaciones para una búsqueda exitosa.

Relacionado: Es un hashmap Java realmente O(1)?

Todos tenemos fácil acceso a la fuente , donde el comentario que precede a set_lookkey() dice:

/* set object implementation
 Written and maintained by Raymond D. Hettinger <[email protected]>
 Derived from Lib/sets.py and Objects/dictobject.c.
 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.
 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory.  This leaves
 us with a hybrid of linear probing and open addressing.  The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes.  After LINEAR_PROBES steps,
 we then use open addressing with the upper bits from the hash value.  This
 helps break-up long chains of collisions.
 All arithmetic on hash should ignore overflow.
 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.
*/


...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif

/* This must be >= 1 */
#define PERTURB_SHIFT 5

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)  
{
...

Para enfatizar un poco más la diferencia entre set's y dict's, aquí hay un extracto de las secciones de comentarios setobject.c, que aclaran la diferencia principal de los conjuntos contra los dictados.

Los casos de uso de los conjuntos difieren considerablemente de los diccionarios donde se consultaron es más probable que las llaves estén presentes. En contraste, los conjuntos son principalmente acerca de las pruebas de membresía donde la presencia de un elemento no se conoce en avance. En consecuencia, la aplicación del conjunto debe optimizar para ambos el caso encontrado y no encontrado.

Fuente en github