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，但使用虚拟/省略键”。