Jump Consistent Hash

The ring's costs are modest but real: O(N * vnodes) memory, O(log NK) per lookup, and a structure every client must agree on. In 2014, John Lamping and Eric Veach (Google) published a five-line function with zero memory and O(log N) expected time that still moves the minimum number of keys when the bucket count grows:

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (int64_t)((b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1)));
    }
    return b;
}

The mental model: imagine buckets being added one at a time, 1, 2, 3, ... n. Each time bucket j appears, a fair reshuffle demands that exactly 1/(j+1) of all keys "jump" into it — that's what keeps balance perfect. Jump hash replays this history for one key: the LCG line (key * constant + 1 — a linear congruential PRNG step, with key >> 33 extracting high-quality top bits) generates the key's personal, deterministic sequence of jump decisions, and the formula leaps directly from one jump destination b to the next j, skipping the bucket counts in between where the key stays put. Destinations thin out geometrically, so the loop runs O(log n) times in expectation — the last b below num_buckets is the answer.

Two properties fall out, and the tests exercise both. Movement is one-directional: when N grows to N+1, a key either stays or jumps into the new bucket — never between old buckets. In the hidden GROW 4 5 test the only change is 100: 1 -> 4 (into new bucket 4); in GROW 10 11 it's 5: 4 -> 10. Movement is minimal in expectation: each key moves with probability 1/(N+1). Expectation, not certainty — over just 10 sampled keys the GROW 4 5 test observes moved=1/10 where 2 was "expected". Don't hard-code the theory; count actual diffs.

The catch that keeps the ring employed: buckets are integers 0..N-1. You can't add a node named cache-west-7, can't remove bucket 3 without renumbering, can only grow or shrink at the top. Perfect for sharding tables, queues, or user-id ranges; useless as a drop-in for ketama. It ships in exactly those roles: Guava's Hashing.consistentHash() is this algorithm, and ClickHouse exposes it as the jumpConsistentHash() SQL function.

The Python trap: 64-bit overflow doesn't exist

C wraps key * 2862933555777941757 to 64 bits for free. Python multiplies exactly — your key balloons to hundreds of digits, key >> 33 becomes astronomically large, the division rounds j to 0, and since 0 < num_buckets the loop never terminates. The visible test's third line, HASH 10863919174838991 11, is where it bites: masked correctly it prints 6; unmasked it spins until the grader kills you with a time limit. The fix:

Your exercise

Three commands, exact formats. HASH <key> <n> prints the bucket; the visible vector is HASH 10863919174838991 11 -> 6 (plus HASH 0 1 -> 0, HASH 0 10 -> 0). ASSIGN <n> <keys...> prints <key>:<bucket> — colon, no spaces (1:0). GROW <old> <new> <keys...> prints <key>: <old_bucket> for stayers and <key>: <old> -> <new> for movers (colon-space, spaces around the arrow), then moved=<n>/<total>. The grader-caught mistakes: the missing 64-bit mask (time-limit death on the big-key vector); mixed-up formats between ASSIGN (1:0) and GROW (1: 6); and computing moved from theory instead of diffing — GROW 10 11 really does print moved=1/10, not 0 and not 1/11.