前言
在大一剛學(xué)習(xí)編程的時(shí)候吸占，課后習(xí)題有這么一道題：現(xiàn)有一個(gè)數(shù)量為n的有序整數(shù)集合，需要判斷一個(gè)數(shù)是否在這個(gè)集合中涂召。那時(shí)剛學(xué)習(xí)for循環(huán)，所以理所當(dāng)然的敏沉，當(dāng)時(shí)的做法為：
遍歷整個(gè)集合果正，判斷數(shù)字是否存在于集合中
過了一段時(shí)間，學(xué)習(xí)了一些查找算法盟迟，了解了時(shí)間復(fù)雜度的概念秋泳；再次看到了這道題目；此時(shí)的做法則為：
使用二分查找法攒菠，判斷數(shù)字是否存在于集合中
再后來迫皱，學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)相關(guān)的知識(shí)，再次碰到了這道題目要尔；不同的是這次的集合是無序的舍杜。這個(gè)時(shí)候想到了兩種做法；
- 第一種：
先使用快速排序?qū)⒓吓判蛘栽缓笤偈褂枚植檎疫M(jìn)行判斷
但快排本身的時(shí)間復(fù)雜度也有O(nlogn)既绩，只為了查找一條數(shù)據(jù)的話還是有點(diǎn)慢的；于是有了第二種做法还惠。 - 第二種：
使用HashMap來存放數(shù)據(jù)饲握，然后進(jìn)行判斷
使用此方法，時(shí)間復(fù)雜度只需O(1)
曾經(jīng)我以為HashMap算是這類問題的萬能適用解了蚕键；但后來我又遇到了這么一個(gè)問題救欧，依舊是數(shù)量為n的無序集合，判斷一個(gè)整數(shù)是否存在其中锣光，不過不同的是n的值為一億笆怠。
一開始我自然是直接用HashMap處理了，但是在將數(shù)據(jù)存儲(chǔ)至HashMap的時(shí)候內(nèi)存溢出了誊爹，此時(shí)才明白除了時(shí)間復(fù)雜度以外蹬刷，我們還需要考慮到空間問題。這時(shí)候布隆過濾就應(yīng)運(yùn)而生了频丘。
原理
布隆過濾器使用二進(jìn)制向量結(jié)合hash函數(shù)來記錄任意一條數(shù)據(jù)是否已經(jīng)存在于集合中办成。
布隆過濾器的執(zhí)行流程為：
- 首先申請(qǐng)包含SIZE個(gè)bit位的Bit集合，并將所有Bit置0搂漠。
- 然后使用數(shù)種（k）不同的哈希函數(shù)對(duì)目標(biāo)數(shù)據(jù)進(jìn)行哈希計(jì)算并得到k個(gè)哈希值（確保哈希值不超過SIZE大杏芈），然后將Bit集合中以哈希值為下標(biāo)所處的bit值置為1，由于使用了k個(gè)哈希函數(shù)而克，因此記錄一條數(shù)據(jù)的信息將在Bit集合中把k個(gè)bit值置為1靶壮。
- 由于哈希函數(shù)的穩(wěn)定性，任意兩條相同的數(shù)據(jù)在Bit集合中所對(duì)應(yīng)的k個(gè)bit位置是完全相同的员萍。那么在檢測某一條數(shù)據(jù)是否已經(jīng)在Bit集合中有記錄時(shí)亮钦，只需檢測該條數(shù)據(jù)的k個(gè)哈希值在Bit集合中對(duì)應(yīng)的位置的bit是否均已被標(biāo)記為1，相反的只要其存在一個(gè)哈希值對(duì)應(yīng)的bit位置未被標(biāo)記為1充活，則證明該值未被記錄過蜂莉。
使用示例
布隆過濾器的示例如下：
大體過程為：
- 首先初始化一個(gè)二進(jìn)制的數(shù)組，長度設(shè)為 L（圖中為 8）混卵，同時(shí)初始值全為 0 映穗。
- 當(dāng)寫入一個(gè) A1=1000 的數(shù)據(jù)時(shí)，需要進(jìn)行 H 次 hash 函數(shù)的運(yùn)算（這里為 2 次）幕随；與 HashMap 有點(diǎn)類似蚁滋，通過算出的 HashCode 與 L 取模后定位到 0、2 處赘淮，將該處的值設(shè)為 1辕录。
- A2=2000 也是同理計(jì)算后將 4、7 位置設(shè)為 1梢卸。
- 當(dāng)有一個(gè) B1=1000 需要判斷是否存在時(shí)走诞，也是做兩次 Hash 運(yùn)算，定位到 0蛤高、2 處蚣旱，此時(shí)他們的值都為 1 ，所以認(rèn)為 B1=1000 存在于集合中戴陡。
- 當(dāng)有一個(gè) B2=3000 時(shí)塞绿，也是同理。第一次 Hash 定位到 index=4 時(shí)恤批，數(shù)組中的值為 1异吻，所以再進(jìn)行第二次 Hash 運(yùn)算，結(jié)果定位到 index=5 的值為 0喜庞，所以認(rèn)為 B2=3000 不存在于集合中诀浪。
優(yōu)缺點(diǎn)
- 優(yōu)點(diǎn)
時(shí)間復(fù)雜度為O(n)，且布隆過濾器不需要存儲(chǔ)元素本身赋荆，使用位陣列笋妥，占用空間也很小懊昨。 - 缺點(diǎn)
通過布隆過濾窄潭，我們能夠準(zhǔn)確判斷一個(gè)數(shù)不存在于某個(gè)集合中，但對(duì)于存在于集合中這個(gè)結(jié)論，布隆過濾會(huì)有誤報(bào)（可能存在兩組不同數(shù)據(jù)但其多個(gè)哈希值完全一樣的情況）嫉你。但是通過控制Bit集合的大性碌邸（即SIZE）以及哈希函數(shù)的個(gè)數(shù)，可以將出現(xiàn)沖突的概率控制在極小的范圍內(nèi)幽污，或者通過額外建立白名單的方式徹底解決哈希沖突問題嚷辅。
誤判率計(jì)算公式為(1 – e(-nk/SIZE))k，其中n為目標(biāo)數(shù)據(jù)的數(shù)量距误，SIZE為Bit集合大小簸搞，k為使用的哈希函數(shù)個(gè)數(shù)；假設(shè)現(xiàn)有一千萬條待處理數(shù)據(jù)准潭，Bit集合大小為2^30（約10億趁俊，即占用內(nèi)存128MB），使用9個(gè)不同的哈希函數(shù)刑然，計(jì)算可得任意兩條數(shù)據(jù)其9次哈希得到的哈希值均相同（不考慮順序）的概率為2.6e-10寺擂，約為38億分之一。
