プロンプトとスコープ
各スロットに最大1つのキー・値ペアを保持するmスロットの配列を持つ、固定容量のオープンアドレス法ハッシュテーブルを実装してください。insert(key,value)、contains(key)、remove(key)をサポートします。衝突はRobin Hood hashingで解決し、チェイニングやtombstoneは使用しないでください。中核となるアルゴリズムに焦点を当てるため、テーブルが満杯の場合はリサイズする代わりに失敗を返しても構いません。
これは、データ構造、不変条件、エッジケース、計算量に関する一般的なコーディング面接の問題です。スタンフォード大学のCS106Bの公開課題では、学生にRobin Hoodテーブルの実装を求めており、探索距離に基づくスワップ、検索の早期終了、後方シフト削除が明示的に含まれています。現在のソフトウェアエンジニアリング面接ガイドでは、データ構造の判断力、正確性、計算量、エッジケースの処理がコーディング評価シグナルとして挙げられています。
面接官が見ているポイント
- 各要素のホームバケット（ハッシュ元の位置）とPSL（probe sequence length：探索系列長）を保持できるか。
- 「貧しいキー（探索距離が長いキー）が優先される」理由を説明できるか：挿入対象のPSLの方が大きい場合、ホームに近い常駐キーとスワップする。
- PSLの単調性を利用して、配列全体をスキャンすることなく失敗した検索を早期終了できるか。
- tombstoneを使わずに削除を行い、探索クラスタ内のすべてのキーへの到達可能性を維持できるか。
- 平均コストと最悪ケースのコストを述べ、高負荷時のポリシーを選択できるか。
一般的な回答では線形探索を記述するものの、削除による空きスロット（穴）がそれ以降の探索を途切れさせてしまうことを見落としがちです。優れた回答では、「空スロット」と「常駐PSLが対象PSL未満」の双方を、証明された停止条件として扱います。
回答前の前提確認
- 容量は固定ですか？固定容量の場合、挿入失敗は明示的な結果となります。リサイズを伴う場合は、負荷係数の閾値によって再構築（リハッシュ）がトリガーされます。
- 重複キーは許可されますか？重複は2つ目のスロットを追加するのではなく値を更新すると仮定します。マルチマップの場合は異なるAPIと削除の取り決めが必要になります。
- ハッシュは安定しており、キーはコピー可能ですか？ハッシュは1回の操作中に安定している必要があります。ホームバケットをキャッシュすると重複した計算を回避できますが、スロットのメモリを消費します。
- イテレータや参照の安定性は必要ですか？スワップや後方シフトによって要素が移動するため、安定したアドレスは保証されません。呼び出し元が安定したハンドルを必要とする場合は間接参照を使用します。
- 並行性はスコープ内ですか？これはシングルスレッド前提です。並行バージョンにはロック、ストライピング、またはロックフリープロトコルが必要です。通常のนี่の実装はスレッドセーフではありません。
30秒の回答フレームワーク
「占有されている各スロットにキー、値、ホームバケット、PSLを格納します。挿入時はホームから線形探索を行い、挿入対象のPSLが常駐要素のPSLを超えた場合、両者をスワップして移動距離の長い要素に優先度を与え、追い出された要素の配置を続けます。検索は、空スロットに到達した時、または常駐PSLが対象PSLを下回った時に失敗と判定できます。後続のエントリがより短い距離に戻ることはないためです。削除時は、空スロットまたはPSLが0のエントリに達するまで後続のエントリを後方にシフトし、移動ごとにPSLをデクリメントして探索パスが途切れないようにします。期待計算量はほぼO(1)、最悪計算量はO(m)、空間計算量はO(m)です。」
ステップごとの詳細回答
1. スロットモデルと不変条件
占有されている各スロットには(key, value, home, psl)が格納されます。mスロットのリングにおいて、psl = (index - home + m) % mとなります。以下の3つの不変条件を維持します：
homeはキーの固定されたハッシュ起点である。homeからpslステップ前方に進むと現在のインデックスに到達する。- 1つの連続した探索クラスタ内では、占有されているPSL値は決して減少しない。空スロットによってクラスタは終了する。
3つ目の不変条件は、挿入時により大きなPSLを優先することから生じます。これにより、検索時に後続のすべてのスロットを調べることなく、対象のPSLと常駐PSLを比較するだけで済むようになります。
2. 線形探索のボトルネック
通常の線形探索は、ホームから空スロットが見つかるまで前方に進みます。高負荷時には、初期のキーがホームの近くのスロットを占有する一方で、すでに遠くまで探索した後のキーが進み続けることになり、探索長の分散がテールレイテンシを増大させます。Robin Hood hashingはコンパクトな配列レイアウトを維持しつつ、衝突時に移動距離の長いキーを優先します。
3. Robin Hoodの挿入
疑似コード：
insert(key, value):
item = (key, value, home=hash(key), psl=0)
for step in 0 .. m-1:
i = (item.home + item.psl) mod m
if table[i] is empty:
table[i] = item
return success
if table[i].key == key:
table[i].value = value
return updated
if table[i].psl < item.psl:
swap(table[i], item)
item.psl += 1
return fullスワップ後、itemは追い出されたエントリになります。そのPSLはすでに現在の探索位置を表しているため、次のイテレーションで1増やします。空スロットとPSLが0の実際のエントリを明確に区別してください。そうしないと、挿入と削除の境界が曖昧になります。
4. 検索と早期終了
検索は対象のホームから開始し、対象のPSLを追跡します：
contains(key):
home = hash(key)
for psl in 0 .. m-1:
i = (home + psl) mod m
if table[i] is empty:
return false
if table[i].psl < psl:
return false
if table[i].key == key:
return true
return false空スロットはクラスタの終端を意味します。常駐PSLが対象PSLを下回っている場合、クラスタのPSLが減少しないため、後続のスロットに対象が含まれることはあり得ません。スタンフォードの課題では、この早期終了を通常の線形探索との決定的な違いとして扱っています。
5. 後方シフト削除
スロットをすぐにクリアしてはいけません。後続のキーが衝突解決中にそのスロットを通過している可能性があり、検索がその穴で誤って停止してしまうためです。tombstoneも禁止されており、時間の経過とともに探索長を増大させます。
remove(key):
i = find_index_or_not_found(key)
if i is not found:
return false
j = (i + 1) mod m
while table[j] is not empty and table[j].psl > 0:
table[i] = table[j]
table[i].psl -= 1
i = j
j = (j + 1) mod m
table[i] = empty
return true空スロットまたはPSLが0のエントリで停止します。前者はクラスタの終端であり、後者は自身のホームにあるため、1つ前のスロットをクリアしてもその検索パスが途切れることはありません。移動ごとにPSLをデクリメントし、距離の不変条件を回復します。
6. 計算量と高負荷時のポリシー
一様ハッシュかつ負荷係数αが1より十分に低い場合、挿入、検索、削除の期待探索回数は定数スケールです。ただし、単一の操作でmスロットすべてをスキャンする可能性があるため、最悪時間計算量はO(m)、空間計算量はO(m)です。Robin Hood hashingは主に探索長の分布と分散を改善するものであり、オープンアドレス法の最悪ケースを排除するものではありません。引用された解析では高負荷モデルにおける有界な分散が研究されていますが、本番コードでは依然として負荷の閾値が必要です。
αがその閾値に近づいた場合は、期待O(1)に依存せず、より大きな容量で再構築します。容量を固定しなければならない場合は、fullを通常の業務結果として扱い、失敗率、平均PSL、P99探索数、および削除シフト長を監視します。
7. 反例とテストケース
- 空テーブルへの挿入と検索：ホームスロットに直接格納され、存在しないキーは最初の空スロットで停止する。
- 重複キー：値の更新によって要素数が増加しないこと。
- ラップアラウンド（末尾からの折り返し）：末尾近くのホームを選択し、
(index - home + m) % mを検証する。 - スワップの連鎖：衝突するキーを構築し、1回の挿入ですべての項目が適切に退避・配置されることを検証する。
- クラスタの先頭、中間、末尾の削除：残りのすべてのキーが引き続き検索可能であること。
- ホームエントリの削除：後続のPSLが0の場合に停止し、別クラスタ間の不要な移動を防ぐこと。
- テーブル満杯時：
(m+1)番目の異なるキーが無作為にループせず、適切に失敗を返すこと。 - 敵対的ハッシュ：多数のキーを1つのホームに集中させ、正確性を検証しつつ、メトリクス上でO(m)の探索を露出させる。
質の高い模範回答
「固定容量のRobin Hoodオープンアドレス法テーブルを採用し、占有されているすべてのスロットにキー、値、PSLを格納します。挿入時はホームから線形に探索します。挿入エントリの移動距離が常駐エントリよりも長い場合は両者をスワップし、追い出されたエントリの配置を続けます。これにより、探索クラスタ内でPSLが広義単調増加（非減少）に保たれます。
検索はこの不変条件を利用します。空スロットに遭遇した場合は探索失敗となり、常駐PSLが対象PSLを下回っている場合も、後続のエントリがより短い距離に戻ることはないため失敗となります。削除時に穴を残すことはできないため、PSLが正である限りエントリを後方にシフトし、各PSLをデクリメントします。空スロットまたはPSLが0のエントリでシフトを終了します。期待時間はほぼO(1)、最悪時間はO(m)であるため、負荷係数、P99探索数、シフト長を基準にリサイズするか挿入を拒否するかを判断します。シフトにより要素が移動するため、安定したイテレータやメモリアドレスは保証しません。」
よくある間違い
- 間違い → 衝突時に常に先住の要素を優先する → 後続のエントリの探索長が肥大化する → 挿入PSLが大きい場合にスワップする。
- 間違い → 空スロットでのみ検索を停止する → PSLによる最適化が失われる → 常駐PSLが対象を下回る場合にも停止する。
- 間違い → 削除されたスロットを即座にクリアする → 穴によって後続の探索パスが切断される → 後方シフトを使用しPSLをデクリメントする。
- 間違い → 占有されている任意のエントリでシフトを停止する → 到達不能なキーが残るか、クラスタをまたいで移動してしまう → 連続クラスタのPSLが正の間のみシフトする。
- 間違い → 期待O(1)を最悪O(1)と記述する → 不適切なハッシュや高負荷で破綻する → 最悪ケースがO(m)であることを明示し負荷閾値を適用する。
- 間違い → 安定した参照を保証すると約束する → スワップや削除でエントリが移動する → ハンドルを返すか、間接参照を用いるか、アドレス保証を外す。
フォローアップと回答
動的に拡張するテーブルはいつ再構築（リハッシュ）すべきですか？
設定されたαなどの負荷係数と、P99探索バジェットなどのテール探索レイテンシの双方をトリガーにします。配列の剰余（modulus）が変わるため、スロットを直接コピーするのは誤りであり、再構築時にすべてのホームとPSLを再計算する必要があります。書き込みロック、デュアルテーブル移行、バックグラウンド再構築など、可用性の目標に応じたアプローチを取れますが、まずは一貫性と停止（ポーズ）のポリシーを定義します。
なぜtombstoneを避けるのですか？また後方シフトのコストが高くなりすぎることはありませんか？
tombstoneは削除をO(1)にしますが、再構築まで検索時間を恒常的に悪化させます。後方シフトは削除時に処理を集中させ、クラスタをコンパクトに保ちます。削除が支配的で読み取りが稀な場合はtombstoneと定期的な再構築が勝ることもありますが、読み取りレイテンシを重視する場合はシフトを選択し、移動長を監視するのが適切です。
並行する読み取り・書き込みスレッドをどのように処理しますか？
今回の実装はシングルスレッドです。最も単純な並行バージョンではRead-Writeロックを使用します。読み取り側が移動途中のクラスタを参照しないよう、スワップとシフトは1つの書き込みクリティカルセクション内で行う必要があります。スループットを高めるには、ストライプドロックやイミュータブルなスナップショットを利用できます。ロックフリー設計にはバージョンワード、メモリオードリング、メモリ回収が必要であり、アトミックなスロットポインタだけでは不十分です。
Robin Hoodによって平均検索時間は定数時間になりますか？
一般的な一様ハッシュモデルでは、オープンアドレス法の期待コストは負荷係数に依存します。Robin Hoodは主に探索長の分散とテールの広がりを低減します。高負荷時には平均コストも上昇し、最悪ケースではテーブル全体をスキャンする可能性があるため、分散の改善があっても負荷の制御やベンチマークを省くことはできません。