The Hash Ring

After this lesson your program places named nodes on a circle and answers "which node owns this key?" by walking clockwise. Adding or removing a node disturbs only the arc next to it, which is the property modulo hashing could not give you.

Placement without N

Stop tying placement to the node count. Hash both nodes and keys into one fixed space and treat the space as a circle. This lesson uses hsum(s) % 1000 (the sum of the UTF-8 bytes of s, modulo 1000), so positions run from 0 to 999. Production rings use 0..2^32-1.

The rule: a key belongs to the first node at or after its position, walking clockwise. If no node lies at or above the key, wrap around to the lowest node.

Three nodes, and some keys:

position:  0 ........ 315 ...... 424 ...... 529 ......... 999
                      red        blue       green

cat   (312)  first node >= 312         -> red@315
dog   (314)  first node >= 314         -> red@315
cow   (329)  first node >= 329         -> blue@424
zebra (532)  nothing >= 532, so wrap   -> red@315
blue  (424)  sits exactly on blue@424  -> blue

"At or after" includes equality: a key that hashes exactly onto a node's position belongs to that node.

Why this fixes resizing

Each node owns the arc between its predecessor and itself. Here red owns 530 to 999 and 0 to 315 (the arc wraps), blue owns 316 to 424, green owns 425 to 529. Now add a node that hashes to 700. It takes the keys in 530 to 700 from red, and nothing else changes: blue's and green's arcs are untouched. The node count never appears in the rule, so a membership change disturbs only the arcs next to it. That is the K/N guarantee promised in the last lesson.

The data structure

Keep every node as a (position, name) entry in a list sorted by position, then by name. A lookup is a binary search for the first entry whose position is at least the key's hash:

lo = 0, hi = number of entries
while lo < hi:
    mid = (lo + hi) / 2
    if entry[mid].position < h:  lo = mid + 1
    else:                        hi = mid
if lo == number of entries:      lo = 0      (wrap)
owner = entry[lo].name

That is O(log N) per lookup. Sort once when a node is added, never inside the lookup.

Two nodes can land on the same position (ab and ba both sum to 195). Ordering ties by name makes the answer independent of insertion order. A map from position to name would silently keep only one of the two, so keep entries, not a map.

Common mistakes

• No wrap. With only alpha@518 on the ring, LOOKUP whatever (position 870) must print alpha. The search index runs off the end of the list unless you reset it.
• Strictly greater instead of at-or-after. LOOKUP alpha hashes to exactly 518 and must print alpha, not the next node.
• Nearest node instead of clockwise. The rule has a direction. A key just above a node goes forward, never back.
• Incomplete removal, or adding twice. A leftover entry is a ghost that keeps owning an arc, and a second ADD_NODE of the same name must not create a second entry.
• Forgetting the modulus. A long node name sums to more than 1000; its position is the sum mod 1000.

Your exercise

Build the basic ring (one position per node, no virtual nodes yet) behind four commands. The starter already reads and dispatches them and provides hsum and the sorting helper. You write adding, removing, looking up and listing.