set（）如何实现？ [英] How is set() implemented?

问题描述

我已经看到有人说在python中的设置对象有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

所以基本上一个集使用散列表作为其底层数据结构。这解释了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 ，它们主要是从<$ c $中剪切并粘贴c> 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屋！