10

只有当映射包含给定键时，我才想使用给定键的映射值做一些事情。我会天真地写：

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 实现，给定案例的性能如何变化？

注意：让我们假设地图中不允许空值。我不是在这里谈论渐近复杂性，这两个片段都是一样的

4

3 回答 3

8

Map是一个接口，因此实现类在如何实现每个操作方面有很大的自由度（完全可以编写一个缓冲最后一个条目的类，get如果它与最后一个相同，则可以允许对该操作进行恒定时间访问得到对象，使两者实际上等效，除了可能需要的比较）。

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

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

请注意，这HashMap.get是 O(1)（具有非常适合数据的散列函数）并且TreeMap.get是 O(log n)。因此，如果您在循环中进行了大量工作，并且Map不包含数百万个元素，则性能差异可能可以忽略不计。

但是，请注意文档中的免责声明Map.get：

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

于 2013-08-30T14:28:09.393 回答
4

要回答您的问题，
“给定案例的性能相对于 Map 实现有何变化？”
性能差异可以忽略不计。

要评论您的评论，
“在第二个片段中，我不喜欢在更广泛的范围内声明值的事实。”
好，你不应该。 你看，有两种方法可以从 Map 返回 null：

  1. 密钥不存在或
  2. 键确实存在，但它的值为空（如果 Map 实现允许空值，如 HashMap）。

因此，如果键以空值存在，这两种情况实际上可能会产生不同的结果！

编辑

我编写了以下代码来测试两种场景的性能：

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

所以总而言之，性能上的差异可以忽略不计。

于 2013-08-30T14:34:40.027 回答
1

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

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

然而，第二种方法有一个危险：如果我把它放在地图上怎么办：

map.put("null", null);

然后 map.get("null") 将返回 null ，您会将其视为 "null" 未映射，而 map.contains("null") 将返回 true ！

于 2013-08-30T14:27:03.243 回答