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

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

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

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

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

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

确实存在遍历链表的情况
官网标称 O(1) 为定位到哈希桶的时间复杂度，计算 hash 的确是 O(1)
上述问题实际体现出对时间复杂度理解的不足
- 当存在链表遍历时，确实是一个 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;
}