图解算法之散列表
散列表
本文从两个方面介绍散列表
- 散列函数
- 冲突
散列函数
散列函数:将输入映射到数字,具有如下两个性质
1) 一致性
2) 最好是不同的映射对应不同的数字(回顾映射的性质)
在超市价格系统中,散列函数能够准确的指出价格的存储位置。创建的空数组用来存储商品的价格,散列函数将输入映射成数组的索引,这就是工作的机制。另外,散列表事先知道数组的大小,不会有溢出的情况发生。散列表在python中实现为字典:
book=dict()
继续添加商品价格
book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 1.49
print book
{'avocado': 1.49, 'apple': 0.67, 'milk': 1.49}
print book["avocade"]
如果你学过JavaScript或者json等语言的话,其实就能够很适应这种键和键值的对应。
示例:电话本
假设你的手机没有siri等小助手,你的电话簿十分庞大,假设你要创建一个类似这样的电话簿,将姓名映射到电话号码。需要有如下功能
-
添加联系人及其电话号码;
-
通过输入联系人来获悉其电话号码。
散列表来实现
- 创建映射;
- 查找。
phone_book = dict() (或者phone_book = {})
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
print phone_book["jenny"]
若引申到网页访问中,网址必须先转换为IP地址。
防止重复(降重)
计算机软件开发中,有一个很重要的思路就是降重。有些操作规定,每个ID或者某宝宝账号只能有一次机会,散列表就是很好的解决办法。
voted = {}
def check_voter(name):
if voted.get(name):
print "kick them out!"
else:
voted[name] = True
print "let them vote!"
#我们来测试几次
check_voter("tom")
let them vote!
check_voter("mike")
let them vote!
check_voter("mike")
kick them out!
散列表应用于缓存
流程:
cache = {}
def get_page(url):
if cache.get(url):
return cache[url]
else:
data = get_data_from_server(url)
cache[url] = data
return data
小结
- 模拟映射关系
- 降重
- 缓存数据
冲突(collision)
同时有APPLE和AVOCADOS可能会出现冲突,即同一个位置被覆盖的情况,Facebook是这么解决这个办法的:相当于两个维度,散列表和链表叠加在一起。
如图:
总结
- 你可以结合散列函数和数组(链表)来创建散列表。
- 应该最大限度减少冲突的散列函数。
- 散列表的查找、插入和删除速度都非常快。
- 散列表适合用于模拟映射关系。
- 散列表可用于缓存数据(例如,在Web服务器上)。
- 散列表非常适合降低重复。