集合为什么比列表快？

Question

Python的维基百科上说：“用集合和字典来测试成员资格的速度要快得多，复杂度是O(1)，而查找序列的复杂度是O(n)。当你测试‘a in b’时，b应该是一个集合或字典，而不是列表或元组。”

我在代码中只要速度重要，就会用集合代替列表，但最近我在想，为什么集合比列表快这么多。有没有人能解释一下，或者给我指个地方，让我了解一下在Python中，集合为什么会更快的原因？

Answer 1

我觉得你应该好好看看一本关于数据结构的书。简单来说，Python中的列表是用动态数组来实现的，而集合则是用哈希表来实现的。

这些数据结构的实现方式让它们的特点差别很大。例如，哈希表查找的速度非常快，但它不能保持插入的顺序。

Answer 2

list: 想象一下，你在衣柜里找袜子，但你不知道袜子在哪个抽屉，所以你得一个一个抽屉地找，直到找到它们（或者可能永远找不到）。这就是我们所说的 O(n)，因为在最坏的情况下，你需要查看所有的抽屉（这里的 n 是抽屉的数量）。

set: 现在，想象你还是在衣柜里找袜子，但这次你知道袜子在第3个抽屉里。所以，你只需要去第3个抽屉找，而不是每个抽屉都找。这就是我们所说的 O(1)，因为在最坏的情况下，你只需要查看一个抽屉。

Answer 3

集合是通过哈希表来实现的。当你往集合里添加一个对象时，系统会根据这个对象的哈希值来决定它在内存中的位置。检查一个对象是否在集合里时，只需要看看这个对象是否在它的哈希值所指的位置，所以这个操作的速度和集合的大小没有关系。相比之下，列表需要遍历整个列表来查找，这样随着列表的增大，速度就会变慢。

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

需要注意的是，集合并不总是比列表快——在检查一个对象是否存在时，集合更快，删除元素时也是如此。不过，只要你不需要这些操作，列表通常会更快。