redis字典的内部实现方式

Question

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

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

Answer 1

L'image suivante est un diagramme schématique de la table de hachage :

L'essentiel est d'optimiser Hash Function pour réduire au maximum les conflits. Cela permet d'éviter que différents key soient mappés au même value, même si cela n'a pas d'importance même s'il y a un conflit. . .

Référence :
http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm Je ne sais pas si vous devez contourner le pare-feu.

PS : Vous pouvez lire l’introduction aux algorithmes. . .

Answer 2

Il semble que la personne qui pose la question ne sache pas ce qu'est le hachage. Il est recommandé de jeter d'abord les bases de la structure des données, puis d'étudier l'application de Redis basée sur la structure des données.

Bien sûr, la complexité du hachage O(1) fait référence à la complexité moyenne, et c'est aussi l'état le plus idéal. Le pire des cas est O(n)

.

Answer 3

Je ne comprends pas très bien, comment la complexité du parcours d'une liste chaînée peut-elle être de 1 ?

Answer 4

Le soi-disant dictionnaire est une table de hachage, et la complexité de l'ajout, de la suppression et de la modification du hashmap est linéaire sans trop de collision. ~~