TreeMap的keySet视图contains()方法时间复杂度是多少？

你的猜测完全正确：TreeMap的keySet()返回的Set视图调用contains()方法的时间复杂度是O(log(N))，并非O(1)。

核心原因： #

• TreeMap的keySet()返回的是一个内部视图类（TreeMap.KeySet），它没有独立的存储容器，所有操作都会直接委托给底层的TreeMap实例。
• 当调用这个视图的contains(Object o)时，实际会调用TreeMap的containsKey(Object o)方法，而TreeMap基于红黑树实现，红黑树的查找操作时间复杂度就是O(log(N))。
• 你提到的HashSet/LinkedHashSet的O(1)复杂度，是因为它们依赖HashMap的哈希定位；而TreeMap的keySet视图虽然不是TreeSet，但两者底层共享红黑树的查找逻辑，所以复杂度和TreeSet的contains()一致。

源码佐证（以Java 6为例）： #

TreeMap内部的KeySet类实现contains方法时直接复用了TreeMap的containsKey：

public boolean contains(Object o) {
    return containsKey(o);
}

而TreeMap的containsKey方法会执行红黑树的节点查找，时间复杂度为O(log(N))。

内容的提问来源于stack exchange，提问作者ylr