ブルーム フィルターは、要素がセットに属しているかどうかを判断するために使用されるスペース効率の高いデータ構造です。ハッシュ関数とビット配列を使用して、要素が存在するかどうかを効率的に検索します (誤検知も発生する可能性があります)。 URL 重複検出など、多数の要素を迅速に取得する必要があるシナリオに適しています。
PHP データ構造: ブルーム フィルターを賢く使用して、効率的なコレクションの取得を実現します
はじめに
ブルーム フィルターは、要素がギャザリングに属するかどうかを決定するために使用される、スペース効率の高いデータ構造です。ハッシュ関数とビット配列を使用して、要素が存在するかどうかを効率的に検索します。
原理
ブルームフィルターはビット配列を初期化し、各位置は最初は0です。次に、複数のハッシュ関数を使用して要素がハッシュされ、ビット配列にハッシュ値のインデックスが付けられ、その位置の値が 1 に設定されます。
要素がセットに属している場合、そのハッシュ値はビット配列内で 1 である位置を少なくとも 1 つ見つけます。ただし、セットに属さない要素の 1 の位置を見つけることも可能であり、これは偽陽性と呼ばれます。
実装
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
|
実際のケース: URLの重複を検出
目標: ブルームフィルターを使用して、多数のURLがクロールされたかどうかを迅速に検出します。
実装:
add()
メソッドを呼び出して、フィルタに追加します。 add()
方法将其添加到过滤器中。isExists()
isExists()
メソッドを使用して、それがフィルター内にすでに存在するかどうかをすばやく確認します。存在する場合、その URL はスキップされ、存在しない場合は、新しい URL がフィルタに追加されます。 利点:
以上がPHP データ構造: 効率的なコレクション取得を実現するためのブルーム フィルターの賢明な使用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。