java - Java - HashMap.get() 调用有多贵？

Question

HashMap.get() 调用有多贵？有问题的地图包含数百个映射，我希望在每秒 60-1200 次之间的任何地方调用 .get() 。

Answer 1

HashMap.get()是平均O(1)的，这意味着它非常有效。这种效率可能会略有下降，具体取决于 HashMap 中的元素数量，但仍然应该非常有效。

如果您想获得良好的性能，您应该注意正确实现键的哈希码方法，以便对象在映射的存储桶中均匀分布。

这与 HashMap 的工作方式有关 - 稍微简化了一点。

Every object in Java has a hashCode() and equals() methods. When you put a value to the HashMap, it would calculate the bucket to which it belongs. This is done based on the key passed to the put(key,value) method. HashMap uses the value returned by the hashCode() method of the key.

If you had only keys returning distinct hash codes (and if you had infinite number of buckets), HashMap could tell exactly which key+value pair lives in which bucket, but it's not the case.

There could be multiple keys returning the same hash code (leading to placing them in the same bucket), therefore when HashMap finds the correct bucket, with more than one element, it will iterate over all keys and use equals() to find the one, which was requested. The less, elements in the bucket the faster the check.

Therefore the better the hashCode() implementations, the less collisions, the better performance. Of course the more elements you put to the HashMap, the more likely it is that the collision will occur.

Answer 2

这取决于您有多少碰撞（碰撞可以将其效率从 O(1) 推到 O(N)）以及 hash-set/map/table 包含的任何对象的 hashCode() 方法的实现。

您应该编写一个简单的基准来测试它是否需要太长时间。使用字符串 hashCode() 拒绝服务

long start = System.currentTimeMillis()

...Process hashmap gets here

long time = System.currentTimeMillis()-start;
System.out.println("Took "+time+"ms");

Answer 3

这取决于地图中元素的数量及其哈希码分布。如果哈希码是均匀分布的，则获取元素的复杂度为 O(1)。

HashMap 中的数百个元素在相当现代的机器上应该不是什么大问题，如果只有几个哈希码冲突，它应该是毫秒（或更短）的问题。只需测量以确保。

Answer 4

Like most hash table implementations, HashSet operates in constant time (O(1)) for add, remove, and contains operations assuming that your objects have a well-behaved hash function. That means that it takes roughly the same amount of time regardless of the size of the hash set.

For the purpose of the above, a "well-behaved" hash function is one that always calculates the same hash, in constant time, given the same input object, and different hash values for different objects (reducing "hash collisions").

Roughly speaking, hash maps work by calculating a hash code very quickly and only checking the hash bucket that should contain the relevant element. Because calculating the hash code should be constant time (and very fast in practice), and accessing a bucket should be constant time (and very fast in practice), a HashMap is one of the most efficient map implementations out there.