set（）如何实现？
我见过有人说在Python中set对象有O（1）成员资格检查。 他们如何实施内部允许这个？ 它使用什么样的数据结构？ 这个实现有什么其他的影响？
这里的每一个答案都很有启发性，但我只能接受一个，所以我会用最接近的答案去回答我原来的问题。 感谢所有的信息！
根据这个线程 ：
事实上，CPython的集合被实现为具有虚拟值的字典（关键字是集合的成员），而某些优化则利用了这种缺乏值
所以基本上一个set使用散列表作为其基础数据结构。 这解释了O（1）成员资格检查，因为查找散列表中的项目平均是O（1）操作。
如果你非常喜欢，你甚至可以浏览CPython的源代码 ，根据Achim Domma的说法，这个代码主要是从dict实现中剪切粘贴的。
当人们说集合有O（1）成员资格检查，他们谈论平均情况。 在最坏的情况下（当所有散列值碰撞时）成员检查是O（n）。 在时间复杂度上查看Python维基 。
维基百科的文章说，不resize的散列表的最佳时间复杂度是O(1 + k/n) 。 这个结果并不直接适用于Python集合，因为Python集合使用了一个resize的哈希表。
维基百科文章稍微进一步说，对于平均情况，假设一个简单的统一散列函数，时间复杂度为O(1/(1-k/n)) ，其中k/n可以由常数c<1 。
大O只是指n→∞的渐近行为。 由于k / n可以由一个常数来限定，c <1， 与n无关 ，
O(1/(1-k/n))不大于等于O(constant) = O(1) O(1/(1-c)) O(1) 。
所以假设统一的简单散列， 平均来说 ，Python集合的成员检查是O(1) 。
我认为它是一个常见的错误， set查找（或散列表）不是O（1）。
从维基百科
在最简单的模型中，散列函数是完全没有指定的，表格不能resize。 为了最好的select散列函数，一个大小为n的开放寻址的表没有冲突，最多可容纳n个元素，只有一个比较才能成功查找，而一个大小为n的链表和k个键的表的最小值为max （0，kn）碰撞和O（1 + k / n）比较进行查找。 对于散列函数的最差select，每个插入导致冲突，并且散列表退化为线性search，每个插入的Ω（k）摊销比较以及成功查找的多达k个比较。
相关： 是一个Java HashMap真的O（1）？
我们都可以轻松访问源代码 ，在set_lookkey()之前的注释中说：
/* set object implementation Written and maintained by Raymond D. Hettinger <python@rcn.com> 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) { ...
