算法图解（五）｜散列表与字典

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

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

这种复杂度为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）散列表适合用于模拟映射关系，可用于缓存数据、防止重复。

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