TreeMap是Java集合框架中基于红黑树实现的有序映射，它存储的键值对会按照键的自然顺序或者自定义比较器顺序进行排序。TreeMap提供了一个键集视图，也就是通过keySet方法返回的一个Set集合，这个集合包含了TreeMap中所有的键，很多场景下我们会调用这个键集视图的contains方法来判断某个键是否存在于TreeMap中。
TreeMap的底层数据结构基础
TreeMap的核心底层结构是红黑树，红黑树是一种自平衡的二叉查找树，它满足以下特性：
- 每个节点要么是红色，要么是黑色
- 根节点是黑色的
- 每个叶子节点（空节点）是黑色的
- 如果一个节点是红色的，那么它的两个子节点都是黑色的
- 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
红黑树的这些特性保证了它的最长路径不会超过最短路径的两倍，因此相关的增删改查操作都能保持稳定的性能。
键集视图contains方法的实现逻辑
首先我们来看TreeMap的keySet方法返回的是什么样的对象，查看JDK源码可以发现，TreeMap的keySet方法返回的是一个KeySet内部类的实例，这个KeySet继承了AbstractSet类。
KeySet的contains方法的实现逻辑如下：
// TreeMap内部KeySet类的contains方法实现
public boolean contains(Object o) {
// 直接调用TreeMap的containsKey方法
return TreeMap.this.containsKey(o);
}
接下来看TreeMap的containsKey方法的实现：
// TreeMap的containsKey方法实现
public boolean containsKey(Object key) {
// 调用getEntry方法查找对应的节点
return getEntry(key) != null;
}
核心的查找逻辑在getEntry方法中，该方法的源码如下：
// TreeMap的getEntry方法实现
final Entry<K,V> getEntry(Object key) {
// 如果有自定义的比较器，使用比较器进行比较查找
if (comparator != null)
return getEntryUsingComparator(key);
// 如果没有比较器，键需要实现Comparable接口
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 从根节点开始遍历红黑树，进行二叉查找
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
从代码可以看出，getEntry方法的查找过程和普通的二叉查找树查找逻辑一致，从根节点出发，比较目标键和当前节点键的大小，小于当前节点键就往左子树走，大于就往右子树走，相等就返回当前节点，直到遍历到空节点说明不存在该键。
时间复杂度推导
红黑树是一种平衡的二叉查找树，它的高度为O(log n)，其中n是红黑树中节点的数量，也就是TreeMap中键值对的数量。因为getEntry方法的查找过程是从根节点开始，每次比较后都会向下走一层，最多需要遍历的高度层数，所以getEntry方法的时间复杂度是O(log n)。
而键集视图的contains方法直接调用了TreeMap的containsKey方法，containsKey方法又直接调用了getEntry方法，中间没有额外的循环或者复杂操作，因此TreeMap键集视图的contains方法的时间复杂度就是O(log n)。
与其他结构的对比
我们可以把TreeMap键集视图的contains方法和其他常见结构的同类方法做对比：
| 结构类型 | 对应方法 | 时间复杂度 |
|---|---|---|
| HashMap | 键集视图contains方法 | O(1)（理想情况，无哈希冲突） |
| TreeMap | 键集视图contains方法 | O(log n) |
| ArrayList | contains方法 | O(n) |
可以看出TreeMap的键集视图contains方法的时间复杂度介于HashMap和ArrayList之间，虽然比HashMap的O(1)要高，但是它能保证键的有序性，适合需要有序遍历或者范围查找的场景。
注意事项
在使用TreeMap键集视图的contains方法时，需要注意以下几点：
- 如果TreeMap没有指定自定义比较器，那么键必须实现
Comparable接口，否则调用contains方法时如果传入的键没有实现该接口，会抛出ClassCastException - TreeMap不允许键为null，因为红黑树的查找需要调用键的比较方法，null无法调用比较方法，所以传入null调用contains方法会抛出NullPointerException
- 虽然时间复杂度是O(log n)，但是红黑树的常数开销比HashMap要高，所以在不需要有序性的场景下，优先选择HashMap性能会更好
总结来说，TreeMap键集视图的contains方法的时间复杂度为O(log n)，这个复杂度是由其底层的红黑树结构决定的，开发者可以根据实际场景的需求选择是否使用TreeMap。
TreeMap键集视图contains方法时间复杂度修改时间：2026-06-30 15:21:32