上文中我們說到一致性哈希演算法，裡面有一個重要步驟我們沒有細說，就是哈希演算法。

記得我們上學的時候學過哈希表，簡單的哈希表就是一個連續存儲的數組，我們要存儲(k,v)這樣的數據，首先我們要對k進行取模運算，結果就是我們要存儲在數組的index。但是可能會有衝突，然後我們要解決衝突。現實的應用中，會有幾個問題，我們先拋出來： 1.實際的k、v存儲，k大部分情況都是字元串，不會是簡單的int類型，所以我們要想辦法把字元串轉換成整型 2.k、v存儲的在實際應用中一般數據量很大，我們要盡量保證哈希的結果不要有太多的衝突，不然就會影響系統的讀取和寫入的性能（時間都花在解決衝突上去了）。 3.哈希的速度要足夠快，因為一般存儲系統量太大了，哈希的速度回很大影響系統的性能。

那麼什麼樣的演算法是好的哈希演算法呢？我們進行一個不成熟的討論。

1. 如何判斷哈希的好壞

其實如上所述，我認為判斷哈希演算法的好壞的（不用於加密）的標準有兩個： 1.哈希的離散型，即為能否把數據哈希的均勻。 2.哈希的計算性能，一個好的能應用到工業的哈希演算法一定要是足夠快的。

1.1 哈希的離散性

我們知道，數據的key的範圍是無限的，而所謂哈希就是把這無限範圍的空間給映射到有限範圍的空間內，理論上來講必然是會發生衝突的。但是好的哈希演算法就是能把這個衝突的概率降到很低。 我們先來看看常見的幾個哈希演算法。 先來看看一個DJB

unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;

while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;
}

我們來看看這個哈希演算法好像很簡單，首先它給出了一個先初始化了hash值5381，然後遍歷字元串，然後把hash = hash*33 + c,最後直接返回hash。

再來看看FNV哈希演算法

template<class T>
size_t FNVHash(const T* str)
{
if(!*str)
return 0;
register size_t hash = 2166136261;
while (size_t ch = (size_t)*str++)
{
hash *= 16777619;
hash ^= ch;
}
return hash;
}

網上有很多關於FNV的演算法，包括FNV-1，FNV-0，FNV-1a，我們這裡只看他的FNV-1即可，看下它的過程，首先給出,初始hash值，然後迭代字元串，每輪乘一個大的質數16777619，然後再把hash值對當前的字元亦或，相當於把字元信息通過修改hash的低8為來輸入到hash值中，那麼為什麼要用異或操作呢？

這裡就有些意思了，因為異或操作更加隨機，為什麼呢？ 同樣的輸入，與操作有75%的概率為0，25%的概率為1，而或操作75%為1，25%為0，異或操作各50%。 a | b | a AND b —+—+——– 0 | 0 | 0 0 | 1 | 0

1 | 0 | 0

1 | 1 | 1a | b | a OR b —+—+——– 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 1a | b | a XOR b —+—+——–

0 | 0 | 0

0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 有點信息熵的意思哈，熵代表的就是混亂程度，你扔一個硬幣讓你猜正反，各自50%的概率，是最難猜的，如果有75%的概率是正面，當然更好猜一些，也就是說50%的概率隨機性更好的。 ok，我們繼續看一個哈希演算法,BKDRHash

unsigned int bkdr_hash(const char* key)
{
char* str = const_cast<char*>(key);

unsigned int seed = 31; // 31 131 1313 13131 131313 etc.. 37
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return hash;
}

這個演算法也很類似，遍歷字元串每個字元，乘以一個seed，在加上該字元的ASCII值，其實就是如下的公式: hash=(sum^{}{a[n]s^{n}})mod2^{32} 其中a代表就是字元串，s就是seed，為什麼說是mod了呢？賣個關子，我們稍後說。

看了這麼多的哈希演算法，我們心裡一定有以下的幾個疑惑：

1.這些哈希演算法都算是經典的哈希，它們經典在哪了，大部分都是不斷的乘一個數，貌似還是一個很大的質數，在加上字元的ASCII，只是改了一些數字而已，另外為什麼要選質數。我們來嘗試解釋下

讓我們回到上學那會學的簡單的哈希： M=key%N % N 我們的哈希的一個重要的目標就是使得原始的key經過哈希後隨機的分佈，但是實際中的key一般都不是隨機分佈的，如果key與N有公約數的時候，那麼hash發生碰撞的概率就會增大。為什麼呢？ 假設 N=Kn,M=Km ,M，N的公約數為K，我們做下轉化： 令

N % M=r

那麼

N=Mq+r

代入即為

Kn=Kmq+r

由於我們是N對M取模，那麼看起來r的取值範圍在0~M-1之間，但是我們對上式做兩邊除K的操作 n=mq+r/K 看到沒有，n和mq都是整數，代表什麼？r/K必然也是整數啊，驚呆了，r的取值範圍呢？我們上面知道r的取值範圍是0~M-1，那r/K也是整數的話，就代表r實際的取值範圍是0，K，2*K….，(M-M%K)= m*K 也就是說r的取值範圍縮小了K倍。 所以說我們要讓M和N互質纔是最好的，第一個想法就是把N設置為質數不就行了，但是你看上述的幾個演算法，好像大部分都是對取模，那麼我們就得想辦法把key轉換成一個質數了，這也是為什麼我們的那幾個演算法都是在不斷的乘以一個質數的原因，目的就是想把key轉換成一個整數，並且與 2^{32} 互質。

2.我們為什麼要對字元串循環的乘以一個數？

上述的所有演算法都是在遍歷字元串，然後不斷的乘以一個seed，為什麼不把字元串每個字元分別乘以這個數，相加即可？比如，我們的字元串「abc」，hash = a*seed+b*seed+c*seed 這裡也很有意思，你看下如果我們的字元串是「bac」,hash = b*seed+a*seed+c*seed，二者是不是相等的，明白了吧，目的是為了防止相同順序的字元串衝突，而現實生活中這種相同字母不同順序的key多的是 3.這些質數seed都是怎麼取的啊，為什麼是31，為什麼是5381，這些數字都是怎麼搞出來的？

這個問題一直困惑著我，查閱資料大部分都說是經過實驗得出的結論，說這些數字在實際中離散效果較好。這裡面可能有一些離散數學的理論基礎，我就不在深究了，有些選的是一個很大的質數，原因可能是為了擴大隨機空間。

4.一點猜想 現實生活中，可能有些key的分散式有規律的，如果我們能設計一個hash演算法，可以根據實際應用的key分佈來進行hash會不會效果更好呢，這就相當於我們把原始key的那個無限空間變為了一個有限的空間，再映射到一個有限空間豈不是更好，比如我們設計一個hash演算法，初始化的時候可以讓用戶輸入一部分樣例數據，用與選擇我們的seed，當然這個樣例數據樣足夠多能反應數據的分佈。

1.2 哈希的性能

終於要談到hash的性能了，我們知道在K-V存儲系統中，hash的性能至關重要。很多hash演算法，在設計的時候都喜歡做位運算，原因當然是速度快了。另外一個就是我們上述遺留的問題，我們為什麼要對取餘，其實原因很簡單，我們不想做取模的運算，我們的hash返回值是一個32位的整型，無論你計算的hash值有多大，不都自然溢出了，根本不需要我們再去做mod的運算，這樣節省了很大計算。估計這也是一致性哈希為什麼選擇 2^{32} 個桶的原因吧。

推薦閱讀：

相關文章