哈希表简介（JS 对象底层）

在数据结构和算法的世界里，哈希表极其常见。作为一个主要使用 JavaScript 的人，我其实并不需要真正接触过它们——因为就像许多其他东西一样——JavaScript 将它们抽象化了（剧透：它们是对象）。然而，为了学习 DSA 的资料，我这个周末花了一些时间研究它们，希望分享我的学习成果，帮助揭开这种常见数据结构的神秘面纱——并更好地理解对象如何存储数据，以及当你输入键时如何检索值。

为了理解哈希表的内部工作原理，让我们来尝试一个假想的问题：检查一个数组是否包含一个值。

我们有一个 [1, 3, 4] 的数组。我们如何检查此数组是否包含数字 5？最简单的解决方案是遍历数组 - 检查每个值并查看它是否等于 5 - 最终返回 false，因为上述数组没有 5。这很好，但此解决方案在 O(n) 时间内完成 - 也就是说，解决这个问题所需的时间取决于数组的大小。如果我们有一个长度为 10k 的数组，并且我们想要检查它是否包含特定值，这将非常耗时 - 在最坏的情况下，我们必须检查所有 10k 索引才能回答这个问题。因此考虑到这一点，我们如何在 O(1) 或常数时间内解决这个问题。我们如何才能立即得到数组是否包含特定值的答案 - 无论它的长度是多少？

让我们采用另一种方法——我们可以使用布尔数组来表示该索引的值是否包含在我们原始值集中 - （即索引 1 处的 true 表示包含数字 1） - 这看起来像这样：

Values:     1     3  4
 Index:  0  1  2  3  4
   Arr:[ F, T, F, T, T ]

通过这种方式，我们可以在 O(1) 时间内检查值是否包含一个值 - 因为我们所需要做的就是访问该索引并检查 T/F。

现在我们已经有了一个非常简单的示例设置，一个问题变得清晰起来——如果值包含一个很大的数字（例如 100）怎么办？我们必须在数组中填充 90 多个值或 F，才能在索引 100 处指示 T。显然，这非常低效——因此，为了解决这个问题，我们需要想出一种方法，使数组的长度能够更好地与其所表示的实际值数量相对应。一个常见的例子是，如何将值调整到较小的数组中，就是将它们的模 10，然后将其用作存储 T/F 的索引。

我们的新值集包含：1、3、4、77 和 100
77%10=7 和 100%10=0，因此这些索引现在将包含 T

Values: 100    1     3  4        77        
   Arr:[ T, T, F, T, T, F, F, F, T, F, F ]

现在我们已经看到了这一点 - 让我们使我们的数组更复杂一些，并在其中实际存储键/值对，以更好地反映给定索引中包含的任何内容的实际值 - 只看到 0/7 是 T 并不能很好地反映它们所代表的底层值是 100 和 77。

由于这是对象实现方式的底层实现，我们不能只使用对象来实现这一点，而是使用另一个数组，其中第一个索引是键，第二个索引是值

我们的新系列包含：1、3、4、77 和 100

 Arr:[ 
    [100,T], 
    [1, T], 
    F, 
    [3, T], 
    [4, T], 
    F, 
    F, 
    F, 
    [77, T], 
    F, 
    F ]

现在我们添加一个 17，这样我们就会看到另一个问题：冲突。在我们当前的系统中，我们根据某个值对 10 的模数来决定它的存储位置——所以现在我们有两个冲突的值，它们都想存储在索引 7 处（7 和 77）。我们不用覆盖 77，而是直接在索引 7 处添加另一个键/值对数组。像这样将多个值存储在一个位置称为“单独链接”，这只是处理冲突的众多方法之一。

Value at index 7
    [77, T] ------> [ [77,T], [17,T] ]

这很酷——但我们的值是数字，这实在太方便了——如果我们想用字符串来实现类似的功能，该怎么办呢？这需要真正的哈希处理——将一个值转换为某种能够代表它的数字代码。实际上，哈希处理是通过一些非常复杂的数学原理完成的，你可以自己研究一下，但最终它只是将某个值转换为数字代码的过程。

现在假设我们的值包含字符串“Dog”和“Cat”，其中dog的值为5，cat的值为3。一个伪散列函数的例子是使用字符串中每个字符的组合ASCII值来确定其哈希码。我有点懒，所以我们假设“Dog”的组合ASCII值为31，“Cat”的组合ASCII值为23。

太棒了——现在我们只需创建另一个数组，并将值存储在正确的索引处。我们再次使用 %10 来将数组长度控制在大约 10 个字符左右——但现在我们将使用实际的哈希码来确定动物字符串的存放位置——“狗”将存放在索引 1 处，“猫”将存放在索引 3 处。

 Arr:[ 
    F, 
    ['Dog', 5], 
    F, 
    ['Cat', 3], 
    F, 
    F, 
    F, 
    F, 
    F, 
    F, 
    F ]

这里最重要的是，通过一个真正的哈希函数，我们可以将任何类型的数据转换成数字代码，然后使用该代码将其放入数组中。这样，我们就可以在 0(1) 的时间内使用适当的索引访问数据（尽管如果由于单独的链接导致多个值堆积在一个位置，则可能需要更多时间），这比传统的循环效率高得多。

最后要讨论的概念是负载因子（用 lambda 表达式表示）。如果我们要存储 1000 个字符串，会发生什么情况？我们已经知道要控制数组的长度，但最终会导致每个索引中都包含一堆值，因为链式引用彼此独立。如果这种情况发生，哈希表的速度就会变慢，这完全违背了我们的初衷。负载因子就是为了维持这种平衡，其计算方式如下：

负载因子 = （键/值对的数量）/（数组的长度）

当使用分离链式结构时，我们始终希望负载因子为 1 或更低（即数组的长度始终大于或等于其存储的对的数量）。利用这个概念，我们可以在达到平衡时调整数组的大小。

……就是这样——哈希表内部工作原理的简单概述。
从中我们可以得出一个结论：与其简单地将数据存储在数组/列表中并反复循环，不如更进一步，将数据哈希后放入特定的索引中。当我们能够快速找到数据时，这点额外的工作就值得了。

将所有这些归结为一句话 - 哈希表只是一个键/值对的数组，它使用复杂的数学来确定在何处/如何存储该数据，以便以后可以快速访问。

就像编码世界中的许多事物一样 - 它基本上只是一个数组 - 但希望这篇文章能够帮助您揭开哈希表是什么以及为什么使用它的神秘面纱。

感谢您的阅读，请留下任何问题/评论！

谢谢-

洛根