理解TreeMap的keySet().contains()方法的时间复杂度

本文深入探讨了`treemap`的`keyset().contains()`方法的时间复杂度。通过分析openjdk源码，我们揭示了该方法实际上委托给底层`treemap`的`containskey()`方法。因此，其时间复杂度与`treemap`的其他基于键的操作一致，为o(log n)，而非某些`set`实现（如`hashset`）的o(1)。文章强调了集合视图（view）的性能特性与其底层数据结构紧密相关的原则。

在Java集合框架中，理解不同数据结构的操作时间复杂度对于编写高效代码至关重要。当涉及到Map接口的keySet()方法返回的Set视图时，其contains()操作的时间复杂度常常引起混淆，尤其是对于基于树的实现如TreeMap。

集合视图与底层实现

java.util.Map接口提供了keySet()方法，它返回一个包含所有键的Set视图。这个“视图”的概念至关重要，因为它意味着这个Set并不是一个独立的数据结构，而是对原始Map的一种封装，其操作通常会委托给底层的Map。

对于常见的Set实现，contains()方法的时间复杂度有所不同：

• HashSet和LinkedHashSet：由于它们内部使用哈希表，contains()操作的平均时间复杂度为O(1)。
• TreeSet：由于它内部使用红黑树（一种自平衡二叉查找树），contains()操作的时间复杂度为O(log N)，其中N是集合中的元素数量。

鉴于TreeMap本身也是基于红黑树实现的，其键的查找操作（如containsKey()）的时间复杂度为O(log N)。那么，TreeMap的keySet().contains()操作是否会继承TreeSet的O(log N)特性，还是由于某种优化而达到O(1)呢？

TreeMap的keySet().contains()源码分析

为了明确TreeMap的keySet().contains()方法的实际行为，我们需要查看其内部实现。OpenJDK的源码清晰地揭示了这一点。

TreeMap类定义了keySet()方法，它返回一个NavigableSet类型的视图：

虎课网

虎课网是超过1800万用户信赖的自学平台，拥有海量设计、绘画、摄影、办公软件、职业技能等优质的高清教程视频，用户可以根据行业和兴趣爱好，自主选择学习内容，每天免费学习一个...

下载

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable {
    // ...

    public Set keySet() {
        return navigableKeySet();
    }

    public NavigableSet navigableKeySet() {
        KeySet nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }

    // ...
}

这里返回的实际上是TreeMap内部的一个静态嵌套类KeySet的实例。这个KeySet类实现了NavigableSet接口，并且其contains()方法的实现如下：

    static final class KeySet extends AbstractSet implements NavigableSet {
        private final NavigableMap m; // m 是底层TreeMap的引用
        KeySet(NavigableMap map) { m = map; }

        // ...

        public boolean contains(Object o) { 
            return m.containsKey(o); // 关键：委托给底层Map的containsKey()方法
        }

        // ...
    }

从上述源码可以看出，KeySet的contains(Object o)方法并没有自己实现查找逻辑，而是直接调用了其内部持有的底层NavigableMap（即TreeMap实例）的containsKey(o)方法。

时间复杂度结论

由于TreeMap的containsKey()方法是基于红黑树实现的，其查找操作的时间复杂度为O(log N)。因此，map1.keySet().contains(xyz)的调用链最终会执行map1.containsKey(xyz)，其时间复杂度也必然是O(log N)。

这与直接调用TreeMap的containsKey()方法在性能上是完全等价的：

Map map1 = new TreeMap<>();
// ... 填充map1 ...

// 以下两种操作的时间复杂度完全相同，均为 O(log N)
boolean result1 = map1.keySet().contains("someKey");
boolean result2 = map1.containsKey("someKey");

注意事项与总结

1. 视图的特性继承：集合视图（如keySet()、values()、entrySet()）的性能特性直接继承自其底层数据结构。这意味着，如果底层Map是HashMap，那么keySet().contains()的平均时间复杂度为O(1)；如果底层是TreeMap，则为O(log N)。
2. 避免误解：不要因为keySet()返回的是一个Set接口，就想当然地认为它会具备所有Set实现（例如HashSet）的最佳性能特性。始终要考虑其背后的实际实现。
3. 代码清晰度：在处理TreeMap的键是否存在时，直接使用map.containsKey(key)通常比map.keySet().contains(key)更为直观和清晰，尽管两者的性能表现相同。

综上所述，当您在TreeMap的keySet()视图上调用contains()方法时，其时间复杂度是O(log N)，因为它内部委托给了TreeMap的containsKey()方法，而TreeMap是基于红黑树实现的。理解这一机制有助于开发者更准确地评估代码性能，并做出明智的集合选择。