字典也是python中的一个常用数据结构。字典的 get 和 set 操作都是 O(1)。另一个重要的操作是 contains，检查一个键是否在字典中也是 O(1)。这是非常重要的一个性质。
contains操作在列表与字典间的比较
我们将在实验中列出一系列数字。然后随机选择数字，并检查数字是否在列表和字典中。
import matplotlib.pyplot as plt
from timeit import Timer
import random
list_length = [] ##记录数据总量
list_list = [] ##记录列表查询时间
list_dict = [] ##记录字典查询时间
for i in range(10000,1000001,20000):
list_length.append(i)
print(i)
x = list(range(i)) ##建立列表
t_list = Timer("random.randrange(%d) in x"%i, "from __main__ import random,x")
list_list.append(t_list.timeit(number=1000))
del x ##释放列表的存储空间
y = {j:None for j in range(i)} ##建立字典
t_dict = Timer("random.randrange(%d) in y"%i, "from __main__ import random,y")
list_dict.append(t_dict.timeit(number=1000))
del y
plt.figure(figsize=(8,4))
plt.plot(list_length,list_list,label="$List$",color="red",linewidth=2)
plt.plot(list_length,list_dict,"b--",label="$Dictionary$")
plt.xlabel("List Length")
plt.ylabel("ms")
plt.legend()
plt.show()
运行结果如下：
可以看出，在此过程中，列表越大，确定列表中是否包含任意一个数字应该花费的时间越长；而同样的操作在字典中花费的时间是恒定的。从图中也可以确认列表的 contains 操作符是 O(n)，字典的 contains 操作符是 O(1)。
python中字典主要操作的时间复杂度（来自网络）：
