哈希函数如何工作 ?
作为一名程序员，您每天都会使用哈希函数。它们在数据库中用于优化查询，在数据结构中用于使速度更快，在安全性中用于保证数据安全。几乎每次与技术的交互都会以某种方式涉及哈希函数。
哈希函数是基础函数，而且无处不在。但什么是哈希函数，它们如何工作？
在这篇文章[1]中，我们将揭开哈希函数的神秘面纱。我们将从查看一个简单的哈希函数开始，然后我们将学习如何测试哈希函数是否好用，然后我们将查看哈希函数的实际使用：哈希映射。
什么是哈希函数？
哈希函数是接受输入（通常是字符串）并生成数字的函数。如果您使用相同的输入多次调用哈希函数，它将始终返回相同的数字，并且返回的数字始终在承诺的范围内。该范围取决于哈希函数，有些使用 32 位整数（即 0 到 40 亿），有些则更大。
如果我们用 JavaScript 编写一个虚拟哈希函数，它可能如下所示：
function hash(input) {
return 0;
}
即使不知道哈希函数是如何使用的，这个哈希函数毫无用处也不足为奇。让我们看看如何衡量哈希函数的好坏，然后我们将深入探讨如何在哈希映射中使用它们。
哈希函数的优点是什么？
由于输入可以是任何字符串，但返回的数字在某个承诺的范围内，因此两个不同的输入可能会返回相同的数字。这称为“冲突”，好的哈希函数会尝试尽量减少它们产生的冲突数量。
但完全消除碰撞是不可能的。如果我们编写一个返回 0 到 7 范围内的数字的哈希函数，并为其提供 9 个唯一输入，则可以保证至少发生 1 次冲突。
为了可视化碰撞，我将使用网格。网格的每个方块将代表哈希函数输出的数字。这是一个 8x2 网格的示例。单击网格以增加示例哈希输出值，并查看我们如何将其映射到网格方块。看看当你得到的数字大于网格方块的数量时会发生什么。
每次我们对一个值进行哈希处理时，我们都会使其网格上相应的方块变暗一点。这个想法是创建一种简单的方法来查看哈希函数如何避免冲突。我们正在寻找的是一个良好、均匀的分布。如果我们有深色方块的团块或图案，我们就会知道哈希函数不好。
这是一个很好的观察。你说得完全正确，我们将在网格上创建“伪碰撞”。不过没关系，因为如果哈希函数很好，我们仍然会看到均匀分布。每个平方增加 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 网格看起来与随机值的网格相同。
如果我们对前 1,000 个最常见的英语单词进行哈希处理，效果如何：
它更微妙，但我们确实在 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 来查找要使用的存储桶。这是我们的哈希映射代码中唯一使用哈希函数的地方。
class HashMap {
// ...
entry(bucket, key) {
for (let e of bucket) {
if (e.key === key) {
return e;
}
}
return null;
}
}
Entry 方法采用一个存储桶和一个键，并扫描该存储桶，直到找到具有给定键的条目。如果未找到条目，则返回 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 示例中认识到的第一个方法。它需要一个键值对并将其存储在我们的哈希映射中。它通过使用我们之前创建的存储桶和条目方法来实现这一点。如果找到条目，则其值将被覆盖。如果未找到条目，则将键值对添加到映射中。在 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相关的entry，就像set一样。如果找到条目，则返回其值。如果没有找到，则返回 null。
这是相当多的代码。您应该从中了解的是，我们的哈希映射是一个列表列表，并且哈希函数用于知道要从哪个列表中存储和检索给定的键。
这是该哈希图的实际操作的直观表示。单击存储桶上的任意位置，使用我们的 set 方法添加新的键值对。为了保持可视化简单，如果一个存储桶“溢出”，则所有存储桶都将被重置。
因为我们使用 murmur3 作为哈希函数，所以您应该看到存储桶之间的良好分布。预计您会看到一些不平衡，但通常应该相当均匀。
为了从哈希映射中获取值，我们首先对键进行哈希计算，以确定该值将位于哪个存储桶中。然后，我们必须将要搜索的键与存储桶中的所有键进行比较。
我们通过散列最小化了这个搜索步骤，这也是 murmur3 进行速度优化的原因。哈希函数越快，我们找到合适的存储桶进行搜索的速度就越快，哈希映射的整体速度就越快。
这也是为什么减少碰撞如此重要的原因。如果我们确实决定使用本文开头始终返回 0 的虚拟哈希函数，我们会将所有键值对放入第一个存储桶中。找到任何东西可能意味着我们必须检查哈希映射中的所有值。有了好的散列函数和良好的分布，我们就可以将搜索量减少到 1/N，其中 N 是桶的数量。 让我们看看 stringSum 是如何做的。
有趣的是， stringSum 似乎可以很好地分配值。您会注意到一种模式，但整体分布看起来不错。
没那么快，哈斯基。我们需要讨论一个严重的问题。这些连续数字的分布看起来不错，但我们已经看到 stringSum 没有良好的雪崩效应。这结局并不好。
现实世界的碰撞
让我们看一下 2 个现实世界的数据集：IP 地址和英语单词。我要做的是获取 100,000,000 个随机 IP 地址和 466,550 个英语单词，使用 murmur3 和 stringSum 对所有这些进行哈希处理，然后看看我们得到了多少次冲突。
当我们真正使用哈希映射时，我们通常不会在其中存储随机值。我们可以想象计算我们在服务器的速率限制代码中看到某个 IP 地址的次数。或者通过代码计算历史上书籍中单词的出现次数，以跟踪它们的起源和受欢迎程度。 stringSum 对于这些应用程序来说很糟糕，因为它的冲突率极高。
人为制造的碰撞
现在轮到 murmur3 带来一些坏消息了。我们需要担心的不仅仅是输入相似性引起的冲突。看一下这个。
这里发生了什么事？为什么所有这些乱码字符串都会散列到相同的数字？
我对 141 万亿个随机字符串进行哈希处理，以找到在使用 murmur3 时哈希到数字 1228476406 的值。哈希函数必须始终为特定输入返回相同的输出，因此可以通过强力查找冲突。
是的，我只花了 25 分钟。计算机速度很快。
如果您的软件根据用户输入构建哈希映射，那么很容易发生冲突的坏人可能会造成毁灭性的后果。以 HTTP 标头为例。 HTTP 请求如下所示：
GET / HTTP/1.1
Accept: */*
Accept-Encoding: gzip, deflate
Connection: keep-alive
Host: google.com
您不必理解所有单词，只需了解第一行是所请求的路径，所有其他行都是标头即可。标头是键：值对，因此 HTTP 服务器倾向于使用映射来存储它们。没有什么可以阻止我们传递我们想要的任何标头，因此我们可以非常刻薄地传递我们知道会导致冲突的标头。这会显着降低服务器速度。
这也不是理论上的。如果您搜索“HashDoS”，您会发现更多这样的示例。这在 2000 年代中期确实是一件大事。 有几种方法可以缓解 HTTP 服务器特有的这种情况：例如，忽略乱七八糟的标头键并限制您存储的标头数量。但像 murmur3 这样的现代哈希函数提供了一种更通用的解决方案：随机化。
在本文前面，我们展示了一些哈希函数实现的示例。这些实现采用一个参数：输入。许多现代哈希函数都采用第二个参数：种子（有时称为盐）。在 murmur3 的例子中，这个种子是一个数字。
到目前为止，我们一直使用 0 作为种子。让我们看看当我们使用种子 1 时我收集到的碰撞会发生什么。
就这样，0比1，碰撞就消失了。这就是种子的目的：它以不可预测的方式随机化哈希函数的输出。它如何实现这一点超出了本文的范围，所有哈希函数都以自己的方式实现这一点。
对于相同的输入，哈希函数仍然返回相同的输出，只是输入是输入和种子的组合。与一颗种子发生碰撞的物体在使用另一颗种子时不应发生碰撞。编程语言通常会在进程启动时生成一个随机数用作种子，因此每次运行程序时种子都是不同的。作为一个不知道种子的坏人，我现在不可能可靠地造成伤害。
如果您仔细观察上面的可视化和之前的可视化，您会发现它们是被散列的相同值，但它们产生不同的散列值。这意味着，如果您使用一个种子散列一个值，并且希望将来能够与它进行比较，则需要确保使用相同的种子。
不同种子具有不同的值不会影响哈希映射用例，因为哈希映射仅在程序运行期间有效。如果您在程序的生命周期中使用相同的种子，您的哈希映射将继续正常工作。如果您曾经将哈希值存储在程序之外（例如文件中），则需要小心了解使用的种子。
总结
我们已经介绍了哈希函数是什么、衡量它好坏的一些方法、它不好时会发生什么，以及它们可能被坏人破坏的一些方法。
哈希函数的范围很广，在这篇文章中我们实际上只触及了表面。我们还没有讨论加密与非加密散列，我们只触及了散列函数的数千个用例中的一个，并且我们还没有讨论现代散列函数实际上是如何工作的。
往期推荐
[1]
Source: https://samwho.dev/hashing/
腾讯云开发者
