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

问题描述：

Python wiki 上说：“使用集合和字典进行成员测试比搜索序列 O(n) 快得多，O(1)。测试“a in b”时，b 应该是集合或字典，而不是列表或元组。”

每当我的代码中速度很重要时，我都会使用集合代替列表，但最近我一直在想为什么集合比列表快得多。有人能解释一下，或者给我指出一个可以解释 Python 幕后到底发生了什么，让集合更快吗？

解决方案 1：

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

set：现在，想象一下你仍在衣柜里寻找袜子，但现在你知道袜子在哪个抽屉里，比如说在第三个抽屉里。所以，你只需要搜索第三个抽屉，而不是搜索所有抽屉。这就是我们所说的O(1)，因为在最糟糕的情况下，你只会在一个抽屉里寻找。

解决方案 2：

集合是使用哈希表实现的。每当您将对象添加到集合中时，set都会使用要添加的对象的哈希值来确定对象在内存中的位置。在测试成员资格时，需要做的所有事情基本上就是查看对象是否位于其哈希值确定的位置，因此此操作的速度与集合的大小无关。相比之下，对于列表，需要搜索整个列表，随着列表的增长，这会变得越来越慢。

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

请注意，集合通常不比列表快——集合的成员测试更快，删除元素也更快。只要您不需要这些操作，列表通常更快。

解决方案 3：

我认为你需要仔细看看数据结构方面的书。基本上，Python 列表是作为动态数组实现的，而集合是作为哈希表实现的。

这些数据结构的实现方式赋予了它们截然不同的特性。例如，哈希表的查找时间非常快，但无法保留插入顺序。

解决方案 4：

Python 使用哈希表，其查找时间为 O(1)。

解决方案 5：

虽然到目前为止我还没有测量过任何与 Python 相关的性能，但我仍然想指出列表通常更快。

是的，您有 O(1) 与 O(n)。但请始终记住，这仅提供有关某事物渐近行为的信息。这意味着如果您的 n 非常高，O(1) 总是会更快 - 理论上如此。然而在实践中，n 通常需要比您通常的数据集大得多。

因此，集合本身并不比列表快，但只有当你必须处理大量元素时才会如此。

解决方案 6：

基本上，取决于您正在执行的操作……

*对于添加元素 - 集合不需要移动任何数据，它所需要做的就是计算哈希值并将其添加到表中。对于列表插入，则可能需要移动数据。

*对于删除元素 - 集合需要做的就是从哈希表中删除哈希条目，对于列表，它可能需要移动数据（平均 1/2 的数据）。

*对于搜索（即 in 运算符），集合只需要计算数据项的哈希值，在哈希表中找到该哈希值，如果存在，则成功。对于列表，搜索必须依次查找每个项目，平均查找列表中所有项的 1/2。即使对于数千个项目，集合的搜索速度也会快得多。

解决方案 7：

实际上，集合并非在任何情况下都比列表快。通常，列表比集合快。但在搜索集合中的元素时，集合更快，因为集合是使用哈希表实现的。因此，基本上 Python 不必搜索整个集合，这意味着平均时间复杂度为 O(1)。列表使用动态数组，Python 需要检查整个数组才能搜索。因此需要 O(n)。

所以最后我们可以看到，在某些情况下，集合更好，在某些情况下，列表更好。我们需要根据自己的任务选择合适的数据结构。

解决方案 8：

必须逐个搜索列表，其中集合或字典具有索引以便更快地进行搜索。