问

redis字典的内部实现方式

xiao15387977702 发布于 2022-10-25 01:23

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

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

4 个回答

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

2022-10-26 14:04 回答

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

2022-10-26 14:04 回答

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

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

2022-10-26 14:05 回答

手浪用户2602898067
下图是Hash Table的示意图：

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

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

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

2022-10-26 14:05 回答

mobiledu2502905277

撰写答案

今天，你开发时遇到什么问题呢？

热门标签