Java一致性哈希算法舉例分析

這篇文章主要介紹“Java一致性哈希算法舉例分析”，在日常操作中，相信很多人在Java一致性哈希算法舉例分析問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java一致性哈希算法舉例分析”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

一、背景

 google 有一個 Jump consistent hash 算法，可以通過數(shù)學運算做到和一致性哈希效果一樣好的平衡性。

二、看代碼

先看代碼，下面就是全部的代碼。

是不是感覺不可思議，這個代碼的語法全部都懂，但是合在一起我們就看不懂了。
我第一眼看到這個代碼的時候，也是一臉懵逼的。

這個算法是 Google 的 John Lamping 和 Eric Veach 創(chuàng)造的。

三、算法原理

一致性哈希算法有兩個目標：

1. 平衡性。即把數(shù)據(jù)平均的分布在所有節(jié)點中。

2. 單調(diào)性。即節(jié)點的數(shù)量變化時，只需要把一部分數(shù)據(jù)從舊節(jié)點移動到新節(jié)點，不需要做其他的移動。

我們根據(jù)這個單調(diào)性可以推算出一些性質(zhì)來。
這里先令f(key, n)為一致性哈希算法，輸出的為[0,n)之間的數(shù)字，代表數(shù)據(jù)在對應的節(jié)點上。

1. n=1 時，對于任意的key，輸出應該都是0。

2. n=2 時，為了保持均勻，應該有1/2的結(jié)果保持為0，1/2的結(jié)果輸出為1。

3. n=3 時，應該有1/3的結(jié)果保持為0，1/3的結(jié)果保持為1，1/3的結(jié)果保持為2。

4. 依次遞推，節(jié)點數(shù)由n變?yōu)?code>n+1時，f(key, n)里面應該有n/(n+1)的結(jié)果不變，有1/(n+1)的結(jié)果變?yōu)?code>n。

這個使用概率公式來表示，就是這樣的代碼。

關(guān)于這個算法直接看可能還是看不懂。
所以需要使用實際數(shù)據(jù)模擬一下，見下圖。

關(guān)鍵在于n=2到n=3的過程，每個數(shù)字的概率從1/2轉(zhuǎn)化到了1/3。

之后，我們可以得出一個規(guī)律：增加一個節(jié)點，數(shù)據(jù)不發(fā)生變化的概率是n/(n+1) 再乘以之前每個數(shù)字的概率1/n，就可以得出每個數(shù)字最新的概率1/(n+1)

由此，可以輕松計算出n=4各數(shù)字的概率為1/4。自此，我們可以確定這個算法確實是有效的。

這個算法唯一的缺點是復雜度太高，是O(n)的。
所以需要進行優(yōu)化。

四、算法優(yōu)化

在上一小節(jié)中，我們了解到f(key, n)算法的正確性。
除了復雜度是O(n)外，我們還可以確定，循環(huán)越往后，結(jié)果改變的概率會越來越低。

結(jié)果改變指的是，增加一個節(jié)點后，一個固定的key輸出的結(jié)果發(fā)生了改變。
如果我們能夠快速計算出這個固定的key在哪些節(jié)點下發(fā)生了改變，就可以快速計算出最終答案。

假設(shè)某一次結(jié)果是b，經(jīng)過若干次概率測試，下一次改變?yōu)?code>a，則從b到a-1這中間，不管節(jié)點如何變化，這個key的結(jié)果都是不會變化的。
根據(jù)上一小節(jié)的到的概率變化公式，新增一個節(jié)點數(shù)字不變化的概率是n/(n+1)。
那從b到i不變化的概率就是b/i（中間的抵消了）。

如果我們有一個均勻的隨機函數(shù)r，當r<b/i時，f(i)=f(b)。
那么i的上界就是(b+1)/r。
這個上限也是下一次key發(fā)生變化的節(jié)點數(shù)量，由此可以得出下面的代碼。

由于r是均勻的，所以期望是1/2。
這樣，代碼中j就是按照指數(shù)級增長的，平均復雜度就是O(log(n))了。

回頭看看第一個代碼，就可以看懂代碼了。

第一個key=key*x+1算是一個偽隨機生成器。
而j=(b+1)*x/y則是上面的求上界的公式，其中y/x通過浮點數(shù)運算來產(chǎn)生(0,1)內(nèi)的一個隨機數(shù)。
自此，這個代碼就可以看懂了。

到此，關(guān)于“Java一致性哈希算法舉例分析”的學習就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>