Java 地图查找性能
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18535088/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Map lookup performance
提问by cyberz
I'd like to do something using a map value for a given key only if the map contains the given key. Naively I would write:
只有当地图包含给定的键时，我才想使用给定键的映射值做一些事情。天真地我会写：
Map<String, String> myMap = ...;
if(myMap.containsKey(key)) {
String value = myMap.get(key);
// Do things with value
}
The code above looks easy to understand, but from a performance point of view, wouldn't it be better the following code?
上面的代码看起来很容易理解，但是从性能的角度来看，下面的代码不是更好吗？
Map<String, String> myMap = ...;
String value = myMap.get(key);
if(value != null) {
// Do things with value
}
In the second snippet I don't like the fact that valueis declared with a wider scope.
在第二个片段中，我不喜欢value以更广泛的范围声明的事实。
How does the performance of given cases change with respect to the Map implementation?
给定案例的性能如何相对于 Map 实现而变化？
Note: Let's assume that null values are not admitted in the map. I'm not talking about asymptotic complexity here, which is the same for both snippets
注意：假设地图中不接受空值。我不是在这里谈论渐近复杂性，这对于两个片段都是相同的
采纳答案by Bernhard Barker
Mapis an interface, so the implementing classes have quite a bit of freedom in how they implement each operation (it's entirely possible to write a class that buffers the last entry, which may allow constant time access for the getoperation if it's the same as the last gotten object, making the two practically equivalent, except for a presumably required comparison).
Map是一个接口，因此实现类在如何实现每个操作方面有相当多的自由（完全可以编写一个缓冲最后一个条目的类，get如果它与最后一个条目相同，这可能允许对操作进行恒定时间访问得到对象，使两者实际上等价，除了可能需要的比较）。
For TreeMapand HashMap, for example, containsKeyis essentially just a getoperation (more specifically getEntry) with a check for null.
例如，对于TreeMap和HashMap，containsKey本质上只是一个get操作（更具体地说是getEntry）并检查null。
Thus, for these two containers, the first version should take roughly twice as longas the second (assuming you use the same type of Mapin both cases).
因此，对于这两个容器，第一个版本的时间大约是第二个的两倍（假设您Map在两种情况下都使用相同类型的）。
Note that HashMap.getis O(1) (with a hash function well-suited to the data) and TreeMap.getis O(log n). So if you do any significant amount of work in the loop, and the Mapdoesn't contain in the order of millions of elements, the difference in performance is likely to be negligible.
请注意，它HashMap.get是 O(1)（具有非常适合数据的散列函数）并且TreeMap.get是 O(log n)。因此，如果您在循环中进行了大量工作，并且Map不包含数百万个元素，则性能差异可能可以忽略不计。
However, note the disclaimer in the docsfor Map.get:
但是，请注意在免责声明中的文档进行Map.get：
If this map permits null values, then a return value of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null. The containsKey operation may be used to distinguish these two cases.
如果此映射允许空值，则返回 null 值不一定表示该映射不包含该键的映射；地图也有可能将键显式映射到空值。containsKey 操作可用于区分这两种情况。
回答by GerritCap
Obviously the 2nd version is more performant: you only lookup the key in the map once while in the first version you look it up twice hence calculating twice the hashcode of the key and looking in the hashbuckets, assuming that you are using a hashmap of course.
显然，第二个版本的性能更高：您只在地图中查找键一次，而在第一个版本中您查找两次，因此计算两次键的哈希码并查看哈希桶，当然假设您使用的是哈希图.
You can have a completely different implementation of the Map interface that would be able to handle this kind of code much better by remembering the map entry that was linked to the key in the last contains method call, if the the subsequent get uses the same key (using the == operator) you can then immedialtely return the associated value from the remembered map entry.
您可以拥有完全不同的 Map 接口实现，如果后续 get 使用相同的键，则可以通过记住在最后一个 contains 方法调用中链接到键的映射条目来更好地处理此类代码（使用 == 运算符）然后您可以立即从记住的映射条目中返回关联的值。
However there is a danger in the 2nd method: what if I put this in the map:
但是，第二种方法存在危险：如果我将其放在地图中会怎样：
map.put("null", null);
then map.get("null") would return null and you would treat it as "null" is not mapped while map.contains("null") would return true !
然后 map.get("null") 将返回 null 并且您将其视为未映射的 "null" 而 map.contains("null") 将返回 true ！
回答by James Dunn
To answer your question,
"How does the performance of given cases change with respect to the Map implementation?"
The performance difference is negligible.
回答您的问题，
“给定案例的性能如何随 Map 实现而变化？”
性能差异可以忽略不计。
To comment on your comment,
"In the second snippet I don't like the fact that value is declared with a wider scope."
Good, you shouldn't.You see, there are two ways to get null returned from a Map:
要评论您的评论，
“在第二个片段中，我不喜欢以更广泛的范围声明值的事实。”
很好，你不应该。你看，有两种方法可以让 Map 返回 null：
- The key doesn't exist OR
- The key does exist, but its value is null (if the Map implementation allows null values, like HashMap).
- 密钥不存在或
- 键确实存在，但它的值为空（如果 Map 实现允许空值，如 HashMap）。
So the two scenarios could actually have different results if the key existed with a null value!
因此，如果键存在空值，这两种情况实际上可能会产生不同的结果！
EDIT
编辑
I wrote the following code to test out the performance of the two scenarios:
我编写了以下代码来测试两种场景的性能：
public class TestMapPerformance {
static Map<String, String> myMap = new HashMap<String, String>();
static int iterations = 7000000;
// populate a map with seven million strings for keys
static {
for (int i = 0; i <= iterations; i++) {
String tryIt = Integer.toString(i);
myMap.put(tryIt, "hi");
}
}
// run each scenario twice and print out the results.
public static void main(String[] args) {
System.out.println("Key Exists: " + testMap_CheckIfKeyExists(iterations));
System.out.println("Value Null: " + testMap_CheckIfValueIsNull(iterations));
System.out.println("Key Exists: " + testMap_CheckIfKeyExists(iterations));
System.out.println("Value Null: " + testMap_CheckIfValueIsNull(iterations));
}
// Check if the key exists, then get its value
public static long testMap_CheckIfKeyExists(int iterations) {
Date date = new Date();
for (int i = 0; i <= iterations; i++) {
String key = Integer.toString(i);
if(myMap.containsKey(key)) {
String value = myMap.get(key);
String newString = new String(value);
}
}
return new Date().getTime() - date.getTime();
}
// Get the key's value, then check if that value is null
public static long testMap_CheckIfValueIsNull(int iterations) {
Date date = new Date();
for (int i = 0; i <= iterations; i++) {
String key = Integer.toString(i);
String value = myMap.get(key);
if(value != null) {
String newString = new String(value);
}
}
return new Date().getTime() - date.getTime();
}
}
I ran it and this was the result:
我运行它，这是结果：
Key Exists: 9901
Value Null: 11472
Key Exists: 11578
Value Null: 9387
So in conclusion, the difference in performance in negligible.
所以总而言之，性能上的差异可以忽略不计。
