Jump Consistent Hash

Problem

Given a key and a number of buckets, return the bucket chosen by jump consistent hash, which is the algorithm of Lamping and Veach.

Starting from no bucket, repeatedly jump the current key forward with a linear congruential step and compute the next candidate bucket from the top bits of the key. The result is deterministic and changes at most one bucket when the bucket count grows.

Hint

The key is updated with 64-bit wraparound before each jump.

Test cases

case 1

in: [123456,1000]

expected: 984

case 2

in: [0,1]

expected: 0

case 3

in: [42,10]

expected: 2

case 4

in: [9999,100]

expected: 15

case 5

in: [7,2]

expected: 0

Starter codePython

def jump_consistent_hash(key, buckets):
    # Your code here
    pass

5 test cases · run your code against them in the editor