数据结构 – 为什么哈希表查找是O(1),即恒定时间？

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

在使用的哈希函数的适当假设下,我们可以说哈希表查找取预期的O(1)时间.这意味着平均来说,散列表执行查找的工作量最多是一定的.

直观地说,如果你有一个“好的”哈希函数,你会希望这些元素在整个散列表中被均匀地分配,这意味着每个数据桶中元素的数量将接近元素数量除以数字的桶.如果哈希表实现保持这个数字低(比如说,每当元素与桶之间的比例超过一些常量时,添加更多的桶),那么所做的预期工作量就会被作为一些基准量来选择哪个桶应该被扫描,然后做“不太多”的工作,看看元素在那里,因为期望在那个桶中将只有一个恒定数量的元素.

这并不意味着散列表保证了O(1)行为.事实上,在最坏的情况下,散列方案将退化,所有元素都将在一个桶中结束,从而使查找在最坏的情况下花费时间Θ(n).这就是为什么设计好的哈希函数很重要.

有关更多信息,您可能需要阅读算法教科书,以查看哈希表如何有效地支持查找的正式推导.这通常包含在典型的大学课程中作为算法和数据结构的一部分,并且在线有很多好的资源.

希望这可以帮助！

http://stackoverflow.com/questions/15469795/why-hashmap-lookup-is-o1-i-e-constant-time