博客

该方法时间复杂度为O(1)，空间复杂度为O(n)

我们都知道哈希查找的时间复杂度仅为O(1)，所以不管使用什么语言，当然是把要查找的数据存放到哈希表中再进行查找

时间效率最高

（要是想要空间复杂度低的这个方法并不适合哦）。

那我们都知道Python的字典底层是基于哈希表实现的，那我们只要将List中的数据存到

Dictionary

中再进行查找就能够实现O(1)的效率查找数据。

有关Python字典的介绍可以看

菜鸟教程-Python字典

实现

import random
import time

# 创建一个含有1000000个整数的list并打乱顺序
lst = list(range(1000000))
random.shuffle(lst)

# 将List存入字典
tempLst = list(range(len(lst)))   # 生成一个0-List大小的有序整数List，之后作为Dictionary的value，代表对应的key在原先的List中的位置（索引值）
dct = dict(zip(lst, tempLst))    # 用zip方法将原List与索引值信息List组成键值对存入Dictionary

# 字典方式查找
start =time.clock()    # 计时用
if 283 in dct:
    print("该元素在列表的第", dct[283], "个")    # 打印283在原List中的位置
else:
    print("列表中没有这个元素")
end = time.clock()    # 计时用
print('查找用时(字典方式): %s秒'%(end-start))

# index方式查找
start =time.clock()    # 计时用
if lst.count(283) > 0:
    print("该元素在列表的第", lst.index(283), "个")    # 打印283在原List中的位置
else:
    print("列表中没有这个元素")
end = time.clock()    # 计时用
print('查找用时(index方式): %s秒'%(end-start))

输出结果

该元素在列表的第 622688 个
查找用时(字典方式): 0.0001274秒
该元素在列表的第 622688 个
查找用时(index方式): 0.07245950000000001秒

我们将数据量由1000000增加10倍变为10000000，再看输出结果

该元素在列表的第 7049699 个
查找用时(字典方式): 0.00019109999999999998秒
该元素在列表的第 7049699 个
查找用时(index方式): 0.8544263999999999秒

可以看出数据量的增大对改为字典方式的查找几乎没有影响，这就是哈希查找O(1)复杂度的强大之处了！