プロンプトとコンテキスト
add(value)とmightContain(value)を備えたBloom Filterを実装してください。これはコストの高いルックアップの前に行う事前フィルターです。falseは値が確実に存在しないことを意味し、trueは正規ストアを依然として確認する必要があることを意味します。n、p、m、k、削除、リサイズ、並行処理、およびテストについて扱ってください。
面接官が見ているポイント
正しいメンバーシップセマンティクス
標準的なBloom Filterは偽陽性を許容しますが、偽陰性は許容しません。mightContainという名前は、呼び出し元がtrueをメンバーシップの証明として扱わないようにするためのものです。
説明可能なサイジング
ビット配列の長さmとハッシュ関数の数kは、メモリ、速度、およびエラー率を制御します。パラメータを選択する前に、予想される要素数と許容可能なpを確認してください。
完全な境界条件
優れた回答では、標準的な構造では1つの値を安全に削除できないこと、飽和によって偽陽性率が上昇すること、容量拡張には再構築またはスケーラブルなレイヤー化設計が必要であることを明確に示します。
最初に明確にすべき質問
- 予想される値の数はどれくらいで、許容される偽陽性率pはどれくらいか？
- 値はプロセス間やバージョン間で安定したバイトシーケンスにシリアライズされるか？
- フィルターは追記専用（append-only）か、それとも削除や更新をサポートする必要があるか？
- メモリ、レイテンシ、並行書き込みのバジェットはどの程度か？
- 容量に達したとき、フィルターは再構築、書き込み拒否、レイヤー追加のどれを行うべきか？
- 偽陽性と正規ストアでの確定結果はどのように測定されるか？
30秒で答える要約
「mビットの配列と、十分に独立したk個の位置を使用します。addはそれらk個のビットをセットします。問い合わせ時に0のビットがあれば非存在が証明され、すべて1であれば存在する可能性があることを意味します。予想されるnと目標pに対しては、m=-n ln(p)/(ln2)^2およびk=(m/n)ln2を使用します。標準的なフィルターは安全に削除できないため、削除にはカウンティングバケットが必要であり、容量変更には再構築またはレイヤー化が必要です。テストでは、偽陰性がないこと、サンプリングによる偽陽性率、飽和状態、および並行性の保証を検証します。」
ステップごとの詳細な回答
不変条件とAPIの定義
すべてのビットは0から始まります。安定したハッシュ関数が各値に対してk個のインデックスを生成し、挿入はビットを0から1に変更するのみです。クエリがいずれかの必要なインデックスで0を確認した場合、その値がこの正確な位置のセットを挿入したはずはありません。
mとkの計算
予想されるn個のアイテムと目標の偽陽性率pに対して、m = -n * ln(p) / (ln(2)^2)およびk = (m/n) * ln(2)を使用します。n=1,000,000かつp=1%の場合、mは約960万ビット（約1.14 MiB）、kは約7になります。
ハッシュ関数とビット演算の選択
ダブルハッシュ法を使用すると、位置をh_i(x) = h1(x) + i*h2(x)のmodulo mとして導出でき、k個の完全なハッシュ実装を用意する手間を省けます。バイトエンコーディング、エンディアン、シード値を固定してください。これらを変更すると永続化したフィルターの互換性が失われます。
削除とリサイズの解説
複数の値が同じビットを共有する可能性があるため、1つの削除のためにビットをクリアすると偽陰性が発生するおそれがあります。したがって、標準的なBloom Filterには安全な削除操作がありません。Counting Bloom Filterはメモリコストと引き換えにバケットごとのカウンターを追加します。予想容量が変更された場合は、より大きなフィルターを再構築するか、容量制限のあるレイヤーを複数使用します。
並行処理とライフサイクルの管理
並行読み取りは通常シンプルです。並行書き込みではビットセット操作が失われないようにする必要があります。アトミックOR、シャーディングされたビット配列、または書き込みロックが選択肢になります。容量、m、k、ハッシュアルゴリズム、シード、フォーマットバージョンをまとめて永続化します。
疑似コード
~~~text add(x): for i in 0..k-1: bits[index(hash1(x), hash2(x), i)] = 1
mightContain(x): for i in 0..k-1: if bits[index(hash1(x), hash2(x), i)] == 0: return false return true ~~~
計算量と検証
各操作はk個の位置をチェックまたはセットするため、時間計算量はO(k)で、追加空間計算量はO(m)です。挿入されたすべての値がtrueを返すことをテストし、存在しないランダムサンプルから偽陽性を推定し、容量付近での飽和を観察し、空、重複、シード/バージョン、並行書き込みのケースをカバーします。
| 操作 | 規約 | 計算量 |
|---|---|---|
add(x) | ビットをセットし、メンバーシップの証拠を決して削除しない | O(k) |
mightContain(x) | falseは確実に存在しないこと、trueは存在する可能性があること | O(k) |
| リサイズ | 再構築するか、容量制限付きレイヤーを追加する | アイテム数とmに依存 |
模範解答
「Bloom Filterは確率論的なメンバーシップ事前フィルターです。mビットの配列とk個の位置関数を保持します。挿入によってk個のビットがセットされ、クエリでいずれかの0が見つかればfalseを返し、すべて1であればtrueを返しますが、これは『存在する可能性がある』という意味に過ぎないため、バッキングストアで確認します。nとpからmとkを計算します。100万アイテムで偽陽性率1%の場合、約960万ビットと7つの位置が必要です。ビットが共有されているため標準構造では削除できません。削除にはカウンティングバリアントを使用し、容量の増加に伴ってフィルターを再構築するかレイヤー化します。エンコーディングとシードを固定し、偽陰性がないことをテストし、存在しないサンプルで偽陽性を測定します。」
よくある間違い
trueを証明として扱うこと
必要なすべてのビットが1であることは、他の値に起因する可能性があります。呼び出し元には依然として正規のルックアップが必要です。
1つのハッシュしか使用しないこと
単一のハッシュではビット分布と設計されたエラー率が歪む可能性があります。ダブルハッシュ法を使用するか、複数の位置の背後にある独立性の前提を説明してください。
削除のためにビットをクリアすること
共有ビットをクリアすると、挿入済みの別の値がfalseを返す可能性があります。代わりにカウンティングバケットを使用するか再構築してください。
飽和を無視すること
1になるビットが増えるにつれて、偽陽性率が上昇します。推定要素数とセットされたビットの比率を追跡し、バジェットを超える前に再構築してください。
ヒットのみをテストすること
存在しないサンプル、境界容量、重複挿入のテストがなければ、実装がそのエラー規約を満たしていることを証明できません。
追加の質問と回答
なぜ偽陽性をゼロにできないのか？
異なる値が同じ有限のビットセットにマッピングされる可能性があるためです。メモリを増やし適切なkを選択することでレートを下げられますが、衝突を完全に排除することはできません。
どのような場合にCuckoo Filterを選択するか？
削除、フィンガープリントの保存、またはルックアップの挙動が重要になる場合に比較検討します。名前だけで選ぶのではなく、メモリ、書き込み、削除をベンチマークしてください。
どのように永続化するか？
ビット配列をm、k、ハッシュアルゴリズム、シード、エンコーディングバージョン、推定容量とともに保存します。ロード時にバージョンを検証します。
品質をどのように監視するか？
バックエンドで確認された偽陽性、セットされたビットの比率、推定要素数、ルックアップレイテンシ、再構築回数を測定します。定義された閾値で再構築または新しいレイヤーをトリガーします。
計算式の基礎となる前提は何か？
ハッシュがほぼ均一であること、挿入量がnに近いこと、位置間の十分な独立性を前提としています。実際のデータからのサンプルでキャリブレーションします。
並行書き込みの消失をどのように防ぐか？
アトミックなビット設定またはシャーディングされたロックを使用し、リーダーが完全な書き込みを観察できるようにします。結果整合性（eventual consistency）が許容される場合は、マージされたイミュータブルなスナップショットを公開します。