¿Cómo se implementa set ()?

He visto a personas decir que los objetos set en python tienen O (1) control de membresía. ¿Cómo se implementan internamente para permitir esto? ¿Qué tipo de estructura de datos utiliza? ¿Qué otras implicaciones tiene esa implementación?

Todas las respuestas aquí fueron realmente esclarecedoras, pero solo puedo aceptar una, así que iré con la respuesta más cercana a mi pregunta original. ¡Gracias a todos por la información!

Según este hilo :

De hecho, los conjuntos de CPython se implementan como algo así como diccionarios con valores ficticios (las claves son los miembros del conjunto), con algunas optimizaciones que aprovechan esta falta de valores.

Básicamente, un set utiliza una tabla hash como estructura de datos subyacente. Esto explica la verificación de membresía O (1), ya que buscar un elemento en una tabla hash es una operación O (1), en promedio.

Si está tan inclinado, incluso puede navegar por el código fuente de CPython para establecer que, según Achim Domma , es en su mayoría un corte y pegado de la implementación de dict .

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

El artículo de Wikipedia dice que la mejor complejidad de tiempo de caso 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 suponiendo una función de hashing uniforme simple, la complejidad del tiempo es O(1/(1-k/n)) , donde k/n puede estar delimitada por una constante c<1 .

Big-O se refiere solo al comportamiento asintótico como n → ∞. Como k / n puede estar delimitado por una constante, c <1, independiente de n ,

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

Entonces, asumiendo que el hashing simple y uniforme, en promedio , la comprobación de la membresía para los conjuntos de Python es O(1) .

Creo que es un error común, la búsqueda de set (o tabla hash para el caso) no es O (1).
de la Wikipedia

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

Relacionados: ¿Es un hashmap de Java realmente O (1)?

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

 /* set object implementation Written and maintained by Raymond D. Hettinger  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 los set's y los dict's , aquí hay un extracto de las secciones de comentarios de setobject.c , que aclaran la diferencia principal de los sets contra los dictados.

Los casos de uso para conjuntos difieren considerablemente de los diccionarios en los que es más probable que haya claves buscadas. En contraste, los conjuntos son principalmente sobre pruebas de membresía donde la presencia de un elemento no se conoce de antemano. En consecuencia, la implementación del conjunto debe optimizar tanto el caso encontrado como el no encontrado.

fuente en github