Java中HashMap.containsKey()为何能实现常数时间运行？

你看到的遍历是最坏情况下的场景，但HashMap的containsKey()（本质是调用getNode()）的平均时间复杂度是O(1)，核心原因在于这几点：

1. 直接定位桶位置
   源码里第一步通过(n - 1) & hash(key)计算出哈希桶的索引，直接从数组tab中取出对应的桶节点，这一步是纯常数时间操作，没有遍历。

2. 哈希冲突的控制
   只有当多个key的哈希值冲突、落到同一个桶里时，才需要遍历桶内的链表/红黑树：

   • 如果桶是红黑树结构（当链表长度超过8时自动转换），查找的时间复杂度是O(log k)，k是桶内元素数，这个值通常很小，接近常数
   • 如果是链表，HashMap会通过自动扩容机制（当负载因子超过阈值时扩容数组）保证链表长度不会过长（默认链表长度少于6时转回链表），所以平均下来遍历的元素数量极少，几乎可以忽略

3. 平均情况vs最坏情况
   你看到的do-while遍历是极端情况——比如所有key的哈希值都冲突、落到同一个桶里，这时候时间复杂度会退化成O(n)。但这种情况在实际开发中几乎不会出现，因为HashMap的hash()方法会尽量打散哈希值，加上扩容机制的兜底，保证了绝大多数情况下的操作都是常数时间。

简单说：containsKey()的核心是先通过哈希直接定位桶，再在桶内做极小范围的查找，所以平均下来是常数时间。

附上你提供的源码（已格式化）：

/**
 * 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;
}

内容的提问来源于stack exchange，提问作者Brendan B