散列表 - Hash Table

「总结自《Grokking Algotithms》这本书第五章内容」

散列函数

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

散列函数必须满足以下条件:

  • 必须是一致的。即对于同样的输出数据,都返回相同的结果。比如,每次输入 apple,返回结果都是 4。
  • 应将不同的输入映射到不同的输出。如果一个散列表无论对于什么输入,返回的结果都是 1,那它就不是一个好的散列表。一个好的散列表应该对于不同的输入映射到不同的数字。

散列表

散列函数表示了一种映射关系。可以用这种映射关系来建立一个商品价格存储的表。而存储这种映射记录的表就是散列表。散列表由键和值组成。例如,在建立的商品价格列表中,键就是商品名,值就是商品对应的价格。在Python 中,使用字典(dict)就可以建立一个散列表:

>>> food = dict()
>>> food["apple"]=0.67
>>> food["milk"]=2.18
>>> food["tea"]=24.4
>>> food
{'apple': 0.67, 'milk': 2.18, 'tea': 24.4}


>>> food['apple']
0.67
>>> food['milk']
2.18
>>> food['tea']
24.4

散列表可以用于很多地方。比如,用于电话簿的查找;用于浏览器缓存;还能用于防止重复。

冲突

前面提到散列函数,应该将不同的输入映射到不同的输出。但实际上,这很难做到。有时候会发生冲突,即:给两个键分配同一个位置。这就引起了问题,后面保存的值会将之前的值给覆盖掉,使之前的键,不能对应正确的值。

产生冲突了有解决办法吗?当然有,最简单的方法如下:如果两个键映射到了同一个位置,就在这个位置存储一个链表。但是这种解决方法存在弊端。如果该位置上的链表很长,则查找的时间就会很长。而除这个位置外,散列表其他位置的查找时间则依然很快。如果将所有的键都对应到一个值的位置上,该值的位置上用一个链表来连接所有的值。那么就和一开始就将所有的值都存储在链表中一样,查找的速度会很慢。

这里可以看出,如何设计散列函数是很重要的。最理想的状态是,将所有的键都均匀地映射到散列表的不同位置上。而且,如果散列函数设置好的话,链表就不会很长而导致速度很慢。

性能

在平均情况下,散列表执行各种操作的时间都为 O(1),即为常量时间。常量时间不并不意味着马上,而是说不管散列表有多大,所需的时间都相同。而在最糟的情况下,散列表执行各种操作的时间都为 O(n),即为线性时间。下面是散列表和数组,链表的对比:

数组

链表

散列表(平均情况)

散列表(最糟情况)

插入

O(n)

O(1)

O(1)

O(n)

查找

O(1)

O(n)

O(1)

O(n)

删除

O(n)

O(1)

O(1)

O(n)

在平均情况下,散列表的查找速度与数组一样快,而插入和删除都与链表一样快,这相当于吸收了数组和链表两者的优点。但在最糟的情况下,是两者中的最差者,所有的操作都很慢。

所以,在使用散列表的时候,要避开最糟的情况。即,需要避开冲突。避开冲突有下面两种办法:

  • 降低填装因子
  • 使用良好的散列函数

填装因子

什么是填装因子呢?很简单,公式如下:

在散列表中,使用数组来存储数据。因此,需要计算数组中被占用的位置数。比如,一共有 10 个位置,而被元素占用的为 2 个,填装因子就为 2 / 10。最佳的情况是:10 个位置恰好被存在的 10 个元素占用,填装因子为 1。如果为 5 个位置的话,填装因子将为 2。即,散列表中的位置不够用,不可能让每个元素都有自己的位置。

所以,填装因子大于 1 意味着元素数量超过了数组的位置数量。一旦填装因子开始增大(经验表明大于 0.7 的时候),就需要在散列表中添加位置,即调整长度。这是一种非常麻烦的方法,一旦不够用就需要调整长度,开销很大,没人愿意频繁地做这种事。

良好的散列函数

上面的方法很麻烦,让我们来看看第二种方法。什么样的散列函数是良好的呢?良好的散列函数能够让数组中的值呈均匀分布,而糟糕的散列函数则会让值扎堆,导致大量的冲突。

现实生活中,有一个函数非常好用 - SHA 函数。感兴趣的可以深入研究一下。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 装饰器

    最近在重新在学习 Python 进阶的内容。整理一下关于装饰器(decorator)的一些知识。在解释装饰器前,先花一点时间总结一些关于函数的知识点。

    caoqi95
  • DeepSleepNet - 基于原始单通道 EEG 的自动睡眠阶段评分模型

    这篇论文是 2017 年在 IEEE 神经系统与康复工程学报上发布的一篇关于睡眠分阶的论文。这篇论文的主要贡献有:

    caoqi95
  • 基于 Retinex 的几种图像增强算法总结

    也是上上周布置的作业,主要是比较不同 Retinex 算法实现的结果。同样也是需要自己看论文并实现算法,这点应该是选这门课最大的优点了,也是硕士需要掌握的基本技...

    caoqi95
  • 每天学习一点儿算法--散列表

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

    爱吃西瓜的番茄酱
  • Python面试中8个必考问题

    1、下面这段代码的输出结果是什么?请解释。 ? 怎样修改extendList的定义能够产生以下预期的行为? 上面代码输出结果将是: ? 很多人都会误认为list...

    CDA数据分析师
  • 数据结构与算法笔记(二)

    由于它的内存空间非连续,因此查找某个元素时只能从头到尾遍历,时间复杂度为 O(n)。那么能不能提高链表的查找效率呢?

    WriteOnRead
  • Python列表基本操作

    列表是Python中一种比较常用的数据结构,掌握基本的列表操作命令是python学习的其中一步,下面就来简要介绍Python中列表的几个常用操作。

    深度学习与Python
  • python学习第六讲,python中的数据类型,列表,元祖,字典,之列表使用与介绍

    使用ipython进入shell, 可以建立列表变量,使用的时候, 列表变量.按下TAB键,则会出现对应方法. 如下:

    IBinary
  • Python代码的几条建议

    体会一下这Best这招,选择是使用map函数,它可以将内置函数类型str映射到迭代器range。这会生成一个map对象,然后就可以像其他示例一样join。在某些...

    刀刀老高
  • Python学习笔记五(列表和元组)

    最近这段时间是一年中最忙的时候,学习进度严重耽误,距离上一次更新Python的学习进度又已经一个月过去了,“佩服”我自己。趁着假期,继续学习我的Python,顺...

    世纪访客

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动