Jump Consistent Hash Bucket Lookup

Problem

Implement Jump Consistent Hash, which maps a key to a bucket without storing a ring.

key is an integer and buckets is the number of buckets. The algorithm repeatedly jumps forward using the 64-bit linear congruential step k = (k * 2862933555777941757 + 1) mod 2**64 and computes the next bucket as ((b + 1) * 2**31) // ((k >> 33) + 1) until it passes the bucket count.

Return the chosen bucket index, or -1 when buckets is not positive.

Hint

The jump length shrinks geometrically so the loop runs in O(log n) iterations.

Test cases

case 1

in: [0,1]

expected: 0

case 2

in: [42,10]

expected: 2

case 3

in: [12345,100]

expected: 29

case 4

in: [7,5]

expected: 0

case 5

in: [99,0]

expected: -1

Starter codePython

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

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