If I have a TreeSet and I use contains() on the Set view of keySet() is the time complexity O(1)?

Map<String, Integer> map1 = new TreeMap<>();
map1.keySet().contains(xyz);

I am wondering as for example contains() for HashSet and LinkedHashSet is O(1) but for a TreeSet is O(log(N)) but the keySet() method is not returning a HashSet, LinkedSet or TreeSet but just a Set view in general thus making me unsure.

Best regards

I checked here and here but could not find any performance related information.

EDIT: I have since found this question: What is a view of a collection? This makes me think the call of contains() is then made by the TreeMap and not the Set and would therefore be O(log(N))?

CodePudding user response：

map1.keySet().contains(xyz); is 100% identical to calling map1.containsKey(xyz);. You can verify it by looking at the source:

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    // […]

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

    /**
     * @since 1.6
     */
    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;
        KeySet(NavigableMap<E,?> map) { m = map; }

        // […]

        public boolean contains(Object o) { return m.containsKey(o); } // [<-- delegates back to map]

        // […]
    }

    // ...
}

=> The key set has the same runtime characteristics as the collection itself. In case of a TreeMap that's O(log(n)) for the contains operation.