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

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

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

如果它是一个数组,它将必须遍历整个数组来搜索这个元素.

Answer 5

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

一旦获得哈希值，它就可以让您计算存储桶数组中的“理想”或预期位置：通常：

理想桶 = 哈希 % num_buckets

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

1）尝试另一个桶

2）让几个不同的值“属于”一个桶，也许是通过让桶保存一个指向值链接列表的指针

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

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

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