redis字典的内部实现方式

Question

最近在看redis的设计与实现一书，看到字典这一章节时，发现redis字典的增删改查操作的复杂度都是O(1)：

对此不太懂，看了它的数据结构，感觉不应该是O(1)的复杂度，给定一个key，去查value的话如果不是定长并且有序的储存结构，怎么可能是O(1)的复杂度？

Answer 1

下图是Hash Table的示意图：

主要是优化Hash Function，尽可能的减少冲突。也就是防止不同的key映射到相同的value上了，虽说即使冲突了也没什么。。。

参考：
http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm 不确定是否需要翻墙。

PS：算法导论可以看看。。。

Answer 2

看来题主是不知道什么是hash啊，建议把数据结构的基础先打好，再去研究redis基于数据结构的应用。

当然，hash的复杂度O(1)是指的平均复杂度，同时也是最理想状态下的，最坏情况下是O(n)

Answer 3

我也不是很懂，遍历链表，复杂度怎么会是1呢？

Answer 4

所谓字典为非也就是一个hash table, 而hashmap在没有太多collision的情况下增查删改复杂度都是线性的。～～