记一个问题：为什么 Redis get 方法时间复杂度官网标称 O(1)

事情源自于上一篇文章：Redis 数据结构 - 字典 dict

在学习到 dict 结构会用来维护 redis 数据库时，联想到 redis 的 get 方法底层一定会访问 dict 来查找键值。本质上还是查找 hash ，那么既然会查找 hash ，redis 又是采取拉链法来解决 hash 冲突，那当访问的哈希桶是一个链表时，不就会出现对这个链表的遍历了么？

我们都知道，对一个链表的遍历，时间复杂度是 O(n)。

那对于这种情况，查询的时间复杂度就会退化为 O(n) 了，而官网标称 get 的时间复杂度是 O(1)。（官网不该如此不严谨的吧）。

后经社区向大佬提问，得到的回答为：

1. 确实存在遍历链表的情况
2. 官网标称 O(1) 为定位到哈希桶的时间复杂度，计算 hash 的确是 O(1)
3. 上述问题实际体现出对时间复杂度理解的不足
   • 当存在链表遍历时，确实是一个 O(n) 的时间，但是并不代表着就退化成了 O(n)，只是介于 O(1) 和 O(n) 之间的一个时间
   • 当一个 hash 表中随处都是链表时，此时要考虑的应该是数据合理性的问题了

以下贴出 redis 的 hash 查找源码（也就只有计算 hash 和 查询链表）

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    if (dictSize(d) == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        he = d->ht_table[table][idx];
        while(he) {
            void *he_key = dictGetKey(he);
            if (key == he_key || dictCompareKeys(d, key, he_key))
                return he;
            he = dictGetNext(he);
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

void *dictGetKey(const dictEntry *de) {
    if (entryIsKey(de)) return (void*)de;
    if (entryIsNoValue(de)) return decodeEntryNoValue(de)->key;
    return de->key;
}

所以实际上 redis 的 get 方法是一个介于 O(1) 和 O(n) 之间的一个时间复杂度，大部分时间都是 O(1) 的。