Redis 哈希算法

當(dāng)要將一個(gè)新的鍵值對(duì)添加到字典里面時(shí)， 程序需要先根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值， 然后再根據(jù)索引值， 將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組的指定索引上面。

Redis 計(jì)算哈希值和索引值的方法如下：

# 使用字典設(shè)置的哈希函數(shù)，計(jì)算鍵 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 屬性和哈希值，計(jì)算出索引值
# 根據(jù)情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

舉個(gè)例子， 對(duì)于圖 4-4 所示的字典來(lái)說(shuō)， 如果我們要將一個(gè)鍵值對(duì) k0 和 v0 添加到字典里面， 那么程序會(huì)先使用語(yǔ)句：

hash = dict->type->hashFunction(k0);

計(jì)算鍵 k0 的哈希值。

假設(shè)計(jì)算得出的哈希值為 8 ， 那么程序會(huì)繼續(xù)使用語(yǔ)句：

index = hash & dict->ht[0].sizemask = 8 & 3 = 0;

計(jì)算出鍵 k0 的索引值 0 ， 這表示包含鍵值對(duì) k0 和 v0 的節(jié)點(diǎn)應(yīng)該被放置到哈希表數(shù)組的索引 0 位置上， 如圖 4-5 所示。

當(dāng)字典被用作數(shù)據(jù)庫(kù)的底層實(shí)現(xiàn)， 或者哈希鍵的底層實(shí)現(xiàn)時(shí)， Redis 使用 MurmurHash2 算法來(lái)計(jì)算鍵的哈希值。

MurmurHash 算法最初由 Austin Appleby 于 2008 年發(fā)明， 這種算法的優(yōu)點(diǎn)在于， 即使輸入的鍵是有規(guī)律的， 算法仍能給出一個(gè)很好的隨機(jī)分布性， 并且算法的計(jì)算速度也非常快。

MurmurHash 算法目前的最新版本為 MurmurHash3 ， 而 Redis 使用的是 MurmurHash2 ， 關(guān)于 MurmurHash 算法的更多信息可以參考該算法的主頁(yè)： http://code.google.com/p/smhasher/ 。