哈希演算法

Redis的數據結構hash，需要為key生成hashcode（哈希值），所採用的是 MurmurHash2 演算法。MurmurHash 演算法最初由 Austin Appleby 於 2008 年發明，是一種非加密型哈希函數，適用於一般的哈希檢索操作，即使輸入的key是有規律的，所產生的hashcode仍然有很好的隨機分布性，而且速度也很快。除了Redis，Memcached、Cassandra、HBase，Lucene、Hadoop、libstdc++、nginx、libmemcached也使用到了這種演算法。

Java的String是根據Horner法則生成hashcode：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

int h = 0;for (int i = 0; i < value.length; i++) { h = 31 * h + val[i];}

MD5消息摘要演算法（MD5 Message-Digest Algorithm）是一種被廣泛使用的密碼哈希函數。演算法輸入是一段不定長的數據或文本，輸出是一個16位元組的哈希值（32位16進位字元串），用於確保信息傳輸的完整一致。例如，伺服器預先提供一個MD5校驗和，用戶下載完文件以後，用MD5演算法計算下載文件的MD5校驗和，然後通過檢查這兩個校驗和是否一致，就能判斷下載的文件是否出錯。

2004年，證實MD5演算法無法防止碰撞（collision），因此無法適用於安全性認證，如SSL公開密鑰認證或是數字簽名等用途。

一致性哈希演算法是在分散式系統中使用的演算法。

想一想虛擬節點反映了什麼計算機思維？

參考資料：

MD5 - 維基百科，自由的百科全書

MurmurHash演算法（高運算性能，低碰撞率，hadoop、memcached等使用） - - ITeye博客

推薦閱讀：