-1

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.

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

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))?

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
ylr
  • 1
  • 2

1 Answers1

3

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.

knittl
  • 246,190
  • 53
  • 318
  • 364
  • 1
    This (or slight adoptions of this) should be true for any view onto any of the standard collections: They tend to be implemented in the most efficient way. I.e. if there's a simple mapping to the original collections methods, then you can safely assume that's what's being done. – Joachim Sauer Nov 30 '22 at 11:09