前言

隨後又發表了本文上篇，初步解釋了 Jump Consistent Hash 的原理。

首先讓我們回顧一下：

擴容時，隨機選擇要移動的元素從現有 n 節點擴容到 n+1 節點時，n 節點上每個元素有 1/(n+1) 的機率移動到新節點使用穩定的、可重現的隨機數序列——以 key 為隨機數種子

我們遺留了一個問題，O(n) 的演算法複雜度不夠理想，如何最佳化？

最佳化複雜度

與其在 bucket 逐步增加的過程中，每次隨機地決定是否跳躍到新增的 bucket。我們嘗試隨機決定下一次加到第幾個 bucket 才跳躍。當然，這個隨機選取的目標需要符合一定的機率分佈。

假設上一次 k 的跳躍發生在增加第 b+1 個 bucket 時，即 ch(k,b) != ch(k,b+1) 且 ch(k,b+1) = b+1（本文 bucket 編號從 1 開始）。這一次跳躍，我們隨機選擇了一個位置 j+1，即 ch(k,j+1) != ch(k,j) 且 ch(k,j) = ch(k,b+1)。

作為單次選擇，跳躍發生在 b+2（連續跳）或者 INT_MAX（再也不跳了），都是可能的。但總體上，j 的選擇要滿足一定的規律。

定義事件：對於任意 i >= b+2，在增加第 b+2、b+3 ... i 個 bucket 時，都沒有發生跳躍。該事件當且僅當 j+1 > i，即 j >= i 時成立。

該事件的機率可以這麼算：

從 b+1 增加到 b+2，不跳躍的機率是 (b+1)/(b+2)一直加到第 i 個 bucket，都不跳躍，其機率為 (b+1)/(b+2)*(b+2)/(b+3)*...*(i-1)/(-) = (b+1)/i即 P(j>=i) = (b+1)/i。該等式對於任意 i 都成立。

j 是我們任選的，可能 j>=i，也可能 j<i。選擇方式待定，但要讓機率 P(j>=i)等於(b+1)/i。

每次要選擇 j 時，我們生成一個 [0,1) 上均勻分佈的隨機數 r，顯然，布林表示式 r <= (b+1)/i 為 true 的機率是 (b+1)/i。我們先變換一下表達式：

r <= (b+1)/i 變換後可得 i <= (b+1)/r。由於 i 是整數，(b+1)/r 向下取整不等式依然成立，表示式最後變換為 i <= floor((b+1)/r)。

當上述表示式為 true 時，我們就選則大 j (j>=i)；否則，我們就選則小 j (j<i)。這個選擇方式, 就使 P(j>=i) = (b+1)/i 成立。

i <= floor((b+1)/r) 時，i 最大可為 floor((b+1)/r)，則 j>=floor((b+1)/r)i > floor((b+1)/r) 時，i 最小可為 floor((b+1)/r)+1，則 j<=floor((b+1)/r)

綜上 j = floor((b+1)/r)。計算有 num_buckets 時，key 應當所在的 bucket 編號（本文中從 1 開始）的程式碼為：

func ch2(key int, num_buckets int) int {    r := rand.New(rand.NewSource(int64(key)))    b1 := -1    j := 0    for j < num_buckets {        b1 = j + 1        j = int(math.Floor(float64(b1)/r.Float64()))    }    return b1}

r 的平均值是 0.5，即跳躍平均發生在 bucket 數量翻倍時。粗略的看，演算法複雜度是 O(log(n))。