Python不同数据结构（列表、元组、集合、字典）查找速度原理问询

测试代码 #

arr = [45,42,2,18,23,1170,12,41,40,9,47,24,33,28,10,32,29,17,46,11,759,37,6,26,21,49,31,14,19,8,13,7,27,22,3,36,34,38,39,30,43,15,4,16,35,25,20,44,5,48]
d = {x: None for x in arr}
s = set(arr)
t = tuple(arr)

print(timeit.timeit(stmt="1170 in arr",globals = globals()))
print(timeit.timeit(stmt="1170 in d",globals = globals()))
print(timeit.timeit(stmt="1170 in s",globals = globals()))
print(timeit.timeit(stmt="1170 in t",globals = globals()))

测试结果：查找存在元素（1170） #

0.04749280004762113
0.03289399994537234
0.02820739999879152
0.05428230005782098

补充测试：查找不存在元素（9999） #

0.2764877999434248
0.0286063000094146
0.0490725999698043
0.3088887999765575

已知集合和字典查找的时间复杂度为O(1)，列表、元组为O(n)，针对测试结果的疑问及解答如下：

1. 为何集合/字典查找是O(1)，而列表/元组是O(n)？ #

• 集合和字典底层基于哈希表实现：存储元素时会计算元素的哈希值，直接映射到对应内存位置；查找时只需计算一次哈希值就能定位目标位置，平均无需遍历所有元素，因此时间复杂度为O(1)。
• 列表和元组是线性存储结构，元素按顺序排列，无索引映射机制。查找时必须从第一个元素开始逐个比对，最坏情况要遍历全部元素，因此时间复杂度为O(n)。

2. 同为O(1)复杂度，为何集合比字典更快（查找存在元素时），但查找不存在元素时字典更快？ #

• 查找存在元素时：集合仅存储元素本身，字典存储的是键值对。集合查找时计算哈希后直接校验元素匹配；字典则需先定位键的位置再确认存在，键值对的存储结构会带来额外开销，因此集合略快。
• 查找不存在元素时：Python字典的哈希表实现针对空槽位判断、哈希冲突处理做了更高效的优化，且底层经过长期迭代，对“键不存在”的场景有更精简的判断路径，因此此时字典比集合快。

3. 同为O(n)复杂度，为何元组比列表更慢？ #

• 列表作为动态数组，底层对元素访问做了大量缓存友好性优化，遍历的字节码指令执行效率更高。
• 元组是不可变结构，虽为线性存储，但在字节码层面的遍历逻辑优化程度不如列表；同时元组的内存结构更紧凑，但遍历比对时部分底层操作的开销略高于列表，导致整体速度稍慢。

内容的提问来源于stack exchange，提问作者JFK