布隆過濾器是集數據結構的一種 。 對于那些不了解的對象，“設置數據結構”僅包含一個主要方法。 它僅用于確定特定元素是否包含在一組元素中。 大多數數據結構（例如Hash Map ， Linked List或Array ）都可以相當輕松地創建此函數。 您只需要在數據結構中搜索特定元素。

但是，當集合中的元素數量超過可用內存量時，這些類型的數據結構可能會帶來問題，因為這些類型的數據結構會將所有元素存儲在內存中。

這是布隆過濾器變得有趣的地方。 因為布隆過濾器實際上并未將集合中的所有元素存儲在內存中。

布隆過濾器沒有將每個元素放入數據結構中，而是僅存儲字節數組。 對于添加到布隆過濾器的每個元素，在其數組中設置k位。 這些位通常由哈希函數確定。

要檢查元素是否在集合中，只需檢查通常對于該項目通常為1的位是否實際上為1。 如果它們都是一（而不是零），則該項在集合內。 如果任何一位都不為1，則該項目不在集合內。

對于每個數據結構，肯定都會退回到Bloom Filter。 通過使用上述方法，布隆過濾器可以說元素實際上不在集合中。 假陽性在該集中是可能的，它們取決于幾個因素，例如：

• 字節數組的大小
• 每個元素設置的位數（k）
• 集合中的項目數

通過調整上述值，您可以輕松地將誤報概率提高到可觀的水平，同時仍然節省大量空間。

發現布隆過濾器后，我開始尋找Java實現。 可悲的是，不存在標準實現！ 因此，我編寫了一個簡單快速的Java版Bloom Filter版本。 您可以在GitHub上找到源代碼 。

我的實現使用：

• MD5哈希
  • 要添加一個Object，該集合采用hashCode（）方法的值來計算MD5哈希。
• 由簡單的字節數組支持
• 實現Set <Object>接口，盡管該接口中的某些方法將無法正常工作。

請注意，該項目還使用SizeOf庫來獲取內存中使用的字節數。

我還做了一些快速到期操作，以將過濾器與Java中的標準ArrayList進行比較，并進行了一些性能檢查。

• 使用不同的k值將元素添加到集合中所需的時間
• 集合的大小與不同級別的數組列表

可以預期，集合中需要的元素數量越多，Bloom Filter變得越有用。 當確定布隆過濾器應該有多大以及給定集合的最佳k值時，確實會有些棘手，尤其是在集合不斷增長的情況下。

對于測試，我僅向每個數據結構添加了對象（大小為16個字節），然后使用SizeOf庫獲取使用的真實空間量。

從上圖可以很容易地看出，一旦數組變得大于100個對象，Bloom Filter的大小效率就會大大提高。 這種趨勢持續到1500個對象，而布隆過濾器需要比ArrayList少22808字節來存儲相同數量的元素。

上圖顯示了以秒為單位的時間（在2012年早期的iMac上），將元素添加到具有不同位數（k）的列表中的時間。 隨著k的增加，時間會相當緩慢地增加到10位。 但是，任何超過10的東西都會變得非常昂貴，設置100位需要一整秒才能完成。

隨時在GitHub上檢查測試的源代碼和Bloom Filter實現本身。

參考：來自我們的JCG合作伙伴 Isaac Taylor在Programming Mobile博客上的GitHub上的Java中Bloom過濾實現 。

翻譯自: https://www.javacodegeeks.com/2012/11/bloom-filter-implementation-in-java-on-github.html