我见过有人这么说setpython 中的对象具有 O(1) 成员资格检查。他们如何在内部实施以实现这一点？它使用什么类型的数据结构？该实施还有哪些其他影响？
这里的每个答案都非常有启发性，但我只能接受一个，所以我将选择最接近我原来问题的答案。谢谢你的信息！
根据:
事实上，CPython 的集合是像字典一样实现的
带有虚拟值（键是集合的成员），带有一些
利用这种价值缺失的优化
所以基本上是一个set使用哈希表作为其底层数据结构。这解释了O(1)成员资格检查，因为在哈希表中查找项目是一个O(1)操作，平均。
如果您愿意，您甚至可以浏览CPython 源代码set https://github.com/python/cpython/blob/main/Objects/setobject.c其中，根据阿奇姆·多玛 http://markmail.org/message/ktzomp4uwrmnzao6, was 起初大部分是从剪切和粘贴dict执行。
注：当今，set and dict的实现有所不同显著地，因此各种用例中的精确行为（例如任意顺序与插入顺序）和性能有所不同；它们仍然是根据哈希表实现的，因此平均情况查找和插入仍然存在O(1), but set不再只是“dict，但带有虚拟/省略的键”。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
