Python の set における衝突解決アルゴリズムの詳細（perturbation の仕組み）
Python の set はオープンアドレス法で衝突を解決する。その核心にあるのが perturbation（摂動）を使った探索アルゴリズムだ。
線形探索の問題
最も単純な衝突解決は線形探索だ。衝突したら次のスロットを試す。
# 線形探索（悪い例）
def find_slot_linear(table, key):
size = len(table)
index = hash(key) % size
while table[index] is not None and table[index] != key:
index = (index + 1) % size
return index
これには「クラスタリング」という問題がある。連続した領域が埋まると、その領域がさらに成長しやすくなる。
衝突が発生すると、次のスロットも衝突しやすくなる。連続した塊が形成され、探索効率が悪化。
同じハッシュ値を持つ要素が同じ探索経路をたどる。別の形でクラスタが形成される。
CPython の探索アルゴリズム
CPython は perturbation を使ってクラスタリングを緩和する。
/* CPython setobject.c からの抜粋（簡略化）*/
static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
{
size_t i = (size_t)hash & so->mask;
size_t perturb = (size_t)hash;
while (1) {
setentry *entry = &so->table[i];
if (entry->key == NULL)
return entry;
if (entry->hash == hash && entry->key == key)
return entry;
/* 次のスロットを計算 */
perturb >>= PERTURB_SHIFT;
i = (i * 5 + perturb + 1) & so->mask;
}
}この式 i = (i * 5 + perturb + 1) & mask が核心だ。
探索式の分解
探索式を分解して理解する。
# 探索式
next_index = (current_index * 5 + perturb + 1) & mask
perturb >>= PERTURB_SHIFT # 通常 5
# 各項の意味
# current_index * 5: 前のインデックスを 5 倍
# + perturb: ハッシュ値由来の擬似乱数
# + 1: 同じ場所に留まらない保証
# & mask: テーブルサイズでラップ
perturb は最初はハッシュ値そのものだが、ループごとに右シフトで減衰していく。
perturbation の減衰
perturb が減衰する様子を観察する。
def trace_probing(hash_value, mask):
i = hash_value & mask
perturb = hash_value
PERTURB_SHIFT = 5
print(f"Initial: index={i}, perturb={perturb}")
for step in range(10):
perturb >>= PERTURB_SHIFT
i = (i * 5 + perturb + 1) & mask
print(f"Step {step+1}: index={i}, perturb={perturb}")
# テーブルサイズ 32（mask = 31）
trace_probing(hash_value=12345, mask=31)
出力例:
# Initial: index=25, perturb=12345
# Step 1: index=2, perturb=385
# Step 2: index=23, perturb=12
# Step 3: index=20, perturb=0
# Step 4: index=5, perturb=0
# Step 5: index=26, perturb=0
# ...
最初の数ステップでは perturb がジャンプを左右するが、やがて 0 になり、その後は i * 5 + 1 の線形合同法的な探索になる。
なぜ 5 倍なのか
係数 5 には理由がある。
偶数だと mask+1（2の累乗）と共通因数を持ち、すべてのスロットを訪問できない可能性がある。
5 は線形合同法で良い分布を得るための経験的に選ばれた値。
テーブルサイズが 2^n のとき、5 倍することで全スロットを巡回できる。
def check_coverage(mask, multiplier):
"""すべてのスロットを訪問できるか確認"""
visited = set()
index = 0
for _ in range(mask + 1):
visited.add(index)
index = (index * multiplier + 1) & mask
return len(visited) == mask + 1
# 2 の累乗サイズで確認
for size in [8, 16, 32, 64]:
mask = size - 1
print(f"Size {size}: covers all = {check_coverage(mask, 5)}")
探索パターンの可視化
異なるハッシュ値での探索パターンを可視化する。
def probe_sequence(hash_value, mask, steps=10):
i = hash_value & mask
perturb = hash_value
sequence = [i]
for _ in range(steps):
perturb >>= 5
i = (i * 5 + perturb + 1) & mask
sequence.append(i)
return sequence
mask = 31 # テーブルサイズ 32
# 異なるハッシュ値での探索パターン
for h in [0, 1, 32, 100, 12345]:
seq = probe_sequence(h, mask, 8)
print(f"hash={h:5d}: {seq}")
同じハッシュ値（mod mask）でも、元のハッシュ値が異なれば異なる経路をたどる。
二次クラスタリングの緩和
通常の二次探索（quadratic probing）では、同じ初期位置から始まる探索は同じ経路をたどる。
# 二次探索（同じ初期位置 → 同じ経路）
def quadratic_probe(start, mask, steps):
return [(start + i * i) & mask for i in range(steps)]
print(quadratic_probe(5, 31, 5)) # [5, 6, 9, 14, 21]
print(quadratic_probe(5, 31, 5)) # 同じ
Python の方式では、元のハッシュ値が異なれば経路も変わる。
# hash % mask は同じでも、元の hash が違えば経路が異なる
print(probe_sequence(5, 31, 5)) # hash=5
print(probe_sequence(5 + 32, 31, 5)) # hash=37（同じ初期位置）
これにより二次クラスタリングが緩和される。
PERTURB_SHIFT の意味
PERTURB_SHIFT = 5 は、perturbation がどれくらい早く減衰するかを決める。
# 64ビットハッシュ値の場合
# perturb >>= 5 を 13 回繰り返すと 0 になる
# (64 / 5 ≈ 13)
hash_value = 2**63 - 1 # 最大値付近
perturb = hash_value
count = 0
while perturb > 0:
perturb >>= 5
count += 1
print(f"Decay steps: {count}") # 13
約 13 ステップで perturbation の影響がなくなり、決定論的な探索に切り替わる。
削除とダミーマーカー
削除されたスロットにはダミーマーカーが置かれる。
#define dummy (&_PySet_Dummy)ダミーがないと、探索チェーンが途切れてしまう。
# 概念的な動作
# テーブル: [A, B, C, None, None, ...]
# A, B, C は衝突で連続配置
# B を削除
# テーブル: [A, DUMMY, C, None, None, ...]
# C を検索
# A を見る → 違う → 次へ
# DUMMY を見る → 削除済み → 探索継続
# C を見る → 見つかった！
# もし DUMMY がなければ
# A を見る → 違う → 次へ
# None を見る → 探索終了 → C が見つからない！
挿入時の最適化
挿入時は、最初に見つかった DUMMY スロットを記憶しておき、要素が見つからなければそこに挿入する。
/* 挿入時の探索（簡略化）*/
setentry *freeslot = NULL;
while (1) {
if (entry->key == NULL) {
/* 空スロットに到達 */
return freeslot ? freeslot : entry;
}
if (entry->key == dummy && freeslot == NULL) {
/* 最初の DUMMY を記憶 */
freeslot = entry;
}
if (entry->hash == hash && entry->key == key) {
/* 既存の要素 */
return entry;
}
/* 次へ */
}これにより、削除が多い状況でもテーブルの先頭付近に挿入できる。
最悪ケースの分析
すべての要素が同じハッシュ値を持つ極端なケースでは、O(n) の探索になる。
class BadHash:
def __init__(self, value):
self.value = value
def __hash__(self):
return 1 # 常に同じ
def __eq__(self, other):
return self.value == other.value
# 衝突が多発
s = set()
for i in range(1000):
s.add(BadHash(i))
しかし、通常のデータでは perturbation によって衝突が分散され、平均 O(1) が維持される。CPython のこのアルゴリズムは、理論と実用のバランスを取った設計だ。
