Python-set()如何实现?

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

这里的每个答案都非常有启发性,但是我只能接受一个答案,因此,我将选择与原始问题最接近的答案。谢谢你的信息!

回答:

实际上,CPython的集合被实现为类似于带有伪值的字典(键是集合的成员)的字典,并且进行了一些优化,可以利用这种缺乏值的方式

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

如果你愿意的话,甚至可以浏览CPython源代码来查找集合,根据Achim Domma的说法,这主要是实现中的剪切粘贴dict

以上是 Python-set()如何实现? 的全部内容, 来源链接: utcz.com/qa/432110.html

回到顶部