背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

查找迅速的哈希表

如果数组是有序的，那么计算机就可以使用二分查找，这只需要O(log N)步。

O(log N)已经很不错了，但我们还能做得更好。事实上，可以好很多。学习本章之后，你就能使用名为哈希表的特殊数据结构了，它可以在O(1)时间内查找数据。在学习哈希表的工作原理和适用场景后，你可以在许多地方发挥它的速度优势。

哈希表

大多数编程语言有一个名叫哈希表的数据结构。它有一个强大特性：快速读取。哈希表在不同编程语言中的名字可能不同。Hash、Map、Hash Map、Dictionary和Associate Array指的都是哈希表。

下面是Ruby中快餐店菜单的哈希表实现：

menu = { "french fries" => 0.75, "hamburger" => 2.5,
"hot dog" => 1.5, "soda" => 0.6 }

哈希表由一组成对的数组成。每对数的第一个元素称作键，第二个元素称作值。在哈希表中，键和值之间有着明显的关联。在本例中，字符串"french fries"就是一个键，而0.75是其对应的值。它们组合在一起，表示炸薯条的价格是75美分。

在Ruby中可以使用以下语句来查找一个键的值：

menu["french fries"]

该语句会返回值0.75。因为通常只需要1步，所以在哈希表中查找值的平均复杂度是O(1)。

用哈希函数进行哈希

这个把字母转换为数字的过程称为哈希。用来把字母转换成特定数字的密码就是哈希函数。

把字母转换成对应数字再求和也是一种哈希函数。

有效的哈希函数只需满足一个条件：对同样的字符串使用哈希函数得到的值应该永远相同。如果不能满足这个条件，那么哈希函数就是无效的。如果一个哈希函数在计算过程中使用了随机数或者当前时间，那么它就是无效的。

哈希表查找

在哈希表中查找时，我们使用键来寻找和它关联的值。下面会以Quickasaurus中的哈希表为例来展示这一过程。

假设要查找和键"bad"关联的值。这一操作可以用如下代码完成：

thesaurus["bad"]

要找到和"bad"关联的值，计算机只需执行简单的两步。

(1) 计算查找的键的哈希值：BAD = 2 × 1 × 4 = 8。

(2) 因为结果是8，所以计算机会检查第8个格子并返回其中的值——"evil"。

宏观来看，哈希表中每个值的位置是由键决定的。对键进行哈希，就得到了存储该键关联值的索引。

因为键决定了值的位置，所以查找简直是“小菜一碟”。如果想查找一个键对应的值，那么这个键本身就已经告诉了我们值的所在位置。就和插入时计算键的哈希值一样，只需再次计算哈希值，即可找到之前存储这个值的位置。

这下能明白查找哈希表为什么是O(1)了吧：这个过程只需要固定时间。计算机只需调用哈希函数，计算键的哈希值，然后跳转到对应索引并读取值即可。

创造高效的哈希表

哈希表的效率取决于3个因素。

• 哈希表中存储的数据量。
• 哈希表中格子的数量。
• 哈希表使用的哈希函数。

前两个因素的重要性显而易见。假如你有很多数据，却只有几个格子，那么就会产生很多冲突，让哈希表不再高效。但为什么哈希函数也会影响哈希表的效率呢？下面来看一下。

假设我们使用的哈希函数的哈希值总是在1和9之间。以下面这个哈希函数为例：该哈希函数会先把字母转换为数字，然后计算数字的和。如果和有不止一位数字，则会继续求它各位数字的和。重复此过程，直到结果为一位数字。

下面用一个例子来描述这个哈希过程。

PUT = 16 + 21 + 20 = 57

因为57有两位数字，所以哈希函数会把它分为5 + 7。

5 + 7 = 12因为12还是有两位数字，所以哈希函数会把它分为1 + 2。

1 + 2 = 3

因此PUT的哈希值是3。

根据定义，该哈希函数的哈希值永远是1和9之间的数。

好的哈希函数需要将数据分布在所有可用格子中。数据分布越广，就越不容易冲突。

用哈希表优化速度

哈希表还可以用来给代码提速，即便数据不成对也可以。

下面是一个简单数组：

array = [61, 30, 91, 11, 54, 38, 72]

假如你要查找数组中的一个数，那么需要多少步呢？

因为数组是无序的，所以必须进行线性查找，这需要N步。本书开头就介绍过这一点。

不过，假如用一段代码把这些数存储到哈希表中呢？

hash_table = {61 => true, 30 => true, 91 => true,
11 => true, 54 => true, 38 => true, 72 => true}

这里把数本身作为键，把布尔值true作为关联的值。

如果在这个哈希表中搜索作为键的特定值，那么需要多少步呢？

答案是使用下面这行简单的代码：

hash_table[72]

只要1步就能找到72。

换言之，用72作为键进行哈希表查找，只需要1步就能确定72是否在哈希表中。原因很简单：如果72确实是表中的一个键，那么因为72对应的值是true，所以代码会返回true。反之，如果72不是表中的键，则代码会返回nil。

因为哈希表查找只需要1步，所以在哈希表中查找任意数（作为键）都只要1步。

像这样把数组转化成哈希表，就可以把查找从O(N)变为O(1)。

总结

在构建高效的软件时，哈希表不可或缺。因为读取和插入的复杂度都是O(1)，所以这是一种很难超越的数据结构。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。