布隆過濾器可以單獨存儲最後50個數據內容

Question

嗨，在我的系統中將有一個主節點和n個從節點，其中主節點將傳入請求分配給它的一個從節點。爲了利用緩存內容，我想跟蹤從節點已經服務的最後50個請求（傳入請求的散列）（假設最後50個請求已經存在於緩存中，那麼該節點將快速提供請求）。 據我研究，布隆過濾器中的刪除很困難。但它也可以通過計數過濾器來完成。是否真的有可能讓布隆過濾器像一個移動的窗口一樣（例如在50請求之後它應該從前端刪除以適應新的請求）。是否真的有可能這樣做還是有其他過濾器像布隆過濾器（它應該足夠快以檢查元素的存在）。

Answer 1

如果你只記錄了50件事情，那麼我認爲布隆過濾器不是一個合適的數據結構。如果數據不能保存在內存中，並且想要執行預過濾以消除某些遠程數據結構（如遠程數據庫）中的不必要查找，那麼Bloom過濾器就非常好。如果你只有50個元素，那麼使用類似散列表的東西來存儲這些值幾乎肯定會更好，因爲在最短的空間開銷下，您可以在預期的O（1）時間內得到確切的答案。

如果你想跟蹤你所看到的最後50個元素，可以考慮查看一個鏈接哈希表，它支持O（1）時間內的插入，查找，刪除和刪除最老的所有內容。 Java的LinkedHashMap在這裏應該很棒。

希望這會有所幫助！