HashMap获取/放置复杂性

Question

HashMap获取/放置复杂性

我们习惯这样说HashMap get/put操作为O(1)。但是，它取决于哈希实现。默认对象哈希实际上是JVM堆中的内部地址。我们确定它足够好声称get/put是O(1)吗？

可用内存是另一个问题。正如我从javadocs了解到的，HashMap load factor应该是0.75。如果JVM和load factor超过极限了？

所以，看起来O(1)没有得到保证。这有意义吗还是我遗漏了什么？

Answer 1

这取决于许多事情。它是通常O(1)，有一个很好的散列，它本身就是固定时间.但是你可能会有一个需要很长时间才能计算出来的散列，和如果哈希映射中有多个返回相同哈希代码的项，get将不得不对它们进行迭代调用equals在他们每个人身上找到一个匹配的。在最坏的情况下，HashMap由于在同一个散列桶中遍历所有条目(例如，如果它们都具有相同的哈希代码)，因此具有O(N)查找。幸运的是，根据我的经验，在现实生活中，这种最坏的情况并不经常出现。所以不，O(1)当然不能保证-但是当您考虑使用哪种算法和数据结构时，通常应该这样做。在JDK 8中，HashMap已经进行了调整，以便如果可以比较键来排序，那么任何人口稠密的桶都被实现为一棵树，因此即使有大量具有相同哈希码的条目，复杂度也是O(Logn)。当然，如果您有一个平等和顺序不同的键类型，这可能会导致问题。是的，如果你没有足够的内存做散列表，你就会有麻烦.但不管你用什么数据结构，这都是真的。

Answer 2

我不确定默认的hashcode是地址-不久前我读了OpenJDK的哈希代码生成源代码，我记得它有点复杂。也许，这还不能保证良好的发行。但是，这在某种程度上是没有意义的，因为在hashmap中用作键的类很少使用默认的hashcode-它们提供自己的实现，这应该是很好的。最重要的是，您可能不知道的是(同样，这是基于读取源代码-不能保证)的是，HashMap在使用它之前先搅拌散列，将整个单词的熵混合到底部位中，这是除了最大的hashmap之外，所有人都需要它的地方。这有助于处理那些自己不这么做的散列，尽管我想不出任何常见的情况。最后，当表被重载时，它会退化为一组并行链表-性能变成O(N)。具体来说，通过链接的数量平均为负载系数的一半。

Answer 3

已经有人提到，hashmap是O(n/m)平均而言，如果n是项目数和m是大小。也有人提到，原则上，整件事可能会变成一个单独的链表。O(n)查询时间。(这都假定计算哈希值是常数时间)。然而，很少有人提到的是，至少有可能1-1/n(因此，对于1000件物品，这是99.9%的机会)最大的水桶将不会超过O(logn)！因此，匹配二进制搜索树的平均复杂度。(常数是好的，更紧的界限是(log n)*(m/n) + O(1)).这个理论界限所需要的就是使用一个相当好的散列函数(参见Wikipedia：通用散列..它可以很简单a*x>>m)。当然，给你哈希值的人不知道你是如何选择随机常量的。TL；DR：在极高的概率下，hashmap的最坏情况获取/放置的复杂性是O(logn).