redis字典的内部实现方式

Question

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

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

Answer 1

Gambar berikut ialah gambarajah skematik Jadual Hash:

Perkara utama ialah mengoptimumkan Hash Function untuk mengurangkan konflik sebanyak mungkin. Itu untuk mengelakkan key yang berbeza daripada dipetakan kepada value yang sama, walaupun ia tidak penting walaupun terdapat konflik. . .

Rujukan:
http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm Tidak pasti jika anda perlu memintas tembok api.

PS: Anda boleh membaca pengenalan kepada algoritma. . .

Answer 2

Nampaknya penyoal tidak tahu apa itu hash Adalah disyorkan untuk meletakkan asas struktur data dahulu, dan kemudian mengkaji aplikasi redis berdasarkan struktur data.

Sudah tentu, kerumitan cincang O(1) merujuk kepada kerumitan purata, dan ia juga merupakan keadaan paling ideal Kes terburuk ialah O(n)

Answer 3

Saya tidak begitu faham, bagaimana kerumitan melintasi senarai terpaut boleh menjadi 1?

Answer 4

Kamus yang dipanggil ialah jadual cincang dan kerumitan penambahan, pemadaman dan pengubahsuaian peta cincang adalah linear tanpa terlalu banyak perlanggaran. ~~