Consistent Hashing Ring Position

Problem

Find the node that owns a key on a consistent hashing ring.

Each node name and the key are hashed with the djb2 hash (start at 5381, then h = (h * 33 + ord(ch)) mod 2**32). Sort the node hashes into a ring and return the first node whose hash is greater than or equal to the key hash, wrapping around to the smallest hash when none qualifies.

Return the chosen node name, or None for an empty node list.

Hint

Sorting the (hash, node) pairs turns the ring into a binary-searchable list.

Test cases

case 1

in: [["a","b","c"],"x"]

expected: "a"

case 2

in: [["node1","node2"],"key1"]

expected: "node1"

case 3

in: [["only"],"anything"]

expected: "only"

case 4

in: [[],"k"]

expected: null

Starter codePython

def ring_position(nodes, key):
    # Your code here
    pass

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