知识问答

set（）如何实现？

内容 隐藏
问题：set（）如何实现？
回答 0
回答 1
回答 2
回答 3
回答 4

问题：set（）如何实现？

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

这里的每个答案都非常有启发性，但是我只能接受一个答案，因此，我将选择与原始问题最接近的答案。谢谢你的信息！

点击查看英文原文

I’ve seen people say that set objects in python have O(1) membership-checking. How are they implemented internally to allow this? What sort of data structure does it use? What other implications does that implementation have?

Every answer here was really enlightening, but I can only accept one, so I’ll go with the closest answer to my original question. Thanks all for the info!

回答 0

根据这个线程：

实际上，CPython的集合被实现为类似于带有伪值的字典（键是集合的成员）的字典，并且进行了一些优化，可以利用这种缺乏值的方式

因此，基本上a set使用哈希表作为其基础数据结构。这解释了O（1）成员资格检查，因为在哈希表中查找项目平均而言是O（1）操作。

如果您愿意，甚至可以浏览CPython源代码以获取集合，根据Achim Domma的说法，该代码大部分是实现中的剪切和粘贴dict。

点击查看英文原文

According to this thread:

Indeed, CPython’s sets are implemented as something like dictionaries with dummy values (the keys being the members of the set), with some optimization(s) that exploit this lack of values

So basically a set uses a hashtable as its underlying data structure. This explains the O(1) membership checking, since looking up an item in a hashtable is an O(1) operation, on average.

If you are so inclined you can even browse the CPython source code for set which, according to Achim Domma, is mostly a cut-and-paste from the dict implementation.

回答 1

当人们说集合具有O（1）成员资格检查时，他们正在谈论平均情况。在最坏的情况下（当所有哈希值冲突时），成员资格检查为O（n）。有关时间复杂性，请参见Python Wiki。

在维基百科的文章说，最好的情况下为一个哈希表，不调整大小的时间复杂度O(1 + k/n)。由于Python集使用调整大小的哈希表，因此该结果并不直接适用于Python集。

在Wikipedia文章上再说一点，对于一般情况，并假设一个简单的统一哈希函数，时间复杂度为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)。

点击查看英文原文

When people say sets have O(1) membership-checking, they are talking about the average case. In the worst case (when all hashed values collide) membership-checking is O(n). See the Python wiki on time complexity.

The Wikipedia article says the best case time complexity for a hash table that does not resize is O(1 + k/n). This result does not directly apply to Python sets since Python sets use a hash table that resizes.

A little further on the Wikipedia article says that for the average case, and assuming a simple uniform hashing function, the time complexity is O(1/(1-k/n)), where k/n can be bounded by a constant c<1.

Big-O refers only to asymptotic behavior as n → ∞. Since k/n can be bounded by a constant, c<1, independent of n,

O(1/(1-k/n)) is no bigger than O(1/(1-c)) which is equivalent to O(constant) = O(1).

So assuming uniform simple hashing, on average, membership-checking for Python sets is O(1).

回答 2

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

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

相关：Java哈希图真的是O（1）吗？

点击查看英文原文

I think its a common mistake, set lookup (or hashtable for that matter) are not O(1).
from the Wikipedia

In the simplest model, the hash function is completely unspecified and the table does not resize. For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to n elements, with a single comparison for successful lookup, and a table of size n with chaining and k keys has the minimum max(0, k-n) collisions and O(1 + k/n) comparisons for lookup. For the worst choice of hash function, every insertion causes a collision, and hash tables degenerate to linear search, with Ω(k) amortized comparisons per insertion and up to k comparisons for a successful lookup.

Related: Is a Java hashmap really O(1)?

回答 3

我们都可以轻松访问source，前面的评论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)  
{
...
点击查看英文原文

We all have easy access to the source, where the comment preceding set_lookkey() says:

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

回答 4

为了进一步强调set's和之间的区别dict's，这是setobject.c注释部分的摘录，其中阐明了set与dicts的主要区别。

集合的用例与字典中存在较大差异的字典大相径庭。相反，集合主要是关于成员资格测试，其中事先不知道元素的存在。因此，集合实现需要针对发现和未发现的情况进行优化。

github上的源代码

点击查看英文原文

To emphasize a little more the difference between set's and dict's, here is an excerpt from the setobject.c comment sections, which clarify’s the main difference of set’s against dicts.

Use cases for sets differ considerably from dictionaries where looked-up keys are more likely to be present. In contrast, sets are primarily about membership testing where the presence of an element is not known in advance. Accordingly, the set implementation needs to optimize for both the found and not-found case.

source on github