为什么hashmap查找是O(1)即恒定时间？

Question

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

Answer 1

在对正在使用的散列函数的适当假设下,我们可以说散列表查找需要预期的 O(1)时间(假设您使用的是标准散列方案,如线性探测或链式散列).这意味着平均而言,哈希表执行查找的工作量最多只是一些常量.

直觉上,如果你有一个"好"的哈希函数,你会期望元素在整个哈希表中或多或少地均匀分布,这意味着每个桶中的元素数量将接近元素的数量除以数量水桶 如果哈希表实现保持这个数字很低(比如,每次元素与桶的比率超过某个常数时添加更多桶),那么完成的预期工作量最终会成为选择哪个桶的基线工作量应该扫描,然后做"不太多"的工作,看看那里的元素,因为期望在那个桶中只有恒定数量的元素.

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

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

有趣的事实:存在某些类型的哈希表(布谷鸟哈希表,动态完美哈希表),其中元素的最坏情况查找时间是O(1).这些哈希表的工作原理是保证每个元素只能位于几个固定位置中的一个位置,插入有时会在元素周围加扰以尝试使所有内容都适合.

希望这可以帮助!

Answer 2

哈希表不是 O(1)。

通过鸽巢原理，您的查找速度不会比 O(log(n)) 更好，因为每个项目需要 log(n) 位来唯一标识 n 个项目。

哈希表似乎是 O(1)，因为它们有一个小的常数因子，并且 O(log(n)) 中的“n”被增加到这样的程度，对于许多实际应用来说，它与实际的数量无关。您正在使用的物品。然而，大 O 表示法并不关心这个事实，并且调用哈希表 O(1) 是一种（理所当然的，荒谬的常见）表示法的滥用。

因为虽然您可以在哈希表中存储一百万或十亿个项目，但仍然获得与单个项目哈希表相同的查找时间...如果您要获取大约十亿或 googleplex 项目，您就会失去这种能力。事实上，你永远不会真正使用 nonillion 或 googleplex 项目，这对于大 O 表示法来说并不重要。

实际上，哈希表性能可能是比数组查找性能差的一个常数因素。是的，这也是 O(log(n))，因为你不能做得更好。

基本上，现实世界的计算机对大小小于其芯片位大小的数组的每次数组查找与理论上最大的可用数组一样糟糕，并且由于哈希表是在数组上执行的巧妙技巧，这就是为什么您似乎得到O(1)

Answer 3

关键是在文档中的这个声明中:

如果要将多个映射存储在HashMap实例中,则使用足够大的容量创建映射将允许映射更有效地存储,而不是根据需要执行自动重新散列来扩展表.

和

加载因子是在自动增加容量之前允许哈希表获取的完整程度的度量.当哈希表中的条目数超过加载因子和当前容量的乘积时,哈希表将被重新哈希(即,重建内部数据结构),以便哈希表具有大约两倍的桶数.

http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html

如果超出负载系数,实际上将重建内部桶结构,允许get和put的摊销成本为O(1).

请注意,如果重建内部结构,会引入可能为O(N)的性能损失,因此在摊销成本再次接近O(1)之前可能需要相当多的get和put.因此,请适当规划初始容量和负载系数,这样既不会浪费空间,也不会触发内部结构的可避免重建.