Python的`in`关键字是线性查找吗？

Question

Python是怎么检查一个值是否在可迭代对象（比如列表、元组等）中存在的呢？它是用in这个关键词来实现的。这个过程是线性搜索吗？比如说：

def naive(iterable, val):
    for i in range(len(l)):
        if iterable[i]==val:
            return True
    return False

还是说它有其他的方法来做到这一点，而不是线性搜索呢？

Answer 1

如果是线性数据结构，那就是线性搜索。比如说，列表和字符串就是线性数据结构的例子。如果是集合，那查找的时间是O(1)，也就是说速度很快；如果我们在字典里检查一个键是否存在，也是O(1)。

Answer 2

在编程中，in这个关键词的工作方式取决于你所调用的对象类里面的__contains__方法是怎么实现的。这就是说，对于那些不能被哈希的东西（比如列表和字符串），它会进行线性搜索，也就是一个一个地查找。而对于可以被哈希的数据结构（比如字典和集合），它的查找速度会更快，基本上是常量时间，意思是查找的时间几乎是固定的，不会随着数据量的增加而增加。

Answer 3

在Python中，in这个操作符会调用一个叫做__contains__的特殊函数，这个函数在不同的容器中实现方式是不同的。

对于字符串（str）、列表（list）和元组（tuple）来说，它们的查找方式是线性搜索，也就是说要一个一个地找，这种方式的时间复杂度是O(N)。不过，由于这个功能是用C语言实现的，所以它的速度可能比你在问题中提到的纯Python实现要快。

而对于集合（set）和字典（dict）来说，查找方式是哈希表查找，这种方式要快得多，平均情况下的时间复杂度是O(1)。

其他的容器可能会有不同的性能特点。我觉得在标准库中没有其他容器，但如果是平衡树这种数据结构，查找的时间复杂度可能是O(log N)。