84669인 학습
152542인 학습
20005인 학습
5487인 학습
7821인 학습
359900인 학습
3350인 학습
180660인 학습
48569인 학습
18603인 학습
40936인 학습
1549인 학습
1183인 학습
32909인 학습
最近在看redis的设计与实现一书,看到字典这一章节时,发现redis字典的增删改查操作的复杂度都是O(1):
对此不太懂,看了它的数据结构,感觉不应该是O(1)的复杂度,给定一个key,去查value的话如果不是定长并且有序的储存结构,怎么可能是O(1)的复杂度?
拥有18年软件开发和IT教学经验。曾任多家上市公司技术总监、架构师、项目经理、高级软件工程师等职务。 网络人气名人讲师,...
下图是Hash Table的示意图:
主要是优化Hash Function,尽可能的减少冲突。也就是防止不同的key映射到相同的value上了,虽说即使冲突了也没什么。。。
Hash Function
key
value
参考:http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm 不确定是否需要翻墙。
PS:算法导论可以看看。。。
看来题主是不知道什么是hash啊,建议把数据结构的基础先打好,再去研究redis基于数据结构的应用。
当然,hash的复杂度O(1)是指的平均复杂度,同时也是最理想状态下的,最坏情况下是O(n)
我也不是很懂,遍历链表,复杂度怎么会是1呢?
所谓字典为非也就是一个hash table, 而hashmap在没有太多collision的情况下增查删改复杂度都是线性的。~~
下图是Hash Table的示意图:
![](http://img.php.cn/upload/image/000/000/000/257bf6a8a6a454d2d6454af90fba88c3-0.jpg)
主要是优化
Hash Function
,尽可能的减少冲突。也就是防止不同的key
映射到相同的value
上了,虽说即使冲突了也没什么。。。参考:
http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm 不确定是否需要翻墙。
PS:算法导论可以看看。。。
看来题主是不知道什么是hash啊,建议把数据结构的基础先打好,再去研究redis基于数据结构的应用。
当然,hash的复杂度O(1)是指的平均复杂度,同时也是最理想状态下的,最坏情况下是O(n)
我也不是很懂,遍历链表,复杂度怎么会是1呢?
所谓字典为非也就是一个hash table, 而hashmap在没有太多collision的情况下增查删改复杂度都是线性的。~~