深入理解TreeMap键集视图contains()方法的时间复杂度

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    // ... 其他成员和方法

    public Set<K> keySet() {
        return navigableKeySet();
    }

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

    // ... 其他成员和方法

    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
        private final NavigableMap<E, ?> m; // 持有对底层TreeMap的引用
        KeySet(NavigableMap<E,?> map) { m = map; }

        // ... 其他Set方法

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

        // ... 其他Set方法
    }

    // ... 其他成员和方法
}

import java.util.Map;
import java.util.TreeMap;

public class TreeMapKeySetComplexity {
    public static void main(String[] args) {
        Map<String, Integer> map1 = new TreeMap<>();
        map1.put("apple", 1);
        map1.put("banana", 2);
        map1.put("cherry", 3);
        map1.put("date", 4);
        map1.put("elderberry", 5);

        String searchKey = "cherry";

        // 使用keySet().contains() 查找
        long startTime1 = System.nanoTime();
        boolean found1 = map1.keySet().contains(searchKey);
        long endTime1 = System.nanoTime();
        System.out.println("keySet().contains('" + searchKey + "'): " + found1 + 
                           ", Time taken: " + (endTime1 - startTime1) + " ns");

        // 直接使用containsKey() 查找
        long startTime2 = System.nanoTime();
        boolean found2 = map1.containsKey(searchKey);
        long endTime2 = System.nanoTime();
        System.out.println("containsKey('" + searchKey + "'): " + found2 + 
                           ", Time taken: " + (endTime2 - startTime2) + " ns");

        // 尝试一个不存在的键
        String nonExistentKey = "grape";
        boolean found3 = map1.keySet().contains(nonExistentKey);
        System.out.println("keySet().contains('" + nonExistentKey + "'): " + found3);
    }
}