其他（杂） - 散列表 - 《数据结构与算法学习之路》

layout: posttitle: 数据结构与算法—散列表
date: 2019-10-15
tag: 数据结构与算法

layout: posttitle: 数据结构与算法—散列表
date: 2019-10-15
tag: 数据结构与算法

本节内容:

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

散列函数

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

实现散列函数的要求：

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

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

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

通过散列函数和数组实现散列表（hash table）

散列表可能是最有用的，也被称为散列映射、映射、字典和关联数组。散列表的速度很快！

散列表的应用

散列表用于查找：手机薄，一个联系人对应一个手机号码
防止重复：投票系统防止同一个用户进行重复投票
用于缓存：网页的缓存机制（网站将数据记住，而不再重新计算。），如用户未登录时，显示相同的内容，用户登录时，向服务器请求新的网页。缓存的优点：用户能够更快地看到网页，降低服务器负载。『缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！』

散列表 - 图2

# 创建一个手机薄
# 添加联系人及其电话号码。通过输入联系人来获悉其电话号码。
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!