HashMap获取/放置复杂性

2018-06-12 22:09:18

我们习惯于说HashMap get/put操作是O（1）。但它取决于散列实现。默认对象散列实际上是JVM堆中的内部地址。我们确定它是否足以说明get/put是O（1）？

可用内存是另一个问题。正如我从javadocs了解到的， HashMap load factor应该是0.75。如果我们在JVM中没有足够的内存并且load factor超出限制会怎么样？

所以，看起来O（1）不能保证。它有意义还是我错过了什么？

这取决于很多事情。它通常是O（1），它有一个不错的散列本身是恒定的时间......但是你可能有一个散列需要很长时间来计算，并且如果在散列映射中有多个项目返回相同的散列码， get将不得不遍历他们调用equals他们每个人找到一个匹配。

在最坏的情况下，由于散列在同一散列桶中的所有条目（例如，如果它们都具有相同的散列码）， HashMap具有O（n）查找。幸运的是，根据我的经验，最坏的情况在现实生活中并不常见。所以不，O（1）当然不能保证 - 但是在考虑使用哪种算法和数据结构时，通常应该假设它。

在JDK 8中，对HashMap进行了调整，以便如果可以比较键的排序顺序，那么任何稠密填充的桶都会以树的形式实现，因此即使存在大量具有相同哈希代码的条目，复杂度也是O（日志n）。当然，如果您的关键类型的平等和排序不同，那么这可能会导致问题。

是的，如果你没有足够的内存来存储哈希映射，那么你会遇到麻烦......但是无论你使用什么数据结构，情况都是如此。

我不确定默认的哈希码是不是地址 - 我前一段时间读取了OpenJDK哈希码生成源，我记得它有点复杂。也许不是保证良好分配的东西。然而，这在一定程度上是没有意义的，因为在hashmap中用作键的类很少使用默认的哈希码 - 它们提供了它们自己的实现，这应该是很好的。

最重要的是，你可能不知道的（再次，这是基于阅读来源 - 它不能保证）是HashMap在使用之前搅动散列，将整个单词的熵混合到底部位，这就是它的地方除了最大的hashmaps外，都需要它。这有助于处理特别不会自己做的哈希，虽然我想不出任何你能看到的常见情况。

最后，当表超载时会发生什么，它退化为一组并行链表 - 性能变为O（n）。具体来说，所遍历的链接的数量平均是负载因子的一半。

已经提到，如果n是物品的数量， m是尺寸，则hashmaps平均为O(n/m) 。还有人提到，原则上整个事情可以用O(n)查询时间折成单链表。（这一切都假定计算哈希是恒定时间）。

然而，通常不会提到的是，如果概率至少为1-1/n （因此1000个项目的概率为99.9％），最大的桶将不会被填充超过O(logn) ！因此匹配二叉搜索树的平均复杂度。（常数是好的，更严格的界限是(log n)*(m/n) + O(1) ）。

这个理论界限所需要的就是你使用一个相当好的散列函数（参见Wikipedia：Universal Hashing，它可以像a*x>>m那样简单）。当然，给你哈希值的人不知道你是如何选择你的随机常量的。

TL; DR：具有非常高的概率，最坏情况下hashmap的get / put复杂度为O(logn) 。

链接地址: http://www.djcxy.com/p/36903.html