专栏首页KEN DO EVERTHING【从0到1学算法】散列表

【从0到1学算法】散列表

这可能是这么多种数据结构中最有用的-----散列表。

一、什么是散列表

超市中用到的条形码,每个码对应一个商品,扫一下马上就能知道商品的价格,查询速度O(1)。哪种数据结构能做到这样?那只有散列表了。

散列函数

首先需要理解散列函数,散列函数是散列表的灵魂。

散列函数是这样的函数,无论你给他什么数据,它都还给你一个数字。

专业点说,就是散列函数“将输入映射到数字”。

散列函数映射数字有这些规则:

1.相同的输入,输出必定也相同。例如,假设输入apple得到4,那每次输入apple得到都是4。

2.不同的输入映射到不同数字。(这是最理想情况)

这有何用途?当然是用来打造散列表。

首先创建一个空数组。

我们将在这个数组中存储商品价格。下面将苹果的价格加入这个数组中,输入apple到散列函数。输出为3,因此将苹果价格存储的索引3位置。

下面将牛奶价格存储到数组中。

不断重复这个过程,最终将数组填满。

现在你想知道鳄梨(avocado)的价格,你无需遍历数组查找,只需将avocado作为输入交给散列函数,它就会帮你找到它。

这便是散列表,利用散列函数构造的数据结构,能够快速找到想要的数据,理想情况下速度为O(1)。散列表可能是你学习的复杂数据结构中最有用的,也成为散列映射、映射、字典和关联数组。

很多时候你根本不需要自己去实现散列表,在很多优秀语言中都提供了散列表的实现。比如Java中的Map, Python中的字典Dictionary。

二.冲突

前面我们说到,散列函数在理想情况下,不同的输入映射到不同数字。但没有那么多的理想情况,有时候散列函数会发生冲突,这影响着散列表的性能。

假设有这样一个数组,它包含26个位置。

而使用的散函数很简单:按字母表顺序分配数组的位置。

将苹果价格存储到散列表中,分配的是第一个位置。香蕉则是第二个位置。

然而,如果要将鳄梨(avocado)存进去,分配的还是第一个位置,可是第一个位置已经放了苹果!这种情况被称为冲突:给两个键分配相同位置。

处理冲突的方式有很多,其中最简单是拉链法:如果连个键映射到同一个位置,就在这个位置上存储一个链表。

在这个例子中,查询香蕉的价格依然很快,而查询A开头的物品时就慢一些,因为需要遍历链表。如果这个链表很短,那没什么大不了,只需搜索几个元素即可。但是,假设这散列表中只存在以字母A开头的物品,这就很糟糕了!散列表会很慢。

这里可得这样的经验教训。

  1. 散列函数很重要,最坏的情况是所有键都映射到同一个位置,最理想的情况是不同键映射到不同位置。
  2. 散列表的链表很长,查询速度会急剧下降。良好的散列函数,不会导致很长的链表。

良好的散列函数是避免冲突的关键之一。

三、填装因子

较低的填装因子是避免冲突的关键之二。填装因子计算公式为:散列表包含的元素数/位置总数。例如,下面的散列表的填装因子为2/5=0.4

一旦填装因子大到一定程度,就需要在散列表中添加位置,这被称为调整长度。通常会将数组增长一倍。

例如下面这个散列表,规定达到3/4时调整长度。

这是需要调整长度,首先创建一个更长的新数组:长度为原来的2倍。

接下来,通过散列函数将所有元素插入到这个新数组中。

填装因子越低,发生冲突的可能性越小,散列表性能越高。但是填装因子越低,空间利用率就越低,所以需要取平衡。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表长度。

四、应用案例

1.快速查找

在大量的数据中查找想要的信息,散列表是一个不错的选择。

比如电话本,将每个姓名映射到电话号码

或是DNS解析。在你访问一个网址时,比如http://adit.io,在DNS服务器会将它转换为IP地址。

无论访问哪个网址,它都必须转换为IP地址。

网址映射到IP地址,这很适合用散列表。

2.防止重复

散列表中每个键只会对应一个位置,无法存储相同的键,这可以起到防重复的效果。

比如,现在需要创建一个投票程序,每个人只能投一票,我们可以用散列表来检查这个人是否已投过票。

3.用作缓存

还有一个重要应用:缓存。其中网页缓存,我们应该经常听到。

假设你正在访问Facebook登录页面,这是一个通用的页面,经常会被缓存到你电脑中。当你第二次打开登录页面,你会发现会比第一次打开的速度快,因为你访问的是你电脑中的缓存数据,而从Facebook服务器下载数据。

除了登录页,一般还会存储主页、About页面、Contact页面等等。

而散列表是这样起到缓存作用的:

小结

  • 散列表可以用散列函数和数组构成。
  • 冲突很糟糕,会严重影响散列表的性能。
  • 避免冲突的两个关键:
    1. 良好的散列函数
    2. 较低的填装因子
  • 常见应用
    1. 快速查找
    2. 防止重复
    3. 缓存

本文分享自微信公众号 - KEN DO EVERTHING(KENDOEVERTHING),作者:a丶ken

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「 从0到1学习微服务SpringCloud 」06 统一配置中心Spring Cloud Config

    「 从0到1学习微服务SpringCloud 」01 一起来学呀! 「 从0到1学习微服务SpringCloud 」02 Eureka服务注册与发现 「 从0到...

    KEN DO EVERTHING
  • 「 互联网笔试题 」No.2 2018酷狗秋招笔试题

    一.单选题 1、在命中率极高的缓存设计中,时间复杂度最差的数据结构是( ) A. 数组 B. 链表 C. 树 D. 哈希表

    KEN DO EVERTHING
  • 【从0到1学算法】二分查找法

    说到算法,大家应该都会脑壳疼吧。除了应付一下面试,准备过算法,也接触过不少算法,但是面试完了,基本上就忘光了。但不得不说,算法真的很重要,算法是解决问的方法,你...

    KEN DO EVERTHING
  • 散列表 - Hash Table

    哈希表(Hash Table),学名散列表。散列表最核心的部分就是散列函数。有了散列函数,无论你给它什么输入数据,它都还你一个数字。专业一点的话,就是散列函数将...

    caoqi95
  • Python算法分享系列-查找,排序,递归

    iTesting,爱测试,爱分享 沉寂了一段时间,继续学习。 算法这个系列我想分享很久了,奈何本身对算法不是特别了解,又找不到合适的载体来分享。 最近看了本有趣...

    企鹅号小编
  • 算法图解(五)|散列表与字典

    我们之前介绍过简单查找和二分查找,简单查找是从头开始一个个查找,二分查找是在有序列表中按分而治之的思想进行查找,虽然二分查找已经很快速了,但是在有些情况下,还是...

    AI深度学习求索
  • HashMap、LRU、散列表

    获取对象的hashcode以后,先进行移位运算,然后再和自己做异或运算,即:hashcode ^ (hashcode >>> 16),这一步甚是巧妙,是将高16...

    六月的雨
  • 每天学习一点儿算法--散列表

    在之前我们已经学过了二分查找和简单查找,我们知道二分查找的运行时间为O(㏒ n), 简单查找的运行时间为O(n)。除此之外,还有没有更快的查找算法呢? 可能有人...

    爱吃西瓜的番茄酱
  • 《图解算法》第5章 散列表

    yeedomliu
  • 1.列表的定义及增删改查

    见贤思齊

扫码关注云+社区

领取腾讯云代金券