地图查找性能

Question

如果一个map中包含给定的键，我想要使用该键对应的值来做一些事情。朴素的想法是：

Map<String, String> myMap = ...;

if(myMap.containsKey(key)) {
  String value = myMap.get(key);

  // Do things with value
}

上面的代码看起来很容易理解，但从性能的角度来看，以下代码是否更好呢？

Map<String, String> myMap = ...;

String value = myMap.get(key);

if(value != null) {
  // Do things with value
}

在第二个代码片段中，我不喜欢value声明了更广泛的作用域。

给定情况下，Map实现的性能如何变化？

注意: 假设地图中不允许空值。这里不涉及渐近复杂度，两个代码片段的渐近复杂度相同。

- cyberz

---

你为什么在这里担心性能问题？ - Sotirios Delimanolis

@SotiriosDelimanolis我认为他只是引入了一个简单的场景。想象一下，以下代码将在循环中执行一百万次。 - Dmitry Zaytsev

请记住，这还取决于您使用的地图实现方式。例如，在“HashMap”中的“Hash”部分并非无用。这样做似乎太过于早期优化了。 - Fritz

@Gamb：我忘记在最后一个字符之前加上“实现”这个词了。 - cyberz

@Sambuca：我在想这两者之间的复杂度权衡（我预计它是地图大小和实现方式的函数）？ - cyberz

Answer 1

Map 是一个接口，因此实现类在实现每个操作时有相当大的自由度（完全可以编写一个缓冲最后一个条目的类，如果它与上次获取的对象相同，则可能允许常数时间访问 get 操作，使两者在实际上等价，除了可能需要比较）。

例如对于 TreeMap 和 HashMap，containsKey 本质上只是一个带有 null 检查的 get 操作（更具体地说是 getEntry）。

因此，对于这两个容器，第一个版本应该需要大约两倍的时间，与第二个版本相比（假设在两种情况下使用相同类型的 Map）。

请注意，HashMap.get 的时间复杂度为 O(1)（具有适合数据的哈希函数），而 TreeMap.get 的时间复杂度为 O(log n)。因此，如果在循环中执行任何重要的工作，并且 Map 不包含数量级在百万级别的元素，则性能差异可能是微不足道的。

然而，请注意文档中关于Map.get的免责声明：

如果此映射允许空值，则返回null并不一定表示该映射未包含键的映射；也可能是该映射将键显式映射到null。可以使用containsKey操作来区分这两种情况。

- Bernhard Barker

---

你开始得很好，但请详细说明TreeMap（O(log n)）和HashMap（O(1)）之间的区别。使用HashMap时，计算键的哈希码以确定桶号码，这些操作与元素数量无关。而使用TreeMap时，需要分析根节点，并对每个不匹配项从可匹配项中丢弃一半的树。虽然它们在查找方面表现不同，但有时较慢的查找会由于其他领域的更好性能而更优秀。 - Edwin Buck

@EdwinBuck 进行了一些编辑。虽然我并不打算让这个答案集中在TreeMap和HashMap之间的区别上（OP没有表明想要这样做，而且我相信已经有足够多的这样的分析了），更多的是关于两个提供的代码示例之间的区别。 - Bernhard Barker

明白，是的，在许多地方广为宣传了O性能差异; 但是，考虑到需要解释Map是一个接口，具有许多可能的实现，我在谨慎方面出错了，认为他可能没有意识到大O符号（仅提及它也是一个入门点）。 - Edwin Buck

@EdwinBuck：这正是问题所在：（大O）复杂度与地图实现的关系。 - cyberz

Answer 2

回答你的问题：
“给定案例的性能如何随着Map实现的变化而变化？”
性能差异可以忽略不计。 针对您的评论进行评论：
“在第二个代码片段中，我不喜欢value被声明为更广泛的作用域。”
好的，你不应该这样做。 您看，从Map中获取null有两种方法：

1. 键不存在 或 2. 键存在，但其值为null（如果Map实现允许null值，例如HashMap）。

所以，如果键存在且值为null，则这两种情况可能实际上具有不同的结果！ 编辑 我编写了以下代码来测试两种场景的性能：

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();
    }

}

我运行了它，结果如下：

Key Exists: 9901
Value Null: 11472
Key Exists: 11578
Value Null: 9387

因此，总的来说，性能差异可以忽略不计。

- James Dunn

Answer 3

显然第二个版本的性能更高：您只需要在地图中查找键一次，而在第一个版本中，您需要查找两次，因此计算键的哈希码两次并查找哈希桶，假设您正在使用哈希映射。

您可以有完全不同的Map接口实现，能够更好地处理此类代码，通过记住与上一次contains方法调用链接到键的映射条目，如果后续get使用相同的键（使用==运算符），则可以立即从记忆的映射条目返回关联值。

但是第二种方法存在危险：如果我将这个放入映射中：

map.put("null", null);

然后，map.get("null") 将返回 null，你会将它视为 "null" 没有被映射，而 map.contains("null") 将返回 true！

- GerritCap

---

第二个问题只有在允许null存在于映射中时才会成为问题。 - cHao