【从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. 缓存