0

This is the documentation for HashMap.containsKey(). As you can see, it uses getNode(). I could be wrong, but it looks like the the hash map is still being iterated through, which would be linear time.

/**
 * Implements Map.get and related methods.
 *
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

/**
 * Returns {@code true} if this map contains a mapping for the
 * specified key.
 *
 * @param   key   The key whose presence in this map is to be tested
 * @return {@code true} if this map contains a mapping for the specified
 * key.
 */
public boolean containsKey(Object key) {
    return getNode(key) != null;
}
Brendan B
  • 7
  • 2
  • 1
    First, note [the `HashMap` documentation](https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/HashMap.html) states: "_This implementation provides constant-time performance for the basic operations (get and put), **assuming the hash function disperses the elements properly among the buckets**_". And this is exactly why. The linked list you're seeing in the code is how `HashMap` handles two keys that hash to the same bucket. Figuring out which bucket to look at is still constant time, however. And you're _likely_ still not iterating the entire key set. – Slaw May 23 '23 at 04:52
  • This is [well known](https://stackoverflow.com/q/4553624/555045) but also note that eventually a [tree is used instead of a linked list](https://stackoverflow.com/q/31373648/555045) (this is also visible in the code you quoted, but it doesn't show the conditions under which the tree is created) – harold May 23 '23 at 04:55
  • So, yes, if somehow every key was hashed to the same bucket, then the performance degrades to O(n). Though if enough keys are hashed to the same bucket, then `HashMap` switches from a linked list to a balanced tree which, if I'm not mistaken, keeps the performance to O(log(n)). – Slaw May 23 '23 at 04:56

0 Answers0