redis字典的内部实现方式

Question

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

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

Answer 1

The picture below is a schematic diagram of the Hash Table:

Mainly due to optimization Hash Function，尽可能的减少冲突。也就是防止不同的key映射到相同的value, although it doesn’t matter even if there is a conflict. . .

Reference:
http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm Not sure if you need to circumvent the firewall.

PS: You can read the introduction to algorithms. . .

Answer 2

It seems that the questioner does not know what hash is. It is recommended to lay the foundation of data structure first, and then study the application of redis based on data structure.

Of course, the complexity of hash O(1) refers to the average complexity, and it is also the best case, and the worst case is O(n)

Answer 3

I don’t quite understand. How can the complexity of traversing a linked list be 1?

Answer 4

The so-called dictionary is a hash table, and the complexity of addition, deletion and modification of hashmap is linear without too much collision. ~~