地图查找性能

Question

仅当地图包含给定键时,我才想使用给定键的映射值执行某些操作.天真我会写:

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

注意:我们假设地图中不允许使用空值.

Answer 1

Map是一个接口,所以实现类在如何实现每个操作方面都有相当大的自由(完全有可能编写一个缓冲最后一个条目的类,get如果它与最后一个条目相同,则可以允许对该操作进行恒定时间访问.获得了对象,使两者几乎等效,除了可能需要的比较).

例如,对于TreeMap和基本上只是一个检查的操作(更具体地说).HashMapcontainsKeygetgetEntrynull

因此,对于这两个容器,第一个版本应该花费大约两倍的时间(假设Map在两种情况下使用相同类型).

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

但是,请注意在免责声明中的文档进行Map.get:

如果此映射允许空值,则返回值null不一定表示映射不包含该键的映射; 地图也可能将键明确映射为null.containsKey操作可用于区分这两种情况.