redis字典的内部实现方式

Question

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

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

Answer 1

다음 그림은 해시 테이블의 개략도입니다.

가장 중요한 것은 Hash Function을 최적화하여 갈등을 최대한 줄이는 것입니다. 서로 다른 key이 같은 value으로 매핑되는 것을 방지하기 위함이지만, 충돌이 일어나도 상관없습니다. . .

참조:
http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm 방화벽을 우회해야 하는지 잘 모르겠습니다.

PS: 알고리즘 소개를 읽어보실 수 있습니다. . .

Answer 2

질문자는 해시가 무엇인지 모르는 것 같습니다. 먼저 데이터 구조의 기초를 다진 다음 데이터 구조를 기반으로 Redis의 응용을 연구하는 것이 좋습니다.

물론 해시 O(1)의 복잡도는 평균 복잡도를 의미하며, 최악의 경우는 O(n)입니다

Answer 3

잘 이해가 안 되네요. 어떻게 연결 리스트 순회 복잡도가 1이 될 수 있나요?

Answer 4

소위 사전은 해시 테이블이며, 해시맵의 추가, 삭제, 수정의 복잡성은 큰 충돌 없이 선형적입니다. ~~