Time complexity analysis of keySet().contains() method in TreeMap

This article deeply explores the time complexity of calling the `contains()` method of the `Set` view obtained through `keySet()` in Java `TreeMap`. By analyzing the source code of `TreeMap`, we revealed that this operation actually delegates the call to the underlying `TreeMap.containsKey()` method. Therefore, its time complexity is consistent with `TreeMap`'s search operation based on red-black trees, which is O(log N), rather than O(1) for some hash sets.

Understand the keySet() method of TreeMap

In Java, TreeMap is an ordered collection of key-value pairs, which is internally implemented through a red-black tree and can maintain the sorting of keys. TreeMap provides the keySet() method, which returns a Set view containing all keys. The important thing is that this Set is not an independent new set with all keys copied, but a "view". This means that any operation on this Set view will actually be reflected on its underlying TreeMap.

When we call the contains() method on the Set view returned by TreeMap's keySet(), for example:

 Map<string integer> map = new TreeMap();
map.put("apple", 1);
map.put("banana", 2);
map.keySet().contains("apple");</string>

Many developers may wonder about its time complexity. Since HashSet's contains() operation is usually O(1), while TreeSet's contains() operation is O(log N), this "view" nature makes the situation less intuitive.

Go deep into the delegation mechanism of keySet().contains()

In order to clarify the time complexity of keySet().contains(), we need to view the source code of TreeMap. OpenJDK's implementation clearly shows its inner workings.

TreeMap's keySet() method actually returns a NavigableSet, specifically an instance of TreeMap's internal static class KeySet. This KeySet class overrides the contains() method and delegates it to the underlying TreeMap instance.

Here is the relevant simplified source code snippet:

 public class TreeMap<k> extends AbstractMap<k> implements NavigableMap<k>, Cloneable, java.io.Serializable {

    // ...other members and methods...

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

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

    // ...other members and methods...

    static final class KeySet<e> extends AbstractSet<e> implements NavigableSet<e> {
        private final NavigableMap<e> m; // Holds a reference to the external TreeMap KeySet(NavigableMap<e> map) {
            m = map;
        }

        // ...other methods...

        public boolean contains(Object o) {
            return m.containsKey(o); // <p> It can be clearly seen from the above code that the contains(Object o) method of the KeySet class does not implement the search logic itself, but directly calls the containsKey(o) method of its internally held NavigableMap m (that is, the external TreeMap instance).</p>
<h3> Time complexity analysis</h3>
<p> Since map.keySet().contains(xyz) is equivalent to map.containsKey(xyz), its time complexity depends entirely on the TreeMap.containsKey() method.</p>
<p> The bottom layer of TreeMap is implemented based on red-black tree (a self-balancing binary search tree). In a red-black tree, finding an element requires starting from the root node and traversing down the path of the tree until the target element is found or determined not to exist. For a red-black tree containing N elements, its height is O(log N). Therefore, the time complexity of the lookup operation (including containsKey) is <strong>O(log N)</strong> .</p>
<h3> Conclusion and Notes</h3>
<p> To sum up, when you call the contains() method on the TreeMap's keySet() view, its time complexity is <strong>O(log N)</strong> . This is because the operation is delegated to the underlying TreeMap.containsKey() method, and the search efficiency of TreeMap is determined by its red-black tree structure.</p>
<p> <strong>Summary of key points:</strong></p>
<ul>
<li> TreeMap.keySet() returns a view, not an independent collection.</li>
<li> The contains() method of this view will delegate to the underlying TreeMap.containsKey() method.</li>
<li> TreeMap is implemented based on red-black trees, and the time complexity of its containsKey() operation is O(log N).</li>
<li> Therefore, the time complexity of map.keySet().contains(key) is also O(log N).</li>
</ul>
<p> Understanding this delegation mechanism is crucial to accurately evaluate the performance of Java collection operations. Different Map implementations (such as HashMap) have different time complexity of keySet().contains() because their underlying search mechanisms are different (HashMap is based on a hash table, usually O(1)). Therefore, when choosing a collection type and evaluating performance, it is important to consider its underlying data structure and operation implementation.</p></e></e></e></e></e></k></k></k></k></k></k>

The above is the detailed content of Time complexity analysis of keySet().contains() method in TreeMap. For more information, please follow other related articles on the PHP Chinese website!