布隆過濾器使用場景

之前在《數(shù)學之美》里面看到過布隆過濾器的介紹。那么什么場景下面需要使用布隆過濾器呢？

看下下面幾個問題

• 字處理軟件中，需要檢查一個英語單詞是否拼寫正確
• 在 FBI，一個嫌疑人的名字是否已經(jīng)在嫌疑名單上
• 在網(wǎng)絡爬蟲里，一個網(wǎng)址是否被訪問過
• yahoo, gmail等郵箱垃圾郵件過濾功能

以上這些場景有個共同的問題：如何查看一個東西是否在有大量數(shù)據(jù)的池子里面。

通常的做法有如下幾種思路：

• 數(shù)組
• 鏈表
• 樹、平衡二叉樹、Trie
• Map (紅黑樹)
• 哈希表

哈希函數(shù)

哈希函數(shù)的概念是：將任意大小的數(shù)據(jù)轉(zhuǎn)換成特定大小的數(shù)據(jù)的函數(shù)，轉(zhuǎn)換后的數(shù)據(jù)稱為哈希值或哈希編碼。下面是一幅示意圖

?

可以明顯的看到，原始數(shù)據(jù)經(jīng)過哈希函數(shù)的映射后稱為了一個個的哈希編碼，數(shù)據(jù)得到壓縮。哈希函數(shù)是實現(xiàn)哈希表和布隆過濾器的基礎。

布隆過濾器介紹

• 巴頓.布隆于一九七零年提出
• 一個很長的二進制向量 （位數(shù)組）
• 一系列隨機函數(shù) (哈希)
• 空間效率和查詢效率高
• 不會漏判，但是有一定的誤判率（哈希表是精確匹配）

布隆過濾器原理

布隆過濾器（Bloom Filter）的核心實現(xiàn)是一個超大的位數(shù)組和幾個哈希函數(shù)。假設位數(shù)組的長度為m，哈希函數(shù)的個數(shù)為k

以上圖為例，具體的操作流程：假設集合里面有3個元素{x, y, z}，哈希函數(shù)的個數(shù)為3。首先將位數(shù)組進行初始化，將里面每個位都設置位0。對于集合里面的每一個元素，將元素依次通過3個哈希函數(shù)進行映射，每次映射都會產(chǎn)生一個哈希值，這個值對應位數(shù)組上面的一個點，然后將位數(shù)組對應的位置標記為1。查詢W元素是否存在集合中的時候，同樣的方法將W通過哈希映射到位數(shù)組上的3個點。如果3個點的其中有一個點不為1，則可以判斷該元素一定不存在集合中。反之，如果3個點都為1，則該元素可能存在集合中。注意：此處不能判斷該元素是否一定存在集合中，可能存在一定的誤判率。可以從圖中可以看到：假設某個元素通過映射對應下標為4，5，6這3個點。雖然這3個點都為1，但是很明顯這3個點是不同元素經(jīng)過哈希得到的位置，因此這種情況說明元素雖然不在集合中，也可能對應的都是1，這是誤判率存在的原因。

添加元素

• 將要添加的元素給k個哈希函數(shù)
• 得到對應于位數(shù)組上的k個位置
• 將這k個位置設為1

查詢元素

• 將要查詢的元素給k個哈希函數(shù)
• 得到對應于位數(shù)組上的k個位置
• 如果k個位置有一個為0，則肯定不在集合中
• 如果k個位置全部為1，則可能在集合中簡易實現(xiàn)

簡易實現(xiàn)

import java.util.BitSet;/*** Created by haicheng.lhc on 18/05/2017.** @author haicheng.lhc* @date 2017/05/18*/ public class SimpleBloomFilter {private static final int DEFAULT_SIZE = 2 << 24;private static final int[] seeds = new int[] {7, 11, 13, 31, 37, 61,};private BitSet bits = new BitSet(DEFAULT_SIZE);private SimpleHash[] func = new SimpleHash[seeds.length];public static void main(String[] args) {String value = " stone2083@yahoo.cn ";SimpleBloomFilter filter = new SimpleBloomFilter();System.out.println(filter.contains(value));filter.add(value);System.out.println(filter.contains(value));}public SimpleBloomFilter() {for (int i = 0; i < seeds.length; i++) {func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);}}public void add(String value) {for (SimpleHash f : func) {bits.set(f.hash(value), true);}}public boolean contains(String value) {if (value == null) {return false;}boolean ret = true;for (SimpleHash f : func) {ret = ret && bits.get(f.hash(value));}return ret;}public static class SimpleHash {private int cap;private int seed;public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}public int hash(String value) {int result = 0;int len = value.length();for (int i = 0; i < len; i++) {result = seed * result + value.charAt(i);}return (cap - 1) & result;}} }

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的布隆过滤器(Bloom Filter)的原理和实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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