84669 人學習
152542 人學習
20005 人學習
5487 人學習
7821 人學習
359900 人學習
3350 人學習
180660 人學習
48569 人學習
18603 人學習
40936 人學習
1549 人學習
1183 人學習
32909 人學習
最近在看redis的設計與實作一書，看到字典這一章節時，發現redis字典的增刪改查操作的複雜度都是O(1)：
對此不太懂，看了它的資料結構，感覺不應該是O(1)的複雜度，給定一個key，去查value的話如果不是定長並且有序的儲存結構，怎麼可能是O (1)的複雜度？
拥有18年软件开发和IT教学经验。曾任多家上市公司技术总监、架构师、项目经理、高级软件工程师等职务。 网络人气名人讲师，...
下圖是Hash Table的示意圖：
主要是優化Hash Function，尽可能的减少冲突。也就是防止不同的key映射到相同的value上了，雖說即使衝突了也沒什麼。 。 。
Hash Function
key
value
參考：http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm 不確定是否需要翻牆。
PS：演算法導論可以看看。 。 。
看來題主是不知道什麼是hash啊，建議把資料結構的基礎先打好，再去研究redis基於資料結構的應用。
當然，hash的複雜度O(1)是指的平均複雜度，同時也是最理想狀態下的，最壞情況下是O(n)
我也不是很懂，遍歷鍊錶，複雜度怎麼會是1呢？
所謂字典為非也就是一個hash table, 而hashmap在沒有太多collision的情況下增查刪改複雜度都是線性的。 ～～
下圖是Hash Table的示意圖：
主要是優化
Hash Function，尽可能的减少冲突。也就是防止不同的key映射到相同的value上了，雖說即使衝突了也沒什麼。 。 。參考：
http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm 不確定是否需要翻牆。
PS：演算法導論可以看看。 。 。
看來題主是不知道什麼是hash啊，建議把資料結構的基礎先打好，再去研究redis基於資料結構的應用。
當然，hash的複雜度O(1)是指的平均複雜度，同時也是最理想狀態下的，最壞情況下是O(n)
我也不是很懂，遍歷鍊錶，複雜度怎麼會是1呢？
所謂字典為非也就是一個hash table, 而hashmap在沒有太多collision的情況下增查刪改複雜度都是線性的。 ～～