set() 是如何实现的? [英] How is set() implemented?

问题描述

我看到有人说 python 中的 set 对象具有 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!

推荐答案

根据这个帖子:

确实，CPython 的集合被实现为类似于字典的东西带有虚拟值(键是集合的成员)，还有一些利用这种缺乏价值的优化

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

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

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.

如果您愿意，您甚至可以浏览 CPython 源代码设置代码，根据Achim Domma，主要是从dict 实现.

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.

这篇关于set() 是如何实现的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！