Redis 사전의 내부 구현

Question

최근에 Redis의 설계 및 구현에 관한 책을 읽다가 사전 장을 봤을 때 Redis 사전의 추가, 삭제, 수정 및 검색 작업의 복잡성이 O(1)이라는 것을 알았습니다.

데이터 구조를 읽은 후에는 O(1) 복잡성이 있어서는 안 된다는 생각이 들었습니다. 키가 고정되어 있지 않은 경우 어떻게 값을 확인할 수 있습니까? - 길이와 정렬된 저장 구조는 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

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