performance - 哈希表 - 为什么它比数组快？

Question

在我为每个元素都有一个键并且我不知道数组中元素的索引的情况下，哈希表的性能优于数组（O(1) vs O(n)）。

这是为什么？我的意思是：我有一个密钥，我对其进行散列..我有散列..算法不应该将此散列与每个元素的散列进行比较吗？我认为内存配置背后有一些技巧，不是吗？

Answer 1

在我为每个元素都有一个键并且我不知道数组中元素的索引的情况下，哈希表的性能优于数组（O(1) vs O(n)）。

哈希表搜索在平均情况下执行 O(1)。在最坏的情况下，哈希表搜索执行 O(n)：当您有冲突并且哈希函数总是返回相同的槽时。人们可能会认为“这是一个遥远的情况”，但一个好的分析应该考虑到它。在这种情况下，您应该遍历数组或链表 (O(n)) 中的所有元素。

这是为什么？我的意思是：我有一个密钥，我对其进行散列..我有散列..算法不应该将此散列与每个元素的散列进行比较吗？我认为内存配置背后有一些技巧，不是吗？

你有一个键，你散列它..你有散列：元素所在的散列表的索引（如果它之前已经找到）。此时您可以访问 O(1) 中的哈希表记录。如果负载因子很小，则不太可能在那里看到多个元素。因此，您看到的第一个元素应该是您正在寻找的元素。否则，如果您有多个元素，则必须将在该位置找到的元素与您正在寻找的元素进行比较。在这种情况下，您有 O(1) + O(number_of_elements)。

在平均情况下，哈希表搜索复杂度为 O(1) + O(load_factor) = O(1 + load_factor)。

请记住，在最坏的情况下 load_factor = n。因此，在最坏的情况下，搜索复杂度为 O(n)。

我不知道您所说的“内存配置背后的技巧”是什么意思。在某些观点下，哈希表（具有其结构和通过链接解决冲突）可以被认为是一种“聪明的技巧”。

当然，哈希表的分析结果可以用数学来证明。

Answer 2

使用数组：如果您知道该值，则必须平均搜索一半的值（除非已排序）才能找到其位置。

使用哈希：位置是根据值生成的。因此，再次给出该值，您可以计算插入时计算的相同哈希值。有时，超过 1 个值会导致相同的散列，因此实际上每个“位置”本身就是散列到该位置的所有值的数组（或链表）。在这种情况下，只需要搜索这个小得多（除非它是一个坏哈希）的数组。

Answer 3

哈希表有点复杂。他们根据哈希值将元素放入不同的桶中。在理想情况下，每个桶中的物品很少，空桶也不多。

一旦知道了密钥，就可以计算哈希。根据哈希，您知道要查找哪个存储桶。并且如上所述，每个桶中的项目数应该相对较少。

哈希表在内部做了很多神奇的事情，以确保存储桶尽可能小，同时不会为空存储桶消耗太多内存。此外，很大程度上取决于密钥 -> 哈希函数的质量。

维基百科提供了非常全面的哈希表描述。

Answer 4

哈希表不必比较哈希中的每个元素。它将根据密钥计算哈希码。例如，如果 key 是 4，那么 hashcode 可能是 - 4*x*y。现在指针确切地知道要选择哪个元素。

而如果它是一个数组，它必须遍历整个数组来搜索这个元素。

Answer 5

为什么 [它] [哈希表通过键执行查找比数组 (O(1) vs O(n))] 更好？我的意思是：我有一个密钥，我对其进行散列..我有散列..算法不应该将此散列与每个元素的散列进行比较吗？我认为内存配置背后有一些技巧，不是吗？

一旦你有了哈希，它就可以让你计算桶数组中的“理想”或预期位置：通常：

理想桶 = 哈希 % num_buckets

那么问题是另一个值可能已经散列到该桶，在这种情况下，散列表实现有两个主要选择：

1）尝试另一个桶

2）让几个不同的值“属于”一个桶，也许通过让桶持有指向值链表的指针

对于实现 1，称为开放寻址或封闭散列，您可以跳过其他存储桶：如果您发现自己的价值，那就太好了；如果您找到一个从未使用过的存储桶，那么您可以在插入时将您的值存储在其中，或者您知道在搜索时永远找不到您的值。如果您遍历替代存储桶的方式最终多次搜索同一个存储桶，则搜索可能会比 O(n) 更糟；例如，如果您使用二次探测，您尝试理想的桶索引 +1，然后 +4，然后 +9，然后 +16 等等 - 但您必须避免使用例如越界桶访问% num_buckets，所以如果有 12 个桶，那么 Ideal+4 和 Ideal+16 搜索同一个桶。跟踪搜索了哪些存储桶可能会很昂贵，因此也很难知道何时放弃：实现可以是乐观的，并假设它总是会找到值或未使用的存储桶（冒着永远旋转的风险），它可以有一个计数器，并且在尝试的阈值之后要么放弃，要么开始逐个桶的线性搜索。

对于实现 2，称为封闭寻址或单独链接，您必须在所有散列到理想存储桶的值的容器/数据结构中进行搜索。这有多有效取决于使用的容器类型。通常预计在一个桶中碰撞的元素数量会很少，这对于具有非对抗性输入的良好散列函数来说是正确的，并且通常即使是平庸的散列函数也足够真实，尤其是对于具有素数的桶。因此，尽管具有 O(n) 搜索属性，但通常使用链表或连续数组：链表易于实现和操作，并且数组将数据打包在一起以获得更好的内存缓存局部性和访问速度。最糟糕的情况是，表中的每个值都散列到同一个桶中，而该桶中的容器现在保存了所有值：桶的容器。如果散列到相同存储桶的元素数量超过阈值，一些 Java 哈希表实现已经开始使用二叉树，以确保复杂性永远不会比 O(log2n) 差。

Python 哈希是 1 = 开放寻址 = 封闭哈希的示例。C++std::unordered_set是封闭寻址 = 单独链接的示例。

Answer 6

散列的目的是为底层数组生成一个索引，这使您能够直接跳转到有问题的元素。这通常通过将散列除以数组的大小并取余数来完成index = hash%capacity。

散列的类型/大小通常是足以索引所有 RAM 的最小整数。在 32 位系统上，这是一个 32 位整数。在 64 位系统上，这是一个 64 位整数。在 C++ 中，这分别对应于unsigned int和unsigned long long。迂腐的 C++ 在技术上为其原语指定了最小大小，即至少 32 位和至少 64 位，但这不是重点。为了使代码可移植，C++ 还提供了一个size_t原语对应于适当的无符号整数。在编写良好的代码中，您会在索引到数组的 for 循环中看到很多类型。在像 Python 这样的语言的情况下，整数原语可以增长到它需要的任何大小。这通常在名为“Big Integer”的其他语言的标准库中实现。为了解决这个问题，Python 编程语言简单地将您从__hash__()方法返回的任何值截断为适当的大小。

在这一点上，我认为值得对智者说一说。无论您是在最后还是在沿途的每一步计算余数，算术的结果都是相同的。截断相当于计算余数模 2^n，其中 n 是您保持不变的位数。现在你可能认为在每一步计算余数是愚蠢的，因为你在每一步都会产生额外的计算。然而，情况并非如此，原因有两个。首先，从计算上讲，截断非常便宜，远比广义除法便宜。其次，这是真正的原因，因为第一个是不够的，即使在没有它的情况下，索赔通常也会成立，在每个步骤中取剩余部分会使数量（相对）小。所以而不是像product = 31*product + hash(array[index])，你会想要类似的东西product = hash(31*product + hash(array[index]))。内部 hash() 调用的主要目的是获取可能不是数字的东西并将其转换为一个，而外部 hash() 调用的主要目的是获取可能过大的数字并将其截断。最后我会注意到，在像 C++ 这样整数基元具有固定大小的语言中，这个截断步骤会在每次操作后自动执行。

现在是房间里的大象。您可能已经意识到散列码通常比它们对应的对象小，更不用说从它们派生的索引通常更小，两个对象完全有可能散列到同一个索引。这称为哈希冲突。set由 Python或dictC++ 之类的哈希表支持的数据结构std::unordered_set或std::unordered_map主要以两种方式之一处理此问题。第一个称为分离链接，第二个称为开放寻址。在单独链接中，用作哈希表的数组本身就是一个列表数组（或者在某些情况下，开发人员觉得很花哨，其他一些数据结构，如二叉搜索树），并且每次元素散列到给定索引时，它都会被添加到相应的列表中。在开放寻址中，如果一个元素散列到一个已经被占用的索引，则数据结构会探测到下一个索引（或者在某些情况下，开发人员觉得很花哨，一个由其他函数定义的索引，如二次探测的情况) 依此类推，直到它找到一个空槽，当它到达数组的末尾时当然会环绕。

接下来谈谈负载系数。在增加或减少负载因子时，当然存在固有的空间/时间折衷。负载因子越高，表占用的空间越少；然而，这是以增加性能降低冲突的可能性为代价的。一般来说，使用单独链接实现的哈希表对负载因子的敏感度低于使用开放寻址实现的哈希表。这是由于称为聚类的现象其中，开放寻址哈希表中的簇在正反馈循环中趋于变得越来越大，这是因为它们越大，它们就越有可能包含新添加元素的首选索引。这实际上是为什么前面提到的逐渐增加跳跃距离的二次探测方案通常是首选的原因。在负载因子大于 1 的极端情况下，开放寻址根本无法工作，因为元素的数量超过了可用空间。也就是说，大于 1 的负载因子通常非常罕见。在编写 Pythonset和dict类时，最大负载因子为 Java 的 2/3，而 C++ 的最大负载因子java.util.HashSet为java.util.HashMap3/4 std::unordered_set，std::unordered_map最大负载因子为 1 的蛋糕。不出所料，Python 的哈希表支持的数据结构处理与开放寻址的冲突，而它们的 Java 和 C++ 对应物使用单独的链接来处理冲突。

最后评论一下桌子的大小。当超过最大负载因子时，哈希表的大小当然必须增加。由于这需要重新索引其中的每个元素，因此将表增长固定数量是非常低效的。这样做会在每次添加新元素时产生订单大小操作。此问题的标准修复方法与大多数动态数组实现所采用的方法相同。在我们需要扩大表格的每一个点上，我们只需将其大小增加其当前大小。不出所料，这被称为表加倍。

Answer 7

我想你在那里回答了你自己的问题。“算法不应该将此哈希与每个元素的哈希进行比较”。当它不知道您正在搜索的内容的索引位置时，它就是这样做的。它比较每个元素以找到您要查找的元素：

例如，假设您在一个字符串数组中寻找一个名为“Car”的项目。您需要检查每个项目并检查 item.Hash() == "Car".Hash() 以找出您要查找的项目。显然，它总是在搜索时不使用散列，但这个例子就成立了。然后你有一个哈希表。哈希表的作用是创建一个稀疏数组，或者有时像上面提到的那样创建一个桶数组。然后它使用 "Car".Hash() 来推断你的 "Car" 项目在稀疏数组中的实际位置。这意味着它不必搜索整个数组来查找您的项目。