HashMap得到/放置复杂性

Question

我们习惯说HashMap get/put操作是O(1).但是它取决于哈希实现.默认对象哈希实际上是JVM堆中的内部地址.我们是否确定声称get/putO(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(log N).当然,如果你有一个密钥类型,其中相等和排序是不同的,那么这可能会导致问题.

是的,如果你没有足够的内存用于哈希映射,你就会遇到麻烦......但无论你使用什么数据结构,这都是正确的.

Answer 2

我不确定默认的哈希码是地址 - 我刚刚读了OpenJDK源代码来生成哈希码,我记得它有点复杂.也许并不是保证良好分配的东西.但是,这在某种程度上没有实际意义,因为您在hashmap中用作键的几个类使用默认的哈希码 - 它们提供了自己的实现,这应该是好的.

最重要的是,你可能不知道的(再次,这是基于阅读源 - 它不能保证)是HashMap在使用之前激活哈希,将整个单词中的熵混合到底部位,这就是它的位置除了最大的哈希映射之外的所有需要.这有助于处理那些本身并没有这样做的哈希,尽管我无法想到你会看到的任何常见情况.

最后,当表重载时会发生什么,它会退化为一组并行链表 - 性能变为O(n).具体而言,遍历的链接数量平均为负载因子的一半.

Answer 3

已经提到过,哈希映射是O(n/m)平均的,如果n是项目数,则是m大小.还有人提到,原则上整个事情可能会崩溃成一个带有O(n)查询时间的单链表.(这都假设计算哈希是恒定时间).

然而,不经常提到的是,至少有概率1-1/n(因此对于1000件物品来说有99.9%的可能性),最大的桶不会被填充超过O(logn)!因此匹配二叉搜索树的平均复杂度.(而且常数是好的,更严格的约束(log n)*(m/n) + O(1)).

这个理论界限所需要的只是你使用一个相当好的哈希函数(参见维基百科:通用哈希.它可以很简单a*x>>m).当然,给你哈希值的人不知道你是如何选择随机常数的.

TL; DR:具有非常高的概率,最糟糕的情况是获取/放置散列映射的复杂性O(logn).

Answer 4

HashMap操作是hashCode实现的依赖因素.对于理想情况,可以说为每个对象提供唯一哈希码的良好哈希实现(无哈希冲突),那么最佳,最差和平均情况将是O(1).让我们考虑一个场景,其中hashCode的错误实现总是返回1或具有哈希冲突的此类哈希.在这种情况下,时间复杂度将是O(n).

现在谈到关于内存的问题的第二部分,那么JVM会照顾内存约束.

Answer 5

我同意：

O(1) 的一般摊销复杂度
一个糟糕的hashCode()实现可能会导致多次碰撞，这意味着在最坏的情况下，每个对象都进入同一个存储桶，因此如果每个存储桶都由 a 支持，则为O( N ) List。
从 Java 8 开始，HashMap用 TreeNodes（当列表大于 8 个元素时的红黑树）动态替换每个桶中使用的节点（链表），导致 O( logN )的最差性能。

但是，如果我们想要 100% 精确，这并不是全部事实。键的实现hashCode()和类型Object（不可变/缓存或作为集合）也可能会影响严格的实时复杂度。

让我们假设以下三种情况：

它们具有相同的复杂性吗？嗯，正如预期的那样，第一个的摊销复杂度是 O(1)。但是，对于其余部分，我们还需要计算hashCode()查找元素，这意味着我们可能必须在算法中遍历数组和列表。

让我们假设上述所有数组/列表的大小都是k。然后，HashMap<String, V>并且HashMap<List<E>, V>将具有 O(k) 摊销复杂度，类似地，Java8 中最坏的情况是O( k + logN )。

*请注意，使用String键是一种更复杂的情况，因为它是不可变的，而且 Java 将的结果缓存hashCode()在私有变量中hash，因此它只计算一次。

/** Cache the hash code for the string */
    private int hash; // Default to 0

但是，上面也有它自己的最坏情况，因为 Java 的String.hashCode()实现是hash == 0在计算之前检查 if hashCode。但是，嘿，有输出hashcode为零的非空字符串，例如“f5a5a608”，请参见此处，在这种情况下，记忆可能没有帮助。