数据结构与算法-散列表

本节内容:

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

散列函数

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

实现散列函数的要求:

  • 必须一致:即同样的值经过散列函数,返回的值必须是一样的『注意:就算不同的输入得到的是相同的值,只要是同样的数输入得到的同样的值就是一致,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服务器上)。
  • 散列表非常适合用于防止重复。

参考资料: 图解算法

原文发布于微信公众号 - 脑洞前端(fe_lucifer)

原文发表时间:2019-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券