Optimizing Jump Consistent Hash: Reducing Complexity to O(log n)

In a previous post the author explained the principle of Jump Consistent Hash; this follow‑up focuses on the O(n) time complexity of the original algorithm and proposes an optimization.

When expanding from n to n+1 nodes, each element moves with probability 1/(n+1); the algorithm uses a stable random sequence seeded by the key. To improve the O(n) cost, the author suggests randomly selecting the next bucket to jump to, ensuring the selection follows a specific probability distribution.

By defining the event that no jump occurs up to bucket i, the probability P(j ≥ i) is derived as (b+1)/i, where b is the last bucket where a jump happened. Using a uniform random number r∈[0,1), the condition r ≤ (b+1)/i leads to the equivalent inequality i ≤ floor((b+1)/r). This yields a simple selection rule: set j = floor((b+1)/r).

The resulting algorithm computes the target bucket for a given key and number of buckets (numbered from 1) in O(log n) time. The Go implementation is shown below:

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
}

Because the average value of r is 0.5, jumps on average occur when the bucket count doubles, confirming the O(log n) complexity claim.