哈希表 - 为什么它比数组快? [英] Hash table - why is it faster than arrays?

问题描述

如果我有每个元素的键并且我不知道元素在数组中的索引，哈希表的性能优于数组(O(1) vs O(n)).

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)).

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

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) vs O(n)).

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)).

The hash table search performs O(1) in the average case. In the worst case, the hash table search performs O(n): when you have collisions and the hash function always returns the same slot. One may think "this is a remote situation," but a good analysis should consider it. In this case you should iterate through all the elements like in an array or linked lists (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).

You have a key, You hash it.. you have the hash: the index of the hash table where the element is present (if it has been located before). At this point you can access the hash table record in O(1). If the load factor is small, it's unlikely to see more than one element there. So, the first element you see should be the element you are looking for. Otherwise, if you have more than one element you must compare the elements you will find in the position with the element you are looking for. In this case you have O(1) + O(number_of_elements).

一般情况下，哈希表搜索复杂度为 O(1) + O(load_factor) = O(1 + load_factor).

In the average case, the hash table search complexity is O(1) + O(load_factor) = O(1 + load_factor).

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

Remember, load_factor = n in the worst case. So, the search complexity is O(n) in the worst case.

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

I don't know what you mean with "trick behind the memory disposition". Under some points of view, the hash table (with its structure and collisions resolution by chaining) can be considered a "smart trick".

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

Of course, the hash table analysis results can be proven by math.

这篇关于哈希表 - 为什么它比数组快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！