python - set() 是如何实现的？

Question

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

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

Answer 1

根据 this thread :

Indeed, CPython's sets are implemented as something like dictionarieswith dummy values (the keys being the members of the set), with someoptimization(s) that exploit this lack of values

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

如果您愿意，您甚至可以浏览 CPython source code for set其中，根据 Achim Domma ，最初主要是 dict 实现的剪切和粘贴。

注意:如今，set 和 dict 的实现显着，因此精确的行为(例如任意顺序与插入顺序) ) 和在各种用例中的性能不同；它们仍然是根据哈希表实现的，因此平均情况查找和插入仍然是 O(1)，但是 set 不再只是“dict，但带有虚拟/省略键”。