Redis 解決鍵沖突

當(dāng)有兩個或以上數(shù)量的鍵被分配到了哈希表數(shù)組的同一個索引上面時， 我們稱這些鍵發(fā)生了沖突（collision）。

Redis 的哈希表使用鏈地址法（separate chaining）來解決鍵沖突： 每個哈希表節(jié)點都有一個 next 指針， 多個哈希表節(jié)點可以用 next 指針構(gòu)成一個單向鏈表， 被分配到同一個索引上的多個節(jié)點可以用這個單向鏈表連接起來， 這就解決了鍵沖突的問題。

舉個例子， 假設(shè)程序要將鍵值對 k2 和 v2 添加到圖 4-6 所示的哈希表里面， 并且計算得出 k2 的索引值為 2 ， 那么鍵 k1 和 k2 將產(chǎn)生沖突， 而解決沖突的辦法就是使用 next 指針將鍵 k2 和 k1 所在的節(jié)點連接起來， 如圖 4-7 所示。

因為 dictEntry 節(jié)點組成的鏈表沒有指向鏈表表尾的指針， 所以為了速度考慮， 程序總是將新節(jié)點添加到鏈表的表頭位置（復(fù)雜度為 ）， 排在其他已有節(jié)點的前面。