最後の50個のデータコンテンツだけを格納するブルームフィルタ

Question

私のシステムでは、マスタノードとn個のスレーブノードが存在します。マスタノードは着信要求をスレーブノードの1つに配信します。キャッシュメモリのコンテンツを利用するためには、スレーブノードがすでにサービスしていた最後の50リクエスト（受信リクエストのハッシュ）を追跡したいと思います（最後の50リクエストがキャッシュメモリに既に存在すると仮定してノードは要求を速やかに処理する）。 私が研究した限り、ブルームフィルターでは削除が困難です。しかし、それはフィルターを数えることによっても行うことができます。ブルームフィルタを移動ウィンドウのように保つことは本当に可能ですか（50リクエスト後は、新しいリクエストに対応するためにフロントエンドから削除する必要があります）。本当にそうすることが可能か、それともブルームフィルタ（要素の存在を確認するのに十分な速さでなければならない）のような他のフィルタがありますか？

Answer 1

あなたが追跡しているものが50個しかない場合、Bloomフィルタは適切なデータ構造ではないと私は思います。 Bloomフィルタは、メモリに保持できないデータがあり、リモートデータベースなどの一部のリモートデータ構造で不要なルックアップを排除するためにプレフィルタリングを実行する必要がある場合、膨大な量がある場合に適しています。 50個の要素しか持たない場合は、ハッシュテーブルのようなものを使って値を格納する方が良いでしょう。スペースオーバーヘッドを最小限に抑えて、期待されるO（1）時間で正確な答えを得ることができるからです。

あなたが見た最後の50個の要素を追跡したい場合は、O（1）時間内にinsert、lookup、delete、およびdelete-eldestをサポートするリンクされたハッシュテーブルを調べることを検討してください。 JavaのLinkedHashMapはここですばらしいはずです。

希望すると便利です。