哈希表真的可以是O(1)吗? [英] Can hash tables really be O(1)?

问题描述

哈希表可以实现O(1)似乎是一个常识，但这对我来说从来没有任何意义.有人可以解释一下吗?这是我想到的两种情况:

It seems to be common knowledge that hash tables can achieve O(1), but that has never made sense to me. Can someone please explain it? Here are two situations that come to mind:

A. 该值是一个小于哈希表大小的整数.因此，该值是其自己的哈希表，因此没有哈希表.但是，如果有的话，它将是O(1)，但效率仍然很低.

A. The value is an int smaller than the size of the hash table. Therefore, the value is its own hash, so there is no hash table. But if there was, it would be O(1) and still be inefficient.

B. 您必须计算值的哈希值.在这种情况下，对于要查找的数据大小，顺序为O(n).在您完成O(n)工作后，查找可能是O(1)，但在我眼里仍然是O(n).

B. You have to calculate a hash of the value. In this situation, the order is O(n) for the size of the data being looked up. The lookup might be O(1) after you do O(n) work, but that still comes out to O(n) in my eyes.

除非您有完美的哈希表或大型哈希表，否则每个存储桶中可能有几项.因此，无论如何它都会演变成小的线性搜索.

And unless you have a perfect hash or a large hash table, there are probably several items per bucket. So, it devolves into a small linear search at some point anyway.

我认为哈希表很棒，但是除非得到理论上的认可，否则我不会获得O(1)的称呼.

I think hash tables are awesome, but I do not get the O(1) designation unless it is just supposed to be theoretical.

Wikipedia的有关哈希表的文章始终引用恒定的查找时间，并且完全忽略了哈希的成本功能.这真的很公平吗?

Wikipedia's article for hash tables consistently references constant lookup time and totally ignores the cost of the hash function. Is that really a fair measure?

总结我学到的知识:

• 从技术上讲这是正确的，因为不需要散列函数来使用键中的所有信息，因此可以是恒定时间，并且因为足够大的表可以使冲突降低到接近恒定时间.

• It is technically true because the hash function is not required to use all the information in the key and so could be constant time, and because a large enough table can bring collisions down to near constant time.

实际上是这样，因为随着时间的推移，只要选择哈希函数和表大小以最大程度地减少冲突，就可以解决问题，尽管这通常意味着不使用恒定时间哈希函数.

It is true in practice because over time it just works out as long as the hash function and table size are chosen to minimize collisions, even though that often means not using a constant time hash function.

推荐答案

您在这里有两个变量m和n，其中m是输入的长度，n是哈希中的项数.

You have two variables here, m and n, where m is the length of the input and n is the number of items in the hash.

O(1)查询性能声明至少做出两个假设:

The O(1) lookup performance claim makes at least two assumptions:

• 您的对象在O(1)时间内可以相等.
• 几乎没有哈希冲突.

如果对象的大小可变，并且相等性检查需要查看所有位，则性能将变为O(m).但是，哈希函数不必为O(m)-可以为O(1).与加密哈希不同，在字典中使用的哈希函数不必查看输入中的每一位即可计算哈希.实现可以随意查看固定数量的位.

If your objects are variable size and an equality check requires looking at all bits then performance will become O(m). The hash function however does not have to be O(m) - it can be O(1). Unlike a cryptographic hash, a hash function for use in a dictionary does not have to look at every bit in the input in order to calculate the hash. Implementations are free to look at only a fixed number of bits.

对于足够多的项目，项目的数量将变得大于可能的散列的数量，然后您将发生碰撞，从而导致性能提高到O(1)以上，例如对于O(n)进行简单的链表遍历(或如果两个假设都为假，则为O(n * m).

For sufficiently many items the number of items will become greater than the number of possible hashes and then you will get collisions causing the performance rise above O(1), for example O(n) for a simple linked list traversal (or O(n*m) if both assumptions are false).

在实践中，尽管O(1)在技术上是错误的，但在许多现实情况下，尤其是在上述假设成立的情况下，近似是正确的.

In practice though the O(1) claim while technically false, is approximately true for many real world situations, and in particular those situations where the above assumptions hold.

这篇关于哈希表真的可以是O(1)吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！