为什么哈希图查找是 O(1)，即恒定时间? [英] Why hashmap lookup is O(1) i.e. constant time?

问题描述

如果我们从 Java 的角度来看，那么我们可以说 hashmap 查找需要恒定的时间.但是内部实现呢?它仍然需要在特定的桶中搜索不同的匹配键(匹配哪个键的哈希码).那么为什么我们说哈希图查找需要恒定时间?请解释.

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 (assuming you're using a standard hashing scheme like linear probing or chained hashing). 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) 行为.事实上，在最坏的情况下，散列方案会退化，所有元素最终都会在一个桶中，在最坏的情况下，查找需要时间θ(n).这就是为什么设计好的哈希函数很重要.

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).这些哈希表的工作原理是保证每个元素只能位于几个固定位置之一，插入有时会围绕元素争先恐后地尝试使所有内容都适合.

Fun fact: there are certain types of hash tables (cuckoo hash tables, dynamic perfect hash tables) where the worst case lookup time for an element is O(1). These hash tables work by guaranteeing that each element can only be in one of a few fixed positions, with insertions sometimes scrambling around elements to try to make everything fit.

希望这有帮助！

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