为何Python3 dict.get()时间复杂度为O(1)，但底层实现似为O(n)？

我们都知道Python的dict.get()方法时间复杂度为O(1)，因为它通过计算键的哈希值来获取对应的值。但我有个疑问：如何通过哈希值直接访问对应的值？为找到答案，我查看了CPython中的do_lookup方法，发现解释器会遍历相关桶来查找所需的哈希值。

do_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key, Py_hash_t hash,
          Py_ssize_t (*check_lookup)(PyDictObject *, PyDictKeysObject *, void *, Py_ssize_t ix, PyObject *key, Py_hash_t))
{
    // ...
    for (;;) {
        ix = dictkeys_get_index(dk, i);
        if (ix >= 0) {
            Py_ssize_t cmp = check_lookup(mp, dk, ep0, ix, key, hash);
            if (cmp < 0) {
                return cmp;
            } else if (cmp) {
                return ix;
            }
        }
        else if (ix == DKIX_EMPTY) {
            return DKIX_EMPTY;
        }
        perturb >>= PERTURB_SHIFT;
        i = mask & (i*5 + perturb + 1);
        // ...
    }
}

结合哈希冲突解决机制，我总结的复杂度情况如下：

O(1) 仅为无冲突的最优情况
O(N) 为无冲突的最坏情况
O(N) + O(len(bucket)) 为存在冲突解决的最坏情况

请问我的逻辑是否存在遗漏或错误？

回答： #

你的观察方向没问题，但有几个关键细节需要纠正：

1. O(1)是平均时间复杂度，而非仅最优情况
   业界所说字典的O(1)复杂度，指的是平均情况——在正常哈希分布下，哪怕存在少量冲突，查找的平均步数也是常数级。最优情况（无冲突）确实是O(1)，但这不是O(1)表述的核心。

2. 复杂度表述存在错误

   • “无冲突的最坏情况O(N)”不成立：无冲突时每个哈希值对应唯一桶，查找直接命中，复杂度就是O(1)。
   • “O(N) + O(len(bucket))”表述冗余，哈希冲突解决时的遍历本质是在冲突的探测序列中查找，这个序列长度最坏会达到O(N)，直接表述为最坏情况O(N)即可，无需额外叠加。

3. 哈希表的“直接访问”是相对概念
   哈希表不是直接通过哈希值定位值，而是用哈希值计算初始桶位置。当发生哈希冲突（不同键哈希值相同，或取模后落到同一桶）时，需要通过冲突解决策略（CPython用开放寻址+扰动函数）遍历后续桶，直到找到目标键或确定键不存在——这就是你看到do_lookup中循环的原因。

4. CPython的优化机制让最坏情况几乎不会出现
   实际场景中，CPython会通过动态扩容哈希表（负载因子超阈值时桶数翻倍）、优化哈希函数减少冲突等方式，保证绝大多数情况下查找复杂度接近O(1)，只有恶意构造哈希冲突的极端场景才会触发O(N)的最坏情况。

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