HashMap获取/放置复杂度 [英] HashMap get/put complexity

问题描述

我们习惯说，$（$）code> HashMap get / put 操作是O（1）。但是这取决于哈希实现。默认对象哈希实际上是JVM堆中的内部地址。我们是否确信这是足够好的，声称 get / put 是O（1）？

We are used to saying that HashMap get/put operations are O(1). However it depends on the hash implementation. The default object hash is actually the internal address in the JVM heap. Are we sure it is good enough to claim that the get/put are O(1) ?

可用内存是另一个问题。根据我从javadocs中了解到， HashMap 负载因子应为0.75。如果我们在JVM中没有足够的内存，并且加载因子超出限制，那么该如何？

Available memory is another issue. As I understand from the javadocs, the HashMap load factor should be 0.75. What if we do not have enough memory in JVM and the load factor exceeds the limit ?

像O（1）不能保证。是否有意义或者我缺少某些东西？

So, it looks like O(1) is not guaranteed. Does it make sense or am I missing something ?

推荐答案

这取决于很多事情。通常情况下，O（1）具有一个体面的哈希，它本身就是恒定的时间...但是如果有的话，你可能需要花费很长时间才能计算出是在哈希映射中的多个项目返回相同的哈希码， get 将不得不迭代他们调用等于每个人都可以找到一个匹配。

It depends on many things. It's usually O(1), with a decent hash which itself is constant time... but you could have a hash which takes a long time to compute, and if there are multiple items in the hash map which return the same hash code, get will have to iterate over them calling equals on each of them to find a match.

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

In the worst case, a HashMap has an O(n) lookup due to walking through all entries in the same hash bucket (e.g. if they all have the same hash code). Fortunately, that worst case scenario doesn't come up very often in real life, in my experience. So no, O(1) certainly isn't guaranteed - but it's usually what you should assume when considering which algorithms and data structures to use.

在JDK 8中， code> HashMap 已被调整，以便如果可以比较密钥进行排序，则任何密集填充的桶将被实现为一棵树，这样即使有很多条目相同哈希码，复杂度为O（log n）。这可能会导致问题，如果你有一个关键类型，其中平等和排序是不同的，当然。

In JDK 8, HashMap has been tweaked so that if keys can be compared for ordering, then any densely-populated bucket is implemented as a tree, so that even if there are lots of entries with the same hash code, the complexity is O(log n). That can cause issues if you have a key type where equality and ordering are different, of course.

是的，如果你没有足够的内存的哈希映射你会遇到困难的，但是无论你使用什么数据结构，这都是真的。

And yes, if you don't have enough memory for the hash map, you'll be in trouble... but that's going to be true whatever data structure you use.

这篇关于HashMap获取/放置复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！