数据结构与算法-散列表

本节内容:

• 散列函数
• 散列表的应用
• 冲突
• 性能
• 小结

散列函数

散列函数的定义：将输入映射到数字

实现散列函数的要求：

• 必须一致：即同样的值经过散列函数，返回的值必须是一样的『注意：就算不同的输入得到的是相同的值，只要是同样的数输入得到的同样的值就是一致，f(x)=1 是满足一致的！』
• 应该将不同的输入映射到不同的数字。例如， 如果一个散列函数不管输入是什么都返回 1，它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。

散列函数能够准确的指出输入对应的输出的位置：

• 散列函数总是将同样的输入映射到相同的索引。
• 散列函数将不同的输入映射到不同的索引。
• 散列函数知道数组有多大，只返回有效的索引。

通过散列函数和数组实现散列表（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 后面的其他位置。换言之，这个散列表中的所有元素都在这个链表中，这与一开始就将所有元素存储到一个链表中一样糟糕：散列表的速度会很慢。

故有两条经验法则：

• 散列函数很重要。最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。
• 如果散列表存储的链表很长，散列表的速度将急剧下降。

性能

如何创建一个“好”的散列表，极其影响其性能。

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。因此在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。避免冲突的几个指标是：

• 较低的填装因子：填装因子 = 散列表包含的元素数/位置总数

• 良好的散列函数：让数组中的值呈均匀分布。

小结

• 大部分编程语言已经实现散列表，python 中的字典等，
• 散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型
• 你可以结合散列函数和数组来创建散列表。
• 冲突很糟糕，应使用可以最大限度减少冲突的散列函数。
• 散列表的查找、插入和删除速度都非常快。
• 散列表适合用于模拟映射关系。
• 一旦填装因子超过 0.7，就该调整散列表的长度。
• 散列表可用于缓存数据（例如，在Web服务器上）。
• 散列表非常适合用于防止重复。

参考资料: 图解算法