本节内容:
散列函数的定义:将输入映射到数字
实现散列函数的要求:
散列函数能够准确的指出输入对应的输出的位置:
通过散列函数和数组实现散列表(hash table)
散列表可能是最有用的,也被称为散列映射、映射、字典和关联数组。散列表的速度很快!
# 创建一个手机薄
# 添加联系人及其电话号码。通过输入联系人来获悉其电话号码。
phone_book = dict()
phone_book["Bob"] = 123 # 添加新联系人
phone_book["Logan"] = 567 # # 添加新联系人
phone_book["Bob"] # 查询联系人
# 投票检测系统
# 首次投票让其进行投票,投过票以后将其加入已投票名单,若重复投票将被检测出来
voted = dict()
def check_voter(name):
if voted.get(name):
print("kick them out!")
else:
voted[name] = True
print("let them vote!")
check_voter("Bob") # let them vote!
check_voter("Logan") # let them vote!
check_voter("Bob") # kick them out! 因为已经投过票了
def get_data_from_server(url):
# 模拟向服务器请求
return url
cache = {}
def get_page(url):
if cache.get(url):
print("get info from local!")
return cache[url] # 返回缓存的数据
else:
data = get_data_from_server(url)
cache[url] = data # 将数据保存于缓存中
print("get info from server!")
return data
get_page("www.google.com") # get info from server!
get_page("www.bing.com") # get info from server!
get_page("www.google.com") # get info from local!
创建散列函数是怎样引起冲突的呢?
如果创建的数据大小小于我们要存储的数据量,那么会导致每个数据不能对应唯一到数组上的位置。例如我们创建一个长度为 26 的数组(英文字母的个数),用它来存储所有的英文单词,明显他并不符合我们创建散列函数的要求。这就形成了冲突:冲突很糟糕,必须要避免。
解决的办法是:如果两个键映射到了同一个位置,就在这个位置存储一个链表。
但是此时又会引起一个问题,假设世界上全部的单词都是以 A 开头的,那么我们就白白浪费了 A 后面的其他位置。换言之,这个散列表中的所有元素都在这个链表中,这与一开始就将所有元素存储到一个链表中一样糟糕:散列表的速度会很慢。
故有两条经验法则:
如何创建一个“好”的散列表,极其影响其性能。
在平均情况下,散列表的查找(获取给定索引处的值)速度与数组一样快,而插入和删除速度与链表一样快,因此它兼具两者的优点!但在最糟情况下,散列表的各种操作的速度都很慢。因此在使用散列表时,避开最糟情况至关重要。为此,需要避免冲突。避免冲突的几个指标是:
参考资料: 图解算法