[TOC] ### 哈希算法 ***** 當要將一個新的鍵值對添加到字典里面時， 程序需要先根據鍵值對的鍵計算出哈希值和索引值， 然后再根據索引值， 將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。 Redis `計算哈希值`和`索引值`的方法如下： ``` // 使用字典設置的哈希函數，計算鍵 key 的哈希值 hash = dict->type->hashFunction(key); // 使用哈希表的 sizemask 屬性和哈希值，計算出索引值 // 根據情況不同， ht[x] 可以是 ht[0] 或者 ht[1] index = hash & dict->ht[x].sizemask; ``` eg:將一個鍵值對k0和v0添加到字典里面： * 程序先使用語句：hash = dict->type->hashFunction(k0), 計算鍵 k0 的哈希值 * 假設計算得出的哈希值為 8 ， 那么程序會繼續使用語句：index = hash & dict->ht\[0\].sizemask = 8 & 3 = 0; * 計算出鍵 k0 的索引值 0 ， 這表示包含鍵值對 k0 和 v0 的節點應該被放置到哈希表數組的索引 0 位置上  ### MurmurHash2 ***** 當字典被用作數據庫的底層實現，或者哈希鍵的底層實現時，Redis使用算法來計算鍵的哈希值。 `MurmurHash算法`最初由Austin Appleby于2008年發明，這種算法的優點在于，即使輸入的鍵是有規律的，算法仍能給出一個很好的隨機分布性，并且算法的計算速度也非常快。 `MurmurHash算法`目前的最新版本為MurmurHash3，而Redis使用的是`MurmurHash2`，關于MurmurHash算法的更多信息可以參考該算法的主頁：http://code.google.com/p/smhasher/。