是什么使集合比列表更快？

Question

python Wiki上说：“使用集和字典进行成员资格测试比搜索序列O（n）更快，O（1）。测试“ a in
b”时，b应该是集合或字典，而不是列表或元组。”

每当速度在我的代码中很重要时，我就一直使用集代替列表，但是最近我一直在想为什么集比列表快得多。任何人都可以解释一下，或者让我指向可以解释这一点的消息源，这是为了在python中更快地进行设置吗？

Answer 1

集是使用哈希表实现的。每当将对象添加到集合中时，都会使用要添加的对象set的哈希值来确定对象在内存中的位置。在测试成员资格时，基本上需要做的只是查看对象是否在其哈希确定的位置，因此此操作的速度不取决于集合的大小。相反，对于列表，需要搜索整个列表，随着列表的增长，列表的搜索速度会变慢。

这也是集合不保留您添加的对象顺序的原因。

请注意，集合通常不会比列表快—成员资格测试对于集合来说更快，因此删除元素也是如此。只要您不需要这些操作，列表通常就会更快。