算法图解(五)|散列表与字典

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

例如我们去商店买东西,如果售货员是通过本子记录价格,即使记录是有序的,可以进行二分查找,在查找价格时,都能感觉到顾客的怒气。因此我们更希望售货员可以记住每样商品的价格,我们将商品拿给他,他立马就能报出价格,付款之后很快就可以离开。

这种复杂度为O(1)的算法结构如何实现呢?

散列表

算法图解第五章内容学习笔记

5.1 散列函数

特点:无论输入是什么数据,散列函数都输出一个数字。用专业术语来说明,散列函数“将输入映射到数字”。

散列函数将输入映射为数字,这有何用途呢?

这可以构建一个记住所有商品价格的售货员。你给他一个商品名字,他能立即报给你商品的价格。我们来根据散列函数来构建散列表。

一句话解释:商品价格存储在一个列表中,将商品名字输入散列函数,函数输出该商品存储在列表中的序号,根据序号读取商品价格。

首先创建一个空数组

在这个数组中存储商品的价格。下面来将苹果的价格加入到这个数组中。为此,将apple作为输入交给散列函数。

散列函数的输出为3,因此我们将苹果的价格存储到数组的索引3处。

下面将牛奶(milk)的价格存储到数组中。为此,将milk作为散列函数的输入。

散列函数的输出为0,我们便将牛奶的价格存储在索引0处。

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

现在假设需要知道鳄梨(avocado)的价格。你无需在数组中查找,只需将avocado作为输入

交给散列函数。

它将告诉你鳄梨的价格存储在索引4处。果然,你在那里找到了。

函数特点:

(1)散列函数总是将同样的输入映射到相同的结果。

(2)散列函数将不同的输入映射到不同的索引。

(3)散列函数知道数组有多大,只返回有效的索引,不会超出索引。

实现:

不用考虑实现,在任意的一门语言中都有散列表的实现,我们仅需要直接使用就好,例如散列表在python中的实现成为字典,下面是一个字典的使用例子。

5.2 应用案例

(1) 将散列表用于查找

电话号码查找,给一个名字,输出他的号码。

(2)防止重复(投票时防止重复投票)

(3)将散列表用作缓存

5.3 冲突

上面的叙述中,我们说到,散列函数总是将不同的键映射到数组的不同位置。实际上,几乎不可能编写出这样的散列函数。

例如我们存储商品单价,若采用按字母表顺序分配数组的位置的散列函数。如下图:

如果你要将苹果apple的价格存储到散列表中,分配给你的是第一个位置。后来再遇到存储鳄梨的价格时,又是以A开头,按理说应该分配第一个位置给它。但是这里,第一个位置已经存储了苹果的价格了,这就引发了“冲突”

解决方法:

如果两个键映射到了同一个位置,就在这个位置存储一个链表

但如果,所有的商品都以A开头,如下图,这就是散列表最糟糕的情况。这时速度会很慢,因此需要避免这种情况。

经验:

(1)散列函数很重要。最理想的情况是,散列函数将键均匀地映射到散列表的不同位置。最糟糕的情况是将所有的键都映射到一个位置;

(2)如果散列表存储的链表很长,散列表的速度将急剧下降。然而,如果使用的散列函数很好,这些链表就不会很长!

5.4 性能

散列表的性能常数级别复杂度:

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

(1)较低的填装因子;

(2)良好的散列函数。

5.4.1 填装因子

	装填因子 = 散列表包含的元素数目/位置总数

填装因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。

调整散列表的长度:首先创建一个更长的新数组,通常将数组增长一倍,再使用函数hash将所有的元素都插入到这个新的散列表中。

调整散列表长度的工作需要很长时间!但平均而言,即便考虑到调整长度所需的时间,散列表操作所需的时间也为O(1)。

5.4.2 良好的散列函数

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

糟糕的散列函数让值扎堆,导致大量的冲突。

总结:

(1)散列表是一种功能强大的数据结构,其操作速度快,还能让你以不同的方式建立数据模型。

(2)散列表的查找、插入和删除速度都非常快。

(3)一旦填装因子超过0.7,就该调整散列表的长度。

(4)使用可以最大限度减少冲突的散列函数避免冲突。

(5)散列表适合用于模拟映射关系,可用于缓存数据、防止重复。

《算法图解》第五章散列表(字典)学习笔记,下一章“广度优先搜索”

原文发布于微信公众号 - AI深度学习求索(AIDeepLearningQ)

原文发表时间:2018-12-05

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏西枫里博客

PHP对数组进行排序操作

昨天别人问了我一个问题,瞬间把我给问懵了。事情是这样的,问我给到一个既定数组,现在让我实现下将数组元素从低到高升序排列。第一个反应是直接使用ksort之类排序函...

7610
来自专栏IT可乐

深入理解计算机系统(2.1)------信息的存储和表示

  前面我们介绍了《深入理解计算机系统》第一章的内容----计算机系统漫游。包括简单介绍了 Hello World 程序在计算机中是如何运行的,存储设备的层次结...

24880
来自专栏行者悟空

我眼中的并发编程——Fork/Join模型

22050
来自专栏杨建荣的学习笔记

实用的位运算应用(r4笔记第97天)

对于位运算,之前在一篇博文中分享了一下在c语言和oracle中的位运算实现 http://blog.itpub.net/23718752/viewspace-1...

29350
来自专栏拭心的安卓进阶之路

重温数据结构:哈希 哈希函数 哈希表

在学习 HashMap 前,我们先来温习下 Hash(哈希) 的概念。 什么是 Hash Hash(哈希),又称“散列”。 散列(hash)英文原意是“混杂”...

31550
来自专栏CDA数据分析师

10个应该早点知道的Python技巧

我的这一生都在编程,但是我没有成为一名程序员。最初,我的大部分工作都是用Visual Basic来完成的,还包括一些其它语言工具,比如R语言,C语言、JavaS...

31490
来自专栏Linyb极客之路

UML类图(下):关联、聚合、组合、依赖

关联(Assocition)关系是类与类之间最常见的一种关系,它是一种结构化的关系,表示一类对象与另一类对象之间有联系,如汽车和轮胎、师傅和徒弟、班级和学生等。...

17120
来自专栏liulun

Nim教程【五】

这是国内第一个关于Nim的系列教程 先说废话 业内的人认为能够直接操作系统硬件的语言才称得上系统级的编程语言 常见的系统级编程语言有:汇编、C、C++、D、GO...

32380
来自专栏青玉伏案

代码重构(四):条件表达式重构规则

继续更新有关重构的博客,前三篇是关于类、函数和数据的重构的博客,内容还算比较充实吧。今天继续更新,本篇博客的主题是关于条件表达式的重构规则。有时候在实现比较复杂...

21090
来自专栏云飞学编程

python学习,数据分析系列工具,初识numpy

其实,数据分析看着很高大上,也很实用,但是真的很枯燥啊。。。。但是它又不得不学,毕竟数据分析对很多工作是很有帮助的,比如爬虫,抓到的数据,不论是保存到文件还是数...

9520

扫码关注云+社区

领取腾讯云代金券