[置頂] 大數據處理算法二：Bloom Filter算法
來源：程序員人生 發布時間：2015-05-29 08:25:30 閱讀次數：3930次
百度面試題：給定a、b兩個文件，各寄存50億個url，每一個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？
Bloom Filter是由Bloom在1970年提出的1種多哈希函數映照的快速查找算法。通常利用在1些需要快速判斷某個元素是不是屬于集合，但是其實不嚴格要求100%正確的場合。
1. 實例
為了說明Bloom Filter存在的重要意義，舉1個實例：
（實例1）,假定要你寫1個網絡蜘蛛（web crawler）。由于網絡間的鏈接撲朔迷離，蜘蛛在網絡間爬行極可能會構成“環”。為了不構成“環”，就需要知道蜘蛛已訪問過那些URL。給1個URL，怎樣知道蜘蛛是不是已訪問過呢？略微想一想，
（實例2）給定a、b兩個文件，各寄存50億個url，每一個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？
就會有以下幾種方案：
1. 將訪問過的URL保存到數據庫。
2. 用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價就能夠查到1個URL是不是被訪問過了。
3. URL經過MD5或SHA⑴等單向哈希后再保存到HashSet或數據庫。
4. Bit-Map方法。建立1個BitSet，將每一個URL經過1個哈希函數映照到某1位。
方法1~3都是將訪問過的URL完全保存，方法4則只標記URL的1個映照位。
以上方法在數據量較小的情況下都能完善解決問題，但是當數據量變得非常龐大時問題就來了。
方法1的缺點：數據量變得非常龐大后關系型數據庫查詢的效力會變得很低。而且每來1個URL就啟動1次數據庫查詢是否是太小題大做了？
方法2的缺點：太消耗內存。隨著URL的增多，占用的內存會愈來愈多。就算只有1億個URL，每一個URL只算50個字符，就需要5GB內存。
方法3：由于字符串經過MD5處理后的信息摘要長度只有128Bit，SHA⑴處理后也只有160Bit，因此方法3比方法2節省了好幾倍的內存。
方法4消耗內存是相對較少的，但缺點是單1哈希函數產生沖突的幾率太高。還記得數據結構課上學過的Hash表沖突的各種解決方法么？若要下降沖突產生的幾率到1%，就要將BitSet的長度設置為URL個數的100倍。
實質上上面的算法都疏忽了1個重要的隱含條件：允許小幾率的出錯，不1定要100%準確！也就是說少許url實際上沒有沒網絡蜘蛛訪問，而將它們錯判為已訪問的代價是很小的――大不了少抓幾個網頁唄。
例如有 1組字符 arr：”哈哈“，”呵呵“........
字符串：“哈哈”
哈希算法1處理后：8
哈希算法2處理后：1
哈希算法1處理后：3
插入BitArray后
再處理字符串：“呵呵”
哈希算法1處理后：2
哈希算法2處理后：1
哈希算法1處理后：9
繼續插入BitArray后，如果繼續游字符串，繼續以這類方式插入
判斷”在這些字符串是不是包括”嘻嘻“
哈希算法1處理后：0
哈希算法2處理后：1
哈希算法1處理后：7
只要判斷 下標分別為 0,1,7位置的值是不是都為1，以下圖 由于位置0跟位置7的值不為1
所以”嘻嘻“不包括在arr中，反之如果都為1怎包括
java代碼實現以下
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
/**
* BloomFilter算法
*
* @author JYC506
*
*/
public class BloomFilter {
/*哈希函數*/
private List<IHashFunction> hashFuctionList;
/*構造方法*/
public BloomFilter() {
this.hashFuctionList = new ArrayList<IHashFunction>();
}
/*添加哈希函數類*/
public void addHashFunction(IHashFunction hashFunction) {
this.hashFuctionList.add(hashFunction);
}
/*刪除hash函數*/
public void removeHashFunction(IHashFunction hashFunction) {
this.hashFuctionList.remove(hashFunction);
}
/*判斷是不是被包括*/
public boolean contain(BitSet bitSet, String str) {
for (IHashFunction hash : hashFuctionList) {
int hashCode = hash.toHashCode(str);
if(hashCode<0){
hashCode=-hashCode;
}
if (bitSet.get(hashCode) == false) {
return false;
}
}
return true;
}
/*添加到bitSet*/
public void toBitSet(BitSet bitSet, String str) {
for (IHashFunction hash : hashFuctionList) {
int hashCode = hash.toHashCode(str);
if(hashCode<0){
hashCode=-hashCode;
}
bitSet.set(hashCode, true);
}
}
public static void main(String[] args) {
BloomFilter bloomFilter=new BloomFilter();
/*添加3個哈希函數*/
bloomFilter.addHashFunction(new JavaHash());
bloomFilter.addHashFunction(new RSHash());
bloomFilter.addHashFunction(new SDBMHash());
/*長度為2的24次方*/
BitSet bitSet=new BitSet(1<<25);
/*判斷test1很test2重復的字符串*/
String[] test1=new String[]{"哈哈","我","大家","逗比","有錢人性","小米","Iphone","helloWorld"};
for (String str1 : test1) {
bloomFilter.toBitSet(bitSet, str1);
}
String[] test2=new String[]{"哈哈","我的","大家","逗比","有錢的人性","小米","Iphone6s","helloWorld"};
for (String str2 : test2) {
if(bloomFilter.contain(bitSet, str2)){
System.out.println("'"+str2+"'是重復的");
}
}
}
}
/*哈希函數接口*/
interface IHashFunction {
int toHashCode(String str);
}
class JavaHash implements IHashFunction {
@Override
public int toHashCode(String str) {
return str.hashCode();
}
}
class RSHash implements IHashFunction {
@Override
public int toHashCode(String str) {
int b = 378551;
int a = 63689;
int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash = hash * a + str.charAt(i);
a = a * b;
}
return hash;
}
}
class SDBMHash implements IHashFunction {
@Override
public int toHashCode(String str) {
int hash = 0;
for (int i = 0; i < str.length(); i++)
hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
return hash;
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
