set() 是如何实现的？

问题描述：

我曾听人说过setPython 中的对象具有 O(1) 成员资格检查。它们在内部是如何实现的？它使用哪种数据结构？该实现还有哪些其他含义？

这里的每个答案都很有启发性，但我只能接受一个，所以我会选择最接近我原始问题的答案。感谢大家提供的信息！

解决方案 1：

根据此主题：

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

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

如果您愿意的话，您甚至可以浏览CPython 源代码set，根据Achim Domma 的说法，该源代码最初大部分是从实现中剪切粘贴的dict。

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

解决方案 2：

当人们说集合具有 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)。

解决方案 3：

我认为这是一个常见的错误，set查找（或哈希表）不是 O（1）。

摘自维基百科

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

相关：Java 哈希图真的是 O(1) 吗？

解决方案 4：

我们都可以轻松访问源代码，其中前面的评论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)  
{
...

解决方案 5：

为了进一步强调set's和之间的区别dict's，这里摘录了评论部分的内容setobject.c，阐明了 set 与 dicts 的主要区别。

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

github上的源代码

解决方案 6：

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]