作为一名程序员，您每天都会使用哈希函数。它们在数据库中用于优化查询，在数据结构中用于使速度更快，在安全性中用于保证数据安全。几乎每次与技术的交互都会以某种方式涉及哈希函数。
哈希函数是基础函数，而且无处不在。
但什么是哈希函数，它们如何工作？
在这篇文章中，我们将揭开哈希函数的神秘面纱。我们将从查看一个简单的哈希函数开始，然后我们将学习如何测试哈希函数是否好用，然后我们将查看哈希函数的实际使用: 哈希映射。
这篇文章有可视化效果，可以点击。
# 什么是哈希函数？
哈希函数是接受输入（通常是字符串）并生成数字的函数。如果您使用相同的输入多次调用哈希函数，它将始终返回相同的数字，并且返回的数字始终在承诺的范围内。该范围取决于哈希函数，有些使用 32 位整数（即 0 到 40 亿），有些则更大。
如果我们用 JavaScript 编写一个虚拟哈希函数，它可能如下所示：
function hash(input) {
return 0;
}
即使不知道哈希函数是如何使用的，这个哈希函数毫无用处也不足为奇。让我们看看如何衡量哈希函数的好坏，然后我们将深入探讨如何在哈希映射中使用它们。
# 哈希函数的优点是什么？
因为input可以是任何字符串，但返回的数字在某个承诺的范围内，所以两个不同的输入有可能返回相同的数字。这称为“冲突”，好的哈希函数会尝试尽量减少它们产生的冲突数量。
但完全消除碰撞是不可能的。如果我们编写一个返回 0 到 7 范围内的数字的哈希函数，并为其提供 9 个唯一输入，则可以保证至少发生 1 次冲突。
hash("to") == 3hash("the") == 2hash("café") == 0hash("de") == 6hash("versailles") == 4hash("for") == 5hash("coffee") == 0hash("we") == 7hash("had") == 1来自著名哈希函数的输出值，模 8。无论我们传递什么 9 个值，都只有 8 个唯一数字，因此冲突是不可避免的。目标是尽可能少。
为了可视化碰撞，我将使用网格。网格的每个方块将代表哈希函数输出的数字。这是一个 8x2 网格的示例。单击网格以增加示例哈希输出值，并查看我们如何将其映射到网格方块。看看当你得到的数字大于网格方块的数量时会发生什么。
13 % 16 == 13每次我们对一个值进行哈希处理时，我们都会使其网格上相应的方块变暗一点。这个想法是创建一种简单的方法来查看哈希函数如何避免冲突。我们正在寻找的是一个良好、均匀的分布。如果我们有深色方块的团块或图案，我们就会知道哈希函数不好。
您说过，当哈希函数为两个不同的输入输出相同的值时，那就是冲突。但是，如果我们有一个输出大范围值的哈希函数，并将它们映射到一个小网格，那么我们是否会在网格上创建大量实际上不是碰撞的碰撞？在我们的 8x2 网格上，1 和 17 都映射到第二个正方形。
这是一个很好的观察。你说得完全正确，我们将在网格上创建“伪碰撞”。不过没关系，因为如果哈希函数很好，我们仍然会看到均匀分布。每个平方增加 100 与每个平方增加 1 一样都是好的分布。如果我们有一个经常发生冲突的糟糕哈希函数，那仍然会很突出。我们很快就会看到这一点。
让我们采用一个更大的网格并对 1,000 个随机生成的字符串进行哈希处理。您可以 单击网格来对一组新的随机输入进行散列，网格将以动画方式向您显示每个输入被散列并放置在网格上。
这些值很好并且分布均匀，因为我们使用了一个很好的、众所周知的哈希函数，称为murmur3。这种哈希在现实世界中被广泛使用，因为它具有很好的分布性，同时也非常非常快。
如果我们使用了错误的哈希函数，我们的网格会是什么样子？
function hash(input) {
let hash = 0;
for (let c of input) {
hash += c.charCodeAt(0);
}
return hash % 1000000;
}
该哈希函数循环遍历给定的字符串并对每个字符的数值求和。然后，它使用模运算符 ( ) 确保该值介于 0 和 1000000 之间%。我们称这个哈希函数为 stringSum。
这是在网格上。提醒一下，这是我们正在散列的 1,000 个随机生成的字符串。
这看起来与 并没有什么不同murmur3。是什么赋予了？
问题是我们要进行哈希处理的字符串是随机的。让我们看看当给定的输入不是随机的时每个函数如何执行：从 1 到 1000 的数字转换为字符串。
现在问题更加清楚了。当输入不是随机的时， 的输出stringSum形成一种模式。然而，我们的murmur3网格看起来与随机值的网格相同。
它更微妙，但我们确实在stringSum网格上看到了一种模式。和往常一样，murmur3 看起来和往常一样。
这就是一个好的哈希函数的力量：无论输入如何，输出都是均匀分布的。让我们讨论另一种可视化这一点的方法，然后讨论它的重要性。
# 雪崩效应
评估哈希函数的另一种方法是基于所谓的“雪崩效应”。这是指当输入的一位发生变化时，输出值中的多少位发生变化。要说哈希函数具有良好的雪崩效应，输入中的单个位翻转应该会导致输出位平均翻转 50%。
正是这个属性帮助哈希函数避免在网格中形成模式。如果输入的微小变化导致输出的微小变化，您就会得到模式。模式表明分布不良且冲突率较高。
下面，我们通过显示两个 8 位二进制数来可视化雪崩效应。上面的数字是输入值，下面的数字是murmur3输出值。单击它可翻转 输入中的一位。输出中发生变化的位将显示为绿色，保持不变的位将显示为红色。
murmur3表现不错，但您会注意到有时翻转的位少于 50%，有时翻转的位更多。没关系，只要平均是 50% 就可以了。
让我们看看stringSum 的表现如何。
嗯，这很尴尬。输出等于输入，因此每次只有一位翻转。这确实有意义，因为stringSum只是对字符串中每个字符的数值进行求和。此示例仅对单个字符的等效值进行哈希处理，这意味着输出将始终与输入相同。
# 为什么这一切都很重要
我们已经花时间了解了一些确定哈希函数是否良好的方法，但我们没有花时间讨论它的重要性。让我们通过讨论哈希图来解决这个问题。
要理解哈希映射，我们首先必须了解映射是什么。映射是一种允许您存储键值对的数据结构。这是一个 JavaScript 示例：
let map = new Map();
map.set("hello", "world");
console.log(map.get("hello"));
这里我们采用一个键值对（"hello"→ "world"）并将其存储在映射中。然后我们打印出与该键关联的值"hello"，即 "world"。
一个更有趣的现实用例是查找字谜词。字谜词是指两个不同的单词包含相同的字母，例如“antlers”和“rentals”或“article”和“recital”。如果您有一个单词列表并且想要查找所有字谜词，您可以按字母顺序对每个单词中的字母进行排序，并将其用作映射中的键。
let words = [
"antlers",
"rentals",
"sternal",
"article",
"recital",
"flamboyant",
]
let map = new Map();
for (let word of words) {
let key = word
.split('')
.sort()
.join('');
if (!map.has(key)) {
map.set(key, []);
}
map.get(key).push(word);
}
此代码生成具有以下结构的映射：
{
"aelnrst": [
"antlers",
"rentals",
"sternal"
],
"aceilrt": [
"article",
"recital"
],
"aabflmnoty": [
"flamboyant"
]
}
# 实现我们自己的简单哈希图
哈希映射是众多映射实现中的一种，实现哈希映射的方法有很多种。最简单的方法，也是我们将要演示的方法，是使用列表的列表。内部列表在现实世界中通常被称为“桶”，因此我们在这里也这么称呼它们。对键使用哈希函数来确定将键值对存储在哪个桶中，然后将键值对添加到该桶中。
让我们看一下 JavaScript 中的简单哈希映射实现。我们将自下而上地进行讨论，因此在讨论set和get实现之前我们将看到一些实用方法。
class HashMap {
constructor() {
this.bs = [[], [], []];
}
}
我们首先创建一个HashMap带有设置 3 个存储桶的构造函数的类。我们使用 3 个存储桶和短变量名称，bs以便此代码可以在屏幕较小的设备上很好地显示。实际上，您可以拥有任意数量的存储桶（以及更好的变量名称）。
class HashMap {
// ...
bucket(key) {
let h = murmur3(key);
return this.bs[
h % this.bs.length
];
}
}
该bucket方法使用传入的murmur3值key 来查找要使用的存储桶。这是我们的哈希映射代码中唯一使用哈希函数的地方。
class HashMap {
// ...
entry(bucket, key) {
for (let e of bucket) {
if (e.key === key) {
return e;
}
}
return null;
}
}
该entry方法采用 abucket和 akey并扫描存储桶，直到找到具有给定键的条目。如果没有找到条目，null则返回。
class HashMap {
// ...
set(key, value) {
let b = this.bucket(key);
let e = this.entry(b, key);
if (e) {
e.value = value;
return;
}
b.push({ key, value });
}
}
该set方法是我们应该从之前的 JavaScript 示例中认识到的第一个方法Map。它需要一个键值对并将其存储在我们的哈希映射中。它通过使用我们之前创建的bucket和entry方法来实现这一点。如果找到条目，则其值将被覆盖。如果未找到条目，则将键值对添加到映射中。在 JavaScript 中，{ key, value }是 的简写{ key: key, value: value }。
class HashMap {
// ...
get(key) {
let b = this.bucket(key);
let e = this.entry(b, key);
if (e) {
return e.value;
}
return null;
}
}
该get方法与 非常相似set。它使用bucket和entry来查找与传入的条目相关的条目key，就像这样set做一样。如果找到条目，value则将其返回。如果没有找到，null则返回。
这是相当多的代码。您应该从中了解的是，我们的哈希映射是一个列表列表，并且哈希函数用于知道要从哪个列表中存储和检索给定的键。
这是该哈希图的实际操作的直观表示。单击存储桶上的任意位置，使用我们的方法添加新的键值对 set。为了保持可视化简单，如果一个存储桶“溢出”，则所有存储桶都将被重置。
因为我们使用murmur3哈希函数，所以您应该看到存储桶之间的良好分布。预计您会看到一些不平衡，但通常应该相当均匀。
为了从哈希映射中获取值，我们首先对键进行哈希计算，以确定该值将位于哪个存储桶中。然后，我们必须将要搜索的键与存储桶中的所有键进行比较。
我们通过散列最小化了这个搜索步骤，这也是为什么murmur3要优化速度的原因。哈希函数越快，我们找到合适的存储桶进行搜索的速度就越快，哈希映射的整体速度就越快。
这也是为什么减少碰撞如此重要的原因。如果我们确实决定使用本文开头始终返回 0 的虚拟哈希函数，我们会将所有键值对放入第一个存储桶中。找到任何东西可能意味着我们必须检查哈希映射中的所有值。有了好的散列函数和良好的分布，我们就可以将搜索量减少到 1/N，其中 N 是桶的数量。
让我们看看stringSum效果如何。
有趣的是，stringSum似乎很好地分配了价值。您会注意到一种模式，但整体分布看起来不错。
最后！一场胜利
stringSum。我知道这会对某些事情有好处。
没那么快，哈斯基。我们需要讨论一个严重的问题。这些连续数字的分布看起来不错，但我们已经看到它stringSum没有良好的雪崩效应。这结局并不好。
# 真实世界的碰撞
让我们看一下 2 个现实世界的数据集：IP 地址和英语单词。我要做的就是获取 100,000,000 个随机 IP 地址和466,550 个英语单词murmur3，用 和 来对它们进行哈希处理stringSum，然后看看我们得到了多少次冲突。
IP地址
murmur3 |
stringSum |
|
|---|---|---|
| 碰撞 | 1,156,959 | 99,999,566 |
| 1.157% | 99.999% |
英语单词
murmur3 |
stringSum |
|
|---|---|---|
| 碰撞 | 25 | 464,220 |
| 0.005% | 99.5% |
当我们真正使用哈希映射时，我们通常不会在其中存储随机值。我们可以想象计算我们在服务器的速率限制代码中看到某个 IP 地址的次数。或者通过代码计算历史上书籍中单词的出现次数，以跟踪它们的起源和受欢迎程度。stringSum对于这些应用来说很糟糕，因为它的碰撞率极高。
# 制造碰撞
现在轮到murmur3一些坏消息了。我们需要担心的不仅仅是输入相似性引起的冲突。看一下这个。
这里发生了什么事？为什么所有这些乱码字符串都会散列到相同的数字？
我对 141 万亿个随机字符串进行哈希处理，以找到 1228476406使用murmur3. 哈希函数必须始终为特定输入返回相同的输出，因此可以通过强力查找冲突。
抱歉，141万亿？就像... 141 然后 12 个零？
是的，我只花了 25 分钟。计算机速度很快。
如果您的软件根据用户输入构建哈希映射，那么很容易发生冲突的坏人可能会造成毁灭性的后果。以 HTTP 标头为例。HTTP 请求如下所示：
GET / HTTP/1.1
Accept: */*
Accept-Encoding: gzip, deflate
Connection: keep-alive
Host: google.com
您不必理解所有单词，只需了解第一行是所请求的路径，所有其他行都是标头即可。标头是Key: Value成对的，因此 HTTP 服务器倾向于使用映射来存储它们。没有什么可以阻止我们传递我们想要的任何标头，因此我们可以非常刻薄地传递我们知道会导致冲突的标头。这会显着降低服务器速度。
这也不是理论上的。如果您搜索“HashDoS”，您会发现更多这样的示例。这在 2000 年代中期确实是一件大事。
有几种方法可以缓解 HTTP 服务器特有的这种情况：例如，忽略乱七八糟的标头键并限制您存储的标头数量。但现代哈希函数murmur3 提供了一种更通用的解决方案：随机化。
在本文前面，我们展示了一些哈希函数实现的示例。这些实现采用一个参数：input。许多现代哈希函数都采用第二个参数：（seed有时称为salt）。在 的情况下murmur3，该种子是一个数字。
到目前为止，我们一直使用 0 作为种子。让我们看看当我们使用种子 1 时我收集到的碰撞会发生什么。
就这样，0比1，碰撞就消失了。这就是种子的目的：它以不可预测的方式随机化哈希函数的输出。它如何实现这一点超出了本文的范围，所有哈希函数都以自己的方式实现这一点。
对于相同的输入，哈希函数仍然返回相同的输出，只是输入是input和的组合seed。与一颗种子发生碰撞的物体在使用另一颗种子时不应发生碰撞。编程语言通常会在进程启动时生成一个随机数用作种子，因此每次运行程序时种子都是不同的。作为一个不知道种子的坏人，我现在不可能可靠地造成伤害。
如果您仔细观察上面的可视化和之前的可视化，您会发现它们是被散列的相同值，但它们产生不同的散列值。这意味着，如果您使用一个种子散列一个值，并且希望将来能够与它进行比较，则需要确保使用相同的种子。
不同种子具有不同的值不会影响哈希映射用例，因为哈希映射仅在程序运行期间有效。如果您在程序的生命周期中使用相同的种子，您的哈希映射将继续正常工作。如果您曾经将哈希值存储在程序之外（例如文件中），则需要小心了解使用的种子。
# 游乐场
按照传统，我为您创建了一个游乐场，供您编写自己的哈希函数，并使用本文中看到的网格将它们可视化。点击 这里尝试一下！
# 结论
我们已经介绍了哈希函数是什么、衡量它好坏的一些方法、它不好时会发生什么，以及它们可能被坏人破坏的一些方法。
哈希函数的范围很广，在这篇文章中我们实际上只触及了表面。我们还没有讨论加密与非加密散列，我们只触及了散列函数的数千个用例中的一个，并且我们还没有讨论现代散列函数实际上是如何工作的。
如果您真的对这个主题感兴趣并且想了解更多信息，我建议您进一步阅读：
- https://github.com/rurban/smhasher该存储库是测试哈希函数性能的黄金标准。他们对大量哈希函数运行大量测试，并将结果呈现在一个大表中。很难理解所有测试的目的，但这就是哈希测试的最先进技术。
- https://djhworld.github.io/hyperloglog/这是关于名为 HyperLogLog 的数据结构的交互式文章。它用于有效地计算非常非常大的集合中唯一元素的数量。它使用散列以一种非常聪明的方式来做到这一点。
- https://www.gnu.org/software/gperf/是一个软件，当给定您想要散列的预期内容时，它可以自动生成“完美”散列函数。
来自 https://samwho.dev/hashing/
