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) { ...