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

Question

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

这是为什么呢？我的意思是:我有一个 key ，我对其进行哈希处理。我有哈希值。算法不应该将此哈希值与每个元素的哈希值进行比较吗？我认为内存配置背后有一些技巧，不是吗？

Answer 1

In cases where I have a key for each element and I don't know the index of the element into an array, hashtables perform better than arrays (O(1) vs O(n)).

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

Why is that? I mean: I have a key, I hash it.. I have the hash.. shouldn't the algorithm compare this hash against every element's hash? I think there's some trick behind the memory disposition, isn't it?

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

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

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

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

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