在我每个元素都有一个键，但不知道该元素在数组中的索引时，哈希表的性能比数组更好（O(1) vs O(n)）。
为什么这样呢？我的意思是：我有一个键，我对它进行了哈希处理...我得到了哈希值...难道算法不应该将此哈希值与每个元素的哈希值进行比较吗？我认为内存布局背后肯定有一些诀窍，不是吗？
为什么这样呢？我的意思是：我有一个键，我对它进行了哈希处理...我得到了哈希值...难道算法不应该将此哈希值与每个元素的哈希值进行比较吗？我认为内存布局背后肯定有一些诀窍，不是吗？
7个回答
107
对于每个元素都有一个键值(key)，但我不知道该元素在数组中的索引，这时使用哈希表比使用数组更加高效(O(1) vs O(n))。
哈希表搜索的平均时间复杂度为O(1)。最坏情况下，哈希表搜索的时间复杂度是O(n)：当哈希函数始终返回相同的插槽并且发生碰撞时。这可能被认为是“罕见情况”，但良好的分析应该考虑到这一点。在这种情况下，您需要像在数组或链表中一样遍历所有元素 (O(n))。
你有一个键值，你将其进行哈希操作，得到了哈希值: 哈希表中该元素所在的索引(如果之前已经查找到该元素)。此时，您可以在O(1)的时间内访问哈希表记录。如果负载因子很小，则不太可能看到多个元素位于同一个索引位置。因此，您看到的第一个元素应该是您正在寻找的元素。否则，如果您有多个元素，则必须将在该位置找到的元素与您要查找的元素进行比较。在这种情况下，时间复杂度为O(1) + O(元素数量)。
在平均情况下，哈希表搜索的复杂度为O(1) + O(负载因子) = O(1 + 负载因子)。
请记住，最坏情况下负载因子为n。因此，在最坏情况下，搜索复杂度为O(n)。
我不知道你所说的“内存位置技巧”的含义。从某些角度来看，哈希表（具有其结构和通过链接解决冲突）可以被认为是一种“聪明的技巧”。
当然，通过数学可以证明哈希表分析的结果。
哈希表搜索的平均时间复杂度为O(1)。最坏情况下，哈希表搜索的时间复杂度是O(n)：当哈希函数始终返回相同的插槽并且发生碰撞时。这可能被认为是“罕见情况”，但良好的分析应该考虑到这一点。在这种情况下，您需要像在数组或链表中一样遍历所有元素 (O(n))。
你有一个键值，你将其进行哈希操作，得到了哈希值: 哈希表中该元素所在的索引(如果之前已经查找到该元素)。此时，您可以在O(1)的时间内访问哈希表记录。如果负载因子很小，则不太可能看到多个元素位于同一个索引位置。因此，您看到的第一个元素应该是您正在寻找的元素。否则，如果您有多个元素，则必须将在该位置找到的元素与您要查找的元素进行比较。在这种情况下，时间复杂度为O(1) + O(元素数量)。
在平均情况下，哈希表搜索的复杂度为O(1) + O(负载因子) = O(1 + 负载因子)。
请记住，最坏情况下负载因子为n。因此，在最坏情况下，搜索复杂度为O(n)。
我不知道你所说的“内存位置技巧”的含义。从某些角度来看，哈希表（具有其结构和通过链接解决冲突）可以被认为是一种“聪明的技巧”。
当然，通过数学可以证明哈希表分析的结果。
- bitfox
3
7谢谢大家 :-) @ZoranPavlovic: 我出于热情写回答。点赞看起来像是：“我喜欢你的回复！”它们有助于强调社区中好的答案。 - bitfox
1在最坏的情况下，负载因子如何等于n？如果load_factor是n/k，其中n是元素数量，k是数组大小，那么在最坏的情况下，负载因子不会超过1，因为哈希表中不能存储超过k个元素。 - Isaac
有一件事我不太明白：你说哈希表的最坏情况是O(n)，其中n是元素的总数。然而，唯一需要线性迭代元素的情况是发生了碰撞（在这种情况下，桶是某种数组/链表/树）。所以你是说，在最坏的情况下，哈希表中的每个元素都导致了碰撞，因此查找是O(n)吗？这真的可能吗？应该是O(m)，其中m是散列到相同值的插入元素的数量吧？ - Julien Zakaib
68
使用数组：如果你知道值，你必须平均搜索一半的值(除非已经排序)才能找到它的位置。
使用哈希表：位置是根据值生成的。因此，再次给定该值时，可以计算出插入时计算的相同哈希值。有时，多个值会导致相同的哈希值，因此在实践中，每个"位置"本身都是一个数组(或链接列表)，包含所有哈希到该位置的值。在这种情况下，只需要搜索这个更小的数组(除非哈希函数很差)。
- Andy
4
13我知道这是一个古老的话题，但感谢你的回答！你简单明了的解释让我终于恍然大悟。之前我一直在想，为什么我要对这些东西进行哈希处理，我不是可以从一个简单的数组中获取它们吗...嗯，可能是因为我不知道它们的索引啊，呵呵 拍脑门 :). - Ryan McArthur
6谢谢！多年来，我知道哈希表将值存储在各个桶中（理想情况下，每个桶只有一个值），但是在我所阅读的所有资料中，没有人曾经解释过桶的位置本质上是由被存储的对象确定的，因此重新哈希值的行为让你知道了要查找哪个位置。我突然明白了为什么哈希表具有比数组快得多的潜力。答案简短而确切。 - Michael
4这对我来说比被接受的答案更有意义。谢谢。 - Kyle Delaney
干净、简单、易于理解的回答。谢谢。 - Spearson
28
哈希表有些复杂。它们根据元素的哈希 % 某个值将元素放入不同的桶(bucket)中。在理想情况下，每个桶只包含极少量的项且没有太多的空桶。
一旦你知道了键，就可以计算哈希。根据哈希值，你知道要查找哪个桶。而且，如上所述，每个桶中的项目数量应该相对较小。
哈希表在内部做很多魔法以确保桶尽可能地小，同时不会为空桶消耗太多内存。此外，关键是键-哈希函数的质量。
维基百科提供了非常全面的哈希表说明。
- Tomasz Nurkiewicz
1
1哈希表并不总是使用桶。 - Zoran Pavlovic
12
哈希表不需要比较哈希表中的每个元素，它会根据键计算出哈希码。举例来说，如果键是4，则哈希码可能是-4*x*y。现在指针就知道要选择哪个元素了。
相比之下，如果使用数组，它将必须遍历整个数组来搜索该元素。
- Sohil Jain
5
为什么哈希表的查找效率比数组好（O(1) vs O(n)）？我的意思是：我有一个键，我把它哈希了...我有了哈希值...算法难道不应该将这个哈希值与每个元素的哈希值进行比较吗？我认为在内存布局背后有一些诡计，不是吗？
一旦你有了哈希值，就可以计算出桶数组中“理想”的或预期的位置：通常是：
理想桶 = 哈希 % 桶数
问题在于另一个值可能已经哈希到那个桶中，此时哈希表实现有两个主要选择：
1）尝试另一个桶
2）让几个不同的值“属于”一个桶，通过使桶保存指向值链表的指针
对于实现1，也称为开放地址法或闭合哈希法，您需要跳转到其他桶：如果找到了您的值，那就太好了；如果找到了一个从未使用过的桶，那么在插入时可以将您的值存储在其中，或者在搜索时知道您永远不会找到您的值。如果遍历备选桶的方式导致多次搜索同一个桶，则搜索的潜力甚至可能比O（n）还要糟糕；例如，如果使用二次探测法，则尝试理想桶索引+1，然后+4，然后+9，然后+16等等 - 但必须避免使用例如
对于实现2，也称为闭散列或分离链接，您需要在所有哈希到理想桶的值的容器/数据结构中搜索。这取决于使用的容器类型的效率。通常预期在一个桶中碰撞的元素数量很少，这对于具有非对抗性输入的良好哈希函数是正确的，即使是具有素数桶的中等哈希函数通常也是如此。因此，尽管具有O(n)搜索特性，但通常使用链表或连续数组：链表易于实现和操作，而数组将数据打包在一起以获得更好的内存缓存局部性和访问速度。最坏的情况是，您表中的每个值都哈希到同一个桶中，该桶中的容器现在保存了所有值：您的整个哈希表的效率仅与桶容器一样高。如果哈希到相同桶的元素数量超过阈值，则一些Java哈希表实现已经开始使用二叉树，以确保复杂度永远不会超过O(log2n)。
Python的哈希表是一种开放地址法和闭散列法的例子。C++中的
一旦你有了哈希值，就可以计算出桶数组中“理想”的或预期的位置：通常是：
理想桶 = 哈希 % 桶数
问题在于另一个值可能已经哈希到那个桶中，此时哈希表实现有两个主要选择：
1）尝试另一个桶
2）让几个不同的值“属于”一个桶，通过使桶保存指向值链表的指针
对于实现1，也称为开放地址法或闭合哈希法，您需要跳转到其他桶：如果找到了您的值，那就太好了；如果找到了一个从未使用过的桶，那么在插入时可以将您的值存储在其中，或者在搜索时知道您永远不会找到您的值。如果遍历备选桶的方式导致多次搜索同一个桶，则搜索的潜力甚至可能比O（n）还要糟糕；例如，如果使用二次探测法，则尝试理想桶索引+1，然后+4，然后+9，然后+16等等 - 但必须避免使用例如
% num_buckets 的越界桶访问，因此如果有12个桶，则ideal + 4和ideal + 16搜索相同的桶。跟踪已搜索的桶可能很昂贵，因此很难知道何时放弃：实现可以乐观地假设它将始终找到值或未使用的桶（冒着永远旋转的风险），它可以拥有计数器，并在尝试阈值之后放弃或开始逐个桶进行线性搜索。对于实现2，也称为闭散列或分离链接，您需要在所有哈希到理想桶的值的容器/数据结构中搜索。这取决于使用的容器类型的效率。通常预期在一个桶中碰撞的元素数量很少，这对于具有非对抗性输入的良好哈希函数是正确的，即使是具有素数桶的中等哈希函数通常也是如此。因此，尽管具有O(n)搜索特性，但通常使用链表或连续数组：链表易于实现和操作，而数组将数据打包在一起以获得更好的内存缓存局部性和访问速度。最坏的情况是，您表中的每个值都哈希到同一个桶中，该桶中的容器现在保存了所有值：您的整个哈希表的效率仅与桶容器一样高。如果哈希到相同桶的元素数量超过阈值，则一些Java哈希表实现已经开始使用二叉树，以确保复杂度永远不会超过O(log2n)。
Python的哈希表是一种开放地址法和闭散列法的例子。C++中的
std::unordered_set则是一种闭地址法和分离链接的例子。- Tony Delroy
3
哈希的目的是生成底层数组的索引，从而使您可以直接跳转到所需的元素。通常通过将哈希除以数组大小并取余数来实现
哈希的类型/大小通常是足以索引所有RAM的最小整数类型。在32位系统上，这是32位整数。在64位系统上，这是64位整数。在C ++中，这分别对应于
在这方面，我认为值得明智地说一句话。算术的结果无论你是在最后还是在每个步骤中计算余数都是相同的。截断等同于计算保留n位二进制位的余数，其中n是你保留的位数。现在你可能会认为在每个步骤中计算余数是愚蠢的，因为你在沿途的每个步骤中都会产生额外的计算。然而，由于两个原因，情况并非如此。首先，在计算上，截断是非常便宜的，比广义除法要便宜得多。其次，这是真正的原因，即使没有第一个原因，该声明通常也成立，每个步骤中取余数可以保持数字（相对）较小。因此，您将需要像
现在谈谈房间里的大象。您可能已经意识到哈希码通常比它们对应的对象小，更不用说从中派生的索引通常更小了，因此完全有可能两个对象哈希到相同的索引上。这就是所谓的哈希冲突。由哈希表支持的数据结构，如Python的
接下来讲一下负载因子。当增加或减少负载因子时，空间和时间之间存在固有的权衡。负载因子越高，表占用的浪费空间就越少；但是这会增加性能下降的碰撞可能性。一般来说，使用分离链接实现的哈希表比使用开放地址法实现的哈希表对负载因子不太敏感。这是由于所谓的聚集现象，即在开放寻址哈希表中，簇倾向于随着正反馈循环而变得越来越大，因为它们变得越大，就越有可能包含新添加元素的首选索引。这实际上就是为什么前面提到的二次探测方案经常被优先选择的原因，因为它逐渐增加跳跃距离。在负载因子大于1的极端情况下，开放地址法根本无法工作，因为元素数量超过了可用空间。话虽如此，总体上负载因子大于1的情况非常罕见。在编写本文时，Python的
index = hash%capacity。哈希的类型/大小通常是足以索引所有RAM的最小整数类型。在32位系统上，这是32位整数。在64位系统上，这是64位整数。在C ++中，这分别对应于
unsigned int和unsigned long long。为了严谨起见，C ++技术上规定其原语的最小大小即至少32位和至少64位，但那不是重点。为了使代码具有可移植性，C ++还提供了一个相应的无符号整数size_t。在良好编写的代码中，您会经常看到这种类型用于索引数组的for循环中。在像Python这样的语言中，整数原语会增长到所需的任何大小。这通常在其他语言的标准库中以“大整数”的名称实现。为了解决这个问题，Python编程语言会将您从__hash __()方法返回的任何值截断为适当的大小。在这方面，我认为值得明智地说一句话。算术的结果无论你是在最后还是在每个步骤中计算余数都是相同的。截断等同于计算保留n位二进制位的余数，其中n是你保留的位数。现在你可能会认为在每个步骤中计算余数是愚蠢的，因为你在沿途的每个步骤中都会产生额外的计算。然而，由于两个原因，情况并非如此。首先，在计算上，截断是非常便宜的，比广义除法要便宜得多。其次，这是真正的原因，即使没有第一个原因，该声明通常也成立，每个步骤中取余数可以保持数字（相对）较小。因此，您将需要像
product = hash(31 * product + hash(array[index]))这样的东西，而不是像product = 31 * product + hash(array[index])这样的东西。内部hash()调用的主要目的是将可能不是数字的东西转换为数字，而外部hash()调用的主要目的是将潜在的超大数字截断。最后，我要注意的是，在像C++这样的语言中，整数基元具有固定的大小，每个操作后都会自动执行这个截断步骤。现在谈谈房间里的大象。您可能已经意识到哈希码通常比它们对应的对象小，更不用说从中派生的索引通常更小了，因此完全有可能两个对象哈希到相同的索引上。这就是所谓的哈希冲突。由哈希表支持的数据结构，如Python的
set或dict，或C++的std::unordered_set或std::unordered_map，主要通过以下两种方式处理这个问题。第一种被称为分离链接，第二种被称为开放地址。在分离链接中，充当哈希表的数组本身是一个列表数组（或在某些情况下，如果开发人员感觉想要使用其他数据结构，如二叉搜索树），每次元素哈希到给定索引时，它都会被添加到相应的列表中。在开放地址中，如果一个元素哈希到已经被占用的索引，数据结构会探测到下一个索引（或在某些情况下，如果开发人员感觉想要使用其他函数定义的索引，如二次探测），依此类推，直到找到一个空槽位，当然当它到达数组末尾时会回到开头。接下来讲一下负载因子。当增加或减少负载因子时，空间和时间之间存在固有的权衡。负载因子越高，表占用的浪费空间就越少；但是这会增加性能下降的碰撞可能性。一般来说，使用分离链接实现的哈希表比使用开放地址法实现的哈希表对负载因子不太敏感。这是由于所谓的聚集现象，即在开放寻址哈希表中，簇倾向于随着正反馈循环而变得越来越大，因为它们变得越大，就越有可能包含新添加元素的首选索引。这实际上就是为什么前面提到的二次探测方案经常被优先选择的原因，因为它逐渐增加跳跃距离。在负载因子大于1的极端情况下，开放地址法根本无法工作，因为元素数量超过了可用空间。话虽如此，总体上负载因子大于1的情况非常罕见。在编写本文时，Python的
set和dict类使用最大负载因子2/3，而Java的java.util.HashSet和java.util.HashMap使用3/4，C++的std::unordered_set和std::unordered_map则以最大负载因子1获胜。毫不奇怪，Python的哈希表支持的数据结构使用开放地址法处理冲突，而它们的Java和C++对应物则使用分离链接法。
最后关于表格大小的评论。当超过最大负载因子时，哈希表的大小必须增加。由于这需要重新索引其中的每个元素，因此按固定量增加表格大小非常低效。这样做会在每次添加新元素时产生数量级的操作。解决此问题的标准方法与大多数动态数组实现所采用的方法相同。在我们需要增加表格的每个点上，我们只需将其大小增加到当前大小。不出所料，这被称为表格加倍。
- M.J. Rayburn
-6
我认为你已经回答了自己的问题。"算法不应该将此哈希与每个元素的哈希进行比较"。当它不知道你要搜索的索引位置时，这就是它所做的。它会比较每个元素以找到你要查找的元素：
例如，假设你正在查找一个名为"Car"的项目，该项目位于字符串数组中。你需要遍历每个项目并检查item.Hash() == "Car".Hash()，以找出那是你要查找的项目。显然，它并不总是在搜索时使用哈希，但这个例子仍然成立。然后你有一个哈希表。哈希表所做的是创建一个稀疏数组，或者有时是桶数组，如上面提到的。然后它使用"Car".Hash()来推断出你的"Car"项实际上在稀疏数组中的哪个位置。这意味着它不必搜索整个数组来找到你的项目。
- Zoran Pavlovic
1
在搜索时，您不会比较哈希值。您需要计算哈希值，以获取值所在的索引，然后将找到的列表中的值与您要查找的值进行比较。 - Yousef
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接