201

我见过有人说setpython 中的对象有 O(1) 成员资格检查。它们如何在内部实现以允许这样做？它使用什么样的数据结构？该实施还有哪些其他影响？

这里的每一个答案都很有启发性，但我只能接受一个，所以我会选择最接近我最初问题的答案。谢谢你的信息！

4

6 回答 6

188

根据这个线程：

实际上，CPython 的集合被实现为类似于具有虚拟值的字典（键是集合的成员），并进行了一些优化来利用这种缺乏值

所以基本上 aset使用哈希表作为其底层数据结构。这解释了成员资格检查，因为平均而言，在O(1)哈希表中查找项目是一项操作。O(1)

如果您愿意，您甚至可以浏览CPython 源代码set，根据Achim Domma的说法，这些源代码最初主要是从实现中剪切和粘贴的dict。

注意：如今，set和dict的实现已经有了很大的不同，因此各种用例中的精确行为（例如任意顺序与插入顺序）和性能有所不同；它们仍然是根据哈希表实现的，因此保留了平均大小写查找和插入O(1)，但set不再只是“ dict，而是带有虚拟/省略键”。

于 2010-10-16T14:47:43.110 回答
92

当人们说集合具有 O(1) 成员资格检查时，他们指的是平均情况。在最坏的情况下（当所有散列值发生冲突时）成员资格检查是 O(n)。请参阅有关时间复杂度的 Python wiki。

维基百科文章说，不调整大小的哈希表的最佳情况O(1 + k/n)时间复杂度是. 这个结果并不直接适用于 Python 集，因为 Python 集使用了一个可以调整大小的哈希表。

维基百科文章进一步说，对于平均情况，假设一个简单的统一散列函数，时间复杂度是O(1/(1-k/n))，其中k/n可以由一个常数 限制c<1。

Big-O 仅指作为 n → ∞ 的渐近行为。由于 k/n 可以由一个常数 c<1 限定，与 n 无关，

O(1/(1-k/n))不大于O(1/(1-c))等于O(constant)=的那个O(1)。

因此，假设统一的简单散列，平均而言，Python 集的成员资格检查是O(1).

于 2010-10-16T16:47:12.853 回答
15

我认为这是一个常见的错误，set查找（或哈希表）不是 O(1)。
来自维基百科

在最简单的模型中，哈希函数是完全未指定的，并且表不会调整大小。对于散列函数的最佳选择，具有开放寻址的大小为 n 的表没有冲突并且最多可容纳 n 个元素，通过一次比较以成功查找，并且具有链接和 k 个键的大小为 n 的表具有最小最大值(0, kn) 碰撞和O(1 + k/n)比较查找。对于哈希函数的最坏选择，每次插入都会导致冲突，并且哈希表会退化为线性搜索，每次插入进行 Ω(k) 摊销比较，最多进行 k 次比较才能成功查找。

相关：Java hashmap 真的是 O(1) 吗？

于 2010-10-16T14:57:26.020 回答
14

我们都可以轻松访问源代码，前面的评论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)  
{
...
于 2010-10-16T14:59:38.607 回答
3

set's为了更加强调和之间的区别dict's，这里是评论部分的摘录setobject.c，它阐明了 set 与 dicts 的主要区别。

集合的用例与更可能出现查找键的字典有很大不同。相反，集合主要是关于成员资格测试，其中元素的存在是事先不知道的。因此，集合实现需要针对找到和未找到的情况进行优化。

github上的源码

于 2017-11-15T08:58:10.640 回答
2

python 中的集合在内部使用哈希表。我们先来说说哈希表。假设您想要将一些元素存储在哈希表中，并且您在哈希表中有 31 个可以这样做的位置。设元素为：2.83、8.23、9.38、10.23、25.58、0.42、5.37、28.10、32.14、7.31。当您想使用哈希表时，您首先要确定哈希表中将存储这些元素的索引。模函数是确定这些索引的一种流行方法，因此假设我们一次取一个元素，将其乘以 100 并应用模数乘以 31。重要的是，对元素的每个此类操作都会产生一个唯一的数字作为除非允许链接，否则哈希表中的条目只能存储一个元素。这样，每个元素将存储在由通过模运算获得的索引控制的位置。现在，如果您想在一个基本上使用此哈希表存储元素的集合中搜索一个元素，您将在 O(1) 时间内获得该元素，因为该元素的索引是在恒定时间内使用模运算计算的。为了说明模运算，我还写了一些代码：

piles = [2.83, 8.23, 9.38, 10.23, 25.58, 0.42, 5.37, 28.10, 32.14, 7.31]

def hash_function(x):
    return int(x*100 % 31)

[hash_function(pile) for pile in piles]

输出：[4、17、8、0、16、11、10、20、21、18]

于 2020-10-23T07:26:00.950 回答