線形走査法のハッシュ表で負荷率0.92から応答時間SLAを回復する
ある販売管理システムでは、商品コード（0〜999,999の整数）をキーとするハッシュ表をメモリ上に保持している。表サイズは1,200、ハッシュ関数は h(k) = k mod 1,200、衝突解決は線形走査法（linear probing）である。登録件数が800件のときの平均探索回数は1.3回であったが、商品数が1,100件に増えた現在、平均探索回数は8.7回、最悪45回となり、応答時間はSLAの5msを超えて平均18msになっている。削除は論理削除で、再ハッシュは行っていない。アクセスログを調べると、キー600〜720の範囲に検索が集中している。表サイズ1,200は素数ではなく、2^4×3×5^2である。現在の負荷率は約0.92である。メモリ制約から、表サイズを極端に大きくすることはできない。表サイズを2,401（素数）にすると、一時的にメモリ使用率が95%を超える見込みである。改善案として、(a) 表サイズを2,401に拡張、(b) 二重ハッシュ法に変更、(c) 論理削除領域の再利用、(d) チェイン法への変更、が挙がっている。
1. 性能劣化の主原因を、負荷率・ハッシュ関数・削除方式の3点から説明せよ。
Read the worked answer
負荷率は1,100/1,200≒0.92で、線形走査法の成功探索の平均回数は約0.5(1+1/(1-0.92))≒6.5回と理論上も悪化する。実測8.7回は、キー600〜720へのアクセス集中による一次クラスタリングと、論理削除で残った墓標（tombstone）が探索列を長くしているためである。h(k)=k mod 1,200は素数でないため、キーによっては同じ剰余に偏りやすい。主原因は「高負荷率＋クラスタリング＋墓標」の複合であり、ハッシュ関数単独ではない。
2. 優先すべき対策を1つ選び、理由と残るリスクを述べよ。
Read the worked answer
最優先は(a)表サイズ2,401への拡張である。負荷率が0.458まで下がり、平均探索回数は約1.42回と試算でき、SLA回復に最も直接的に効く。素数化により剰余の偏りも緩和される。ただし、再ハッシュ時に一時的な停止が発生し、メモリ使用率が95%を超えるリスクがある。移行は夜間バッチで行い、旧表を一定時間保持する。墓標の除去(c)は低コストだが負荷率を下げないため、拡張後の追加対策とする。二重ハッシュ(b)やチェイン(d)は実装変更が大きく、今回の緊急度では優先度が下がる。
3. 表サイズを2,401に拡張した場合の負荷率と、線形走査法の成功探索の平均回数の近似値を求めよ。また、1回の探索あたりの時間を現状から推定し、SLAを満たせるか判断せよ。
Read the worked answer
負荷率α=1,100/2,401≒0.458。成功探索の平均回数≒0.5(1+1/(1-0.458))≒1.42回。現状は8.7回で18msなので、1回あたり約2.07ms（18/8.7）と推定できる。拡張後は1.42×2.07≒2.9msとなり、SLAの5ms以内に収まる見込みである。ただし、墓標が残る場合は実測が理論値より大きくなるため、拡張後に(c)の再利用も実施し、再測定する。