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

但是，當(dāng)集合中的元素?cái)?shù)量超過(guò)可用內(nèi)存量時(shí)，這些類型的數(shù)據(jù)結(jié)構(gòu)可能會(huì)帶來(lái)問(wèn)題，因?yàn)檫@些類型的數(shù)據(jù)結(jié)構(gòu)會(huì)將所有元素存儲(chǔ)在內(nèi)存中。

這是布隆過(guò)濾器變得有趣的地方。 因?yàn)椴悸∵^(guò)濾器實(shí)際上并未將集合中的所有元素存儲(chǔ)在內(nèi)存中。

布隆過(guò)濾器沒(méi)有將每個(gè)元素放入數(shù)據(jù)結(jié)構(gòu)中，而是僅存儲(chǔ)字節(jié)數(shù)組。 對(duì)于添加到布隆過(guò)濾器的每個(gè)元素，在其數(shù)組中設(shè)置k位。 這些位通常由哈希函數(shù)確定。

要檢查元素是否在集合中，只需檢查通常對(duì)于該項(xiàng)目通常為1的位是否實(shí)際上為1。 如果它們都是一（而不是零），則該項(xiàng)在集合內(nèi)。 如果任何一位都不為1，則該項(xiàng)目不在集合內(nèi)。

對(duì)于每個(gè)數(shù)據(jù)結(jié)構(gòu)，肯定都會(huì)退回到Bloom Filter。 通過(guò)使用上述方法，布隆過(guò)濾器可以說(shuō)元素實(shí)際上不在集合中。 假陽(yáng)性在該集中是可能的，它們?nèi)Q于幾個(gè)因素，例如：

• 字節(jié)數(shù)組的大小
• 每個(gè)元素設(shè)置的位數(shù)（k）
• 集合中的項(xiàng)目數(shù)

通過(guò)調(diào)整上述值，您可以輕松地將誤報(bào)概率提高到可觀的水平，同時(shí)仍然節(jié)省大量空間。

發(fā)現(xiàn)布隆過(guò)濾器后，我開(kāi)始尋找Java實(shí)現(xiàn)。 可悲的是，不存在標(biāo)準(zhǔn)實(shí)現(xiàn)！ 因此，我編寫(xiě)了一個(gè)簡(jiǎn)單快速的Java版Bloom Filter版本。 您可以在GitHub上找到源代碼 。

我的實(shí)現(xiàn)使用：

• MD5哈希
  • 要添加一個(gè)Object，該集合采用hashCode（）方法的值來(lái)計(jì)算MD5哈希。
• 由簡(jiǎn)單的字節(jié)數(shù)組支持
• 實(shí)現(xiàn)Set <Object>接口，盡管該接口中的某些方法將無(wú)法正常工作。

請(qǐng)注意，該項(xiàng)目還使用SizeOf庫(kù)來(lái)獲取內(nèi)存中使用的字節(jié)數(shù)。

我還做了一些快速到期操作，以將過(guò)濾器與Java中的標(biāo)準(zhǔn)ArrayList進(jìn)行比較，并進(jìn)行了一些性能檢查。

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

可以預(yù)期，集合中需要的元素?cái)?shù)量越多，Bloom Filter變得越有用。 當(dāng)確定布隆過(guò)濾器應(yīng)該有多大以及給定集合的最佳k值時(shí)，確實(shí)會(huì)有些棘手，尤其是在集合不斷增長(zhǎng)的情況下。

對(duì)于測(cè)試，我僅向每個(gè)數(shù)據(jù)結(jié)構(gòu)添加了對(duì)象（大小為16個(gè)字節(jié)），然后使用SizeOf庫(kù)獲取使用的真實(shí)空間量。

從上圖可以很容易地看出，一旦數(shù)組變得大于100個(gè)對(duì)象，Bloom Filter的大小效率就會(huì)大大提高。 這種趨勢(shì)持續(xù)到1500個(gè)對(duì)象，而布隆過(guò)濾器需要比ArrayList少22808字節(jié)來(lái)存儲(chǔ)相同數(shù)量的元素。

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

隨時(shí)在GitHub上檢查測(cè)試的源代碼和Bloom Filter實(shí)現(xiàn)本身。

參考：來(lái)自我們的JCG合作伙伴 Isaac Taylor在Programming Mobile博客上的GitHub上的Java中Bloom過(guò)濾實(shí)現(xiàn) 。

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

總結(jié)

以上是生活随笔為你收集整理的GitHub上Java的Bloom Bloom实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。