为什么哈姆马特查询是O（1），即恒定时间？ [英] Why hashmap lookup is O(1) i.e. constant time?

问题描述

如果从Java的角度来看，我们可以说，哈希表查找需要不断的时间。但是内部实施呢？它仍然需要通过特定的桶（匹配哪个密钥的哈希码匹配）来搜索不同的匹配密钥。那么为什么我们说哈希表查找需要不断的时间？请解释。

If we look from Java perspective then we can say that hashmap lookup takes constant time. But what about internal implementation? It still would have to search through particular bucket (for which key's hashcode matched) for different matching keys.Then why do we say that hashmap lookup takes constant time? Please explain.

推荐答案

根据正在使用的哈希函数的适当假设，我们可以说哈希表查找取预期 O（1）时间。这意味着平均 ，散列表执行查找的工作量最多是一些常数。

Under the appropriate assumptions on the hash function being used, we can say that hash table lookups take expected O(1) time. This means that on average, the amount of work that a hash table does to perform a lookup is at most some constant.

直观地说，如果你有一个好的哈希函数，你会希望元素在整个哈希表中或多或少的均匀分布，这意味着每个分组中的元素数量将接近元素数量除以桶的数量。如果散列表实现保持这个数字低（比如说，每次元素比例增加到桶数之后添加更多的存储桶），那么所需的工作量就会成为一些基准的工作量来选择哪一个应该扫描，然后做不太多的工作，看看元素在那里，因为期望在那个桶中只有一个不变的元素。

Intuitively, if you have a "good" hash function, you would expect that elements would be distributed more or less evenly throughout the hash table, meaning that the number of elements in each bucket would be close to the number of elements divided by the number of buckets. If the hash table implementation keeps this number low (say, by adding more buckets every time the ratio of elements to buckets exceeds some constant), then the expected amount of work that gets done ends up being some baseline amount of work to choose which bucket should be scanned, then doing "not too much" work looking at the elements there, because on expectation there will only be a constant number of elements in that bucket.

这个并不意味着哈希表具有保证 O（1）行为。事实上，在最坏的情况下，散列方案将会退化，所有元素都将在一个桶中最终出现，从而使查找在最坏的情况下花费时间和精力。这就是为什么设计好的哈希函数很重要。

This doesn't mean that hash tables have guaranteed O(1) behavior. In fact, in the worst case, the hashing scheme will degenerate and all elements will end up in one bucket, making lookups take time Θ(n) in the worst case. This is why it's important to design good hash functions.

有关更多信息，您可能需要阅读算法教科书，以查看哈希表为什么支持查找的正式推导有效率的。这通常包含在典型的大学课程的算法和数据结构的一部分，并有许多好的资源在线。

For more information, you might want to read an algorithms textbook to see the formal derivation of why hash tables support lookups so efficiently. This is usually included as part of a typical university course on algorithms and data structures, and there are many good resources online.

希望这有帮助

这篇关于为什么哈姆马特查询是O（1），即恒定时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！