你从未见过的 Hashmap

伪装成对象或集合的哈希图

一种极其高效的读写方式

哈希。关于“哈希”函数

计算字符数

免费性能增益

输入越大，性能越好

保持好奇心

我写了一本电子书来帮助你

说到哈希表 (HashMap)，你每天都在使用它们，但你可能并不清楚它的工作原理，也不知道为什么偏爱它。为什么我说它是最好的呢？因为它不仅是你在任何编程面试中的灵丹妙药，还能在日常代码编写中免费提升性能。

伪装成对象或集合的哈希图

打开你上一个项目，几乎可以肯定你到处都在用哈希表 (hashmap)。如果你写的是 JavaScript，它们就是普通的对象{ name: 'carlos' }（严格来说，参见最后一节）。Java 使用HashMap对象，Python 称之为字典，Go 有映射 (map)。为了便于说明，我们来看一个 TypeScript 的例子。

const ages: Record<string, number> = {
  carlos: 28,
  leena: 34,
  luigy: 14,
  maria: 54
};

那么，您熟悉这个概念 - 您知道它是什么样子的，但是，它是什么？

一种极其高效的读写方式

哈希表 (Hashmap) 是一种数据结构（即用于管理数据的一段代码），它在内存中存储和检索数据方面极其高效。可以将其想象成一个包含键值对 (pair) 的表。“键”用于标识“值”。在上一节中，键分别为“carlos”、“leena”、“luigy”和“maria”；值分别为 28、34、14 和 54。

哈希。关于“哈希”函数

hashmap 是一个强化版的数组。区别在于，你不是用数字索引来访问数组，而是用对象。这是怎么回事？如果没有索引，如何指向数组中的某个元素？

很简单：如果您没有数组索引，则需要一种从对象中获取它的方法。

火焰就是魔法。这种魔法被称为哈希函数。它是一种将某些对象（字符串、数字、对象）转换为数组中某个位置的方法。每种编程语言都有其独特的哈希函数实现方法。哈希表的效率可能非常低下，也可能非常快，这取决于其哈希函数。

什么是 糟糕的那么哈希函数是什么样的呢？

几周前，我把这篇文章发给了我邮件列表中的 700 多位开发者。欢迎加入这里，获取我关于算法和职业发展的技巧和想法。如果您不习惯使用电子邮件，可以关注我的Twitter ，提前了解我的工作进展。

计算字符数

让我们实现一个糟糕的哈希函数，它只适用于字符串类型的键。它会将键映射到一个长度为 10 的数组。我们的哈希函数工作原理如下：

我们的哈希函数 h(x)：将字符串中的每个字符转换x为其在字母表中的数字位置。将所有这些数字相加。除以 10，然后取其余数（即模数%）。

听起来很复杂，最好举个例子：

• h('abc') = (1+2+3) % 10 = 6 % 10 = 6
• h('carlos') = (3+1+18+12+15+19) % 10 = 68 % 10 = 8

这意味着 map{ carlos: 28 }会将值存储28在其底层数组的位置8。以下是哈希函数概念的更直观的表示。

免费性能增益

至此，你已经对这个概念深信不疑了。你明白了它为什么这么快，以及它的内部工作原理。但是，你为什么要关心它呢？你该如何在现实生活中应用这个概念呢？

让我们来研究一个你在日常工作中可能经常遇到的算法：找出单词列表中最常见的元素。例如，列表中[4,1,3,4]最常见的元素是“4”。解决这个问题的方法有很多，但这里我们只关注其中的两种：

1. 对于每个元素，找出其所有重复项。返回重复项最多的元素。
2. 计算每个元素的出现次数。选择出现次数最多的元素。

第一种方法需要嵌套循环（对每个元素进行i循环，遍历所有其他元素j以搜索此项）；第二种方法只需要一个哈希表。让我们看看它们在操作方面有何不同。

如果你不明白为什么 21 和 9 运算，请思考一下：

1. 在第一种方法中，你访问第一个元素“carlos”，然后访问其余元素以查找类似的元素。总共访问了 6 次。然后，你访问第二个元素“edgar”，并遍历剩余的 4 个元素。总共访问了 5 次。继续执行此操作，直到只剩下 1 个元素，将所有访问次数相加，总共需要 21 次操作。

2. 在第二种方法中，你访问第一个元素“carlos”，并将其保存在哈希表中，值为 1。每当你找到另一个“carlos”，你就会在哈希表中增加它的值。也就是说，你只需要遍历每个元素一次，总共访问 6 次。哈希表最终包含 3 个元素，因此你需要遍历每个元素，找出哪个出现的次数最多（最大值）。总共需要 9 次操作。

输入越大，性能越好

你可能会想：“这个例子太蠢了，只是为了说明你的观点，21 和 9 对我的 CPU 来说根本算不了什么。” 让我们看看当你有一个包含 10、20、30、……、100 个元素的数组时会发生什么。

如您所见，我们的算法在使用哈希表时的性能比使用嵌套循环时要好得多。评判算法的优劣，应该看其在输入趋近于无穷大时的性能。事实上，第一种方法的运行时间是二次方的，O(n^2)而使用哈希表的方法则是线性的O(n)。这就是BigO 符号。

知识就是力量。现在，你又多了一分力量，可以使用 Hashmap 来提升代码效率！

保持好奇心

这只是我个人认为非常有用且有趣的数据结构的介绍（实际上，这是你能学到的最好的数据结构）。话虽如此，这只是一个庞大主题的冰山一角。处理哈希图时会涉及到很多复杂性。如果你对此感兴趣，我邀请你继续研究以下主题：

• 冲突处理：'carlos' 和 'mike' 都映射到同一个数组索引8。然后会发生什么？如果元素的哈希值与另一个键冲突，该如何检索？
• 负载因子：当列表已满时会发生什么？例如，列表元素数量应从 10 个增加到 20 个，它如何决定何时执行此操作？
• JavaScript 可能没有使用 Hashmap 来存储对象。那么，它是如何做到的呢？
• 为了满足您的好奇心，请观看 Google 如何构建超快速且高效的 Hashmap。

如果你从这篇文章中有所收获，或者学到了新东西，请在Twitter上告诉我。写代码时要多加注意，考虑性能和底层机制。Hashmap 也能帮助你在职业生涯中顺利通过很多面试，我就是这么过来的。

我写了一本电子书来帮助你

我的使命是通过发布简历写作技巧、教授算法或分享我在顶级远程工作场所的工作经验来帮助开发者成长。我写了一本电子书，帮助你在Toptal找到工作。如果你对此感兴趣，请在此注册，并在下一封电子邮件中收到。