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

问题描述

我们习惯说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 将必须遍历它们，对每个项目调用 equals 以找到匹配项.

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 中，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屋！