一文搞懂Python中list和dict的in操作的区别

---

Python中List和Dict基本操作的时间复杂度表

List

操作	操作说明	时间复杂度
index(value)	查找list某个元素的索引	O(1)
a = index(value)	索引赋值	O(1)
append(value)	队尾添加	O(1)
pop()	队尾删除	O(1)
pop(index)	根据索引删除某个元素	O(n)
insert(index, value)	根据索引插入某个元素	O(n)
search(in)	列表搜索（即in操作）	O(n)

Dict

操作	操作说明	时间复杂度
copy	复制	O(n)
get(value)	获取	O(1)
set(value)	修改	O(1)
delete(value)	删除	O(1)
search(in)	字典搜索（即in操作）	O(1)
iteration	字典迭代	O(n)

List和Dict的in操作对比

首先设计一个性能试验来验证list中检索一个值，以及dict中检索一个值的计时对比
生成包含连续值的list和包含连续关键码key的dict，用随机数来检验操作符in的耗时

import timeit
import random

for i in range(10000,1000001,20000):
	t = timeit.Timer("random.randrange(%d) in x"%i,
					 "from __main__ import random,x")
	x = list(range(i))
	lst_time = t.timeit(number=1000)
	x = {j:None for j in range(i)}
	d_time = t.timeit(number=1000)
	print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))

下表是程序运行的结果

规模大小	列表搜索所用时间	字典搜索所用时间
10000	0.062	0.001
30000	0.189	0.001
50000	0.329	0.001
70000	0.440	0.001
90000	0.582	0.001
110000	0.710	0.001
130000	0.840	0.001
150000	0.951	0.001
170000	1.077	0.001
190000	1.227	0.001
210000	1.377	0.001
230000	1.499	0.001
250000	1.618	0.001
270000	1.738	0.001
290000	1.892	0.001
310000	2.055	0.001

通过上例我们可以看到list的查找效率远远低于dict的效率，原因如下：

python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n),而dict对象的存储结构采用的是哈希表(散列表)，其在最优情况下查询复杂度为O(1)。

何为哈希表？

哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。(关键字就是所要存储的数据，存储位置相当于数组的索引)。
当然，可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1，而是由关键字(数据本身)通过哈希函数得到。

举例说明

例1.将26个小写字母存储到数组 int [26] a。

a对应a[0]，b对应a[1]，c对应a[3]……以此类推。

那么，数组 int [26] a 就是一个哈希表！

例1中，关键字(小写字母)是如何得到自己对应的索引(存储位置)的呢？

关键字的ASCII值减去a的ASCII值！

index = ch - 'a'
f(ch) = ch - 'a'
<index为索引，ch为字符的	ASCII>

上面说过，关键字通过哈希函数得到索引，所以，f(ch)就是本例题的哈希函数。

这样，我们就在关键字和数字(存储位置)之间建立了一个确定的对应关系f。

关键字与数字是一一对应的，由于数组本身支持随机访问，所以，当查找关键字时，只需要O(1)的查找操作，也就是实现了不经过任何比较，一次便能得到所查记录。

---

更详细了解的请参考：哈希表—什么是哈希表、Python列表/字典操作 时间复杂度