Day 160-Q1 — 2026-09-25 — Jump Consistent Hash（Lamping–Veach 2014・バケツ数を変えたとき移動するキーを 1/(n+1) に抑える、メモリ 0 の一貫性ハッシュ）

問題

$K$ 個のキー $x_1,\dots,x_K$（64 ビット符号なし整数）と、バケツ数の列 $n_0,n_1,\dots,n_Q$ が与えられる。キー $x$ をバケツ数 $n$ のもとで次の関数 $\mathrm{JCH}(x,n)\in[0,n)$ に割り当てる（Lamping, Veach「A Fast, Minimal Memory, Consistent Hash Algorithm」Figure 1 のコードそのもの。演算は uint64 の wrap-around、double は IEEE 754 倍精度）。

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

各 $i=1,\dots,Q$ について、バケツ数を $n_{i-1}$ から $n_i$ に変えたときに 割り当て先が変わるキーの個数 $\#\{t : \mathrm{JCH}(x_t,n_{i-1})\ne \mathrm{JCH}(x_t,n_i)\}$ を出力せよ。

入力形式

K Q
x_1 x_2 ... x_K
n_0 n_1 ... n_Q

制約

入出力例

8 3
0 1 2 3 4 5 6 7
3 4 5 3

2
1
3

（各キーの割り当て: $n=3,4,5$ の順に key0: 0,0,0 / key1: 0,0,0 / key2: 0,3,3 / key3: 2,3,3 / key4: 1,1,1 / key5: 1,1,4 / key6: 2,2,2 / key7: 0,0,0。$3\to4$ で動くのは新バケツ 3 へ移る 2 個だけ、$4\to5$ は新バケツ 4 へ移る 1 個だけ、$5\to3$ はバケツ 3・4 にいた 3 個が元の場所に戻る）

この問題は Lamping, Veach（Google, 2014, https://arxiv.org/abs/1406.2294 、2026-09-25 参照）の Jump Consistent Hash を題材にしている。一貫性ハッシュ（consistent hashing）の原典は Karger ら（STOC 1997）のリング方式で、分散キャッシュ・シャーディングでキーの再配置を最小にする目的で使われる。

概念図：ジャンプ列と割り当て

ヒント（クリックで段階的に開示）

def jump_chain(key, n_max):
    chain, b, j = [], -1, 0
    while j < n_max:
        b = j; chain.append(b)
        key = (key * MUL + 1) & MASK
        j = int((b + 1) * (2147483648.0 / ((key >> 33) + 1)))
    return chain
# JCH(x, n) = chain[bisect_left(chain, n) - 1]
# 変わる ⇔ bisect_left(chain, n_prev) != bisect_left(chain, n_next)

模範解答 (Python)

📋 コピーimport sys
from bisect import bisect_left

MASK = (1 << 64) - 1
MUL = 2862933555777941757
TWO31 = float(1 << 31)


def jump_chain(key, n_max):
    """key に対するジャンプ列 b_0=0 < b_1 < ... （すべて n_max 未満）を返す。"""
    chain = []
    b, j = -1, 0
    while j < n_max:
        b = j
        chain.append(b)
        key = (key * MUL + 1) & MASK
        j = int((b + 1) * (TWO31 / ((key >> 33) + 1)))
    return chain


def main():
    data = sys.stdin.buffer.read().split()
    k, q = int(data[0]), int(data[1])
    keys = data[2:2 + k]
    ns = [int(x) for x in data[2 + k:2 + k + q + 1]]
    n_max = max(ns)
    moved = [0] * q
    for x in keys:
        ch = jump_chain(int(x), n_max)
        pos = [bisect_left(ch, n) for n in ns]   # bucket(n) = ch[pos-1]
        for i in range(q):
            if pos[i] != pos[i + 1]:
                moved[i] += 1
    sys.stdout.write("\n".join(map(str, moved)) + "\n")


main()

Step-by-Step 解説

迷った他案と採らなかった理由

前提が変わったら: ストレージのシャードのように「番号付きで増減は末尾だけ」ならジャンプ。キャッシュサーバのように「任意の 1 台が落ちる」ならリングか Rendezvous（ジャンプで途中を消すと、それ以降の全バケツの番号がずれて大量移動が起きる）。

よくあるミス

次のステップ

• 発展1: 重み付きバケツ（容量 2 倍のサーバ）をジャンプで扱うには？（仮想バケツを割り当てる／Rendezvous の重み付き版 $-w/\ln h$ と比較）
• 発展2: 途中のバケツ $d$ を消したい。「$d$ を末尾 $n-1$ と入れ替える写像表」を持つと移動は何個になるか実測する
• 扱わなかった範囲: 複製（replica）の配置、負荷上限付き一貫性ハッシュ（Mirrokni ら 2018, bounded loads）、Maglev

自己評価

自分の回答

気づき・メモ