原創(chuàng)不易氮帐，轉(zhuǎn)載請(qǐng)注名出處：http://www.reibang.com/p/c98427267fb4
為什么用
去重是數(shù)據(jù)采集中很重要的一個(gè)點(diǎn)隘截，如果一個(gè)任務(wù)被反復(fù)放到任務(wù)列表中扎阶，這無(wú)疑是對(duì)資源最大的浪費(fèi)。同樣一個(gè)結(jié)果反復(fù)的入庫(kù)也是對(duì)數(shù)據(jù)庫(kù)資源的浪費(fèi)婶芭，且先不說(shuō)內(nèi)存占用會(huì)很大东臀，數(shù)據(jù)變很亂，你存表的時(shí)候唯一鍵也會(huì)讓在寫存表的腳本時(shí)異诚考慮占用到你過(guò)多的時(shí)間惰赋。
但是別慌我們有辦法，conner下面介紹一個(gè)很有用的工具呵哨，布隆過(guò)濾器赁濒，會(huì)讓你的代碼結(jié)構(gòu)變得更加的清晰，也可以應(yīng)對(duì)大批量的去重任務(wù)孟害。
原理
當(dāng)我判斷一張臉的時(shí)候流部，如果眼睛，鼻子纹坐，嘴巴，眉毛舞丛，耳朵都和我們腦海中的某個(gè)人的這些特征是一模一樣的話耘子，我們就有理由相信，這張臉我們認(rèn)識(shí)球切。
同樣這種方式我們放到算法中去谷誓，其實(shí)也是蠻好理解的。如果有個(gè)數(shù)據(jù)它通過(guò)不同方式來(lái)進(jìn)行hash（hash可以理解為找這一張臉的五官）吨凑，我們將每次hash后的值都存放到某個(gè)空間中捍歪。如果每次hash之后的值户辱，都能在我們的空間中能找到的話，我們就有足夠的理由相信糙臼，這個(gè)數(shù)據(jù)是在我們庫(kù)中存在的庐镐。
有人會(huì)問(wèn)，既然這樣我們?yōu)槭裁床话颜麖埬槾娴綌?shù)據(jù)庫(kù)中变逃，然后來(lái)比較必逆？你需要先思考清楚，存一張臉和存五官哪個(gè)占用的內(nèi)存大哪個(gè)方便揽乱？當(dāng)然只通過(guò)幾個(gè)特征就想來(lái)識(shí)別一張臉名眉，是會(huì)存在一定程度的誤判。這種誤判可能會(huì)將不存在的某個(gè)數(shù)據(jù)錯(cuò)判斷為存在的數(shù)據(jù)凰棉，但是它一定不會(huì)將存在的值判斷為不存在损拢，而且這個(gè)誤判率其實(shí)是一個(gè)概率，但其實(shí)我們可以控制這個(gè)概率撒犀。
所以可以理解為布隆過(guò)濾器的數(shù)據(jù)結(jié)構(gòu)就是在你的程序里有一堆在記錄有和沒(méi)有的東西福压，如下圖：
假裝有個(gè)圖（好吧其實(shí)我懶得畫)
實(shí)現(xiàn)
關(guān)鍵其實(shí)需要抓住以下幾個(gè)點(diǎn)：
1，hash(生成我們需要的特征绘证，包括hash的次數(shù)隧膏，以及我們需要hash的方法)。
2嚷那，exits判斷這個(gè)值的hash結(jié)果是否都在我們的空間中胞枕。
3，add將hash后到結(jié)果加入到我們的空間中魏宽。
hash算法確定
下面我分別使用python和java實(shí)現(xiàn)一次
hash方法我們選擇使用google的mmh3方法腐泻，這個(gè)方法的好處是能將一個(gè)值hash成多個(gè)值，而且這個(gè)值我們可以指定為64位還是32位队询，比較方便派桩。這個(gè)方法是用c++來(lái)實(shí)現(xiàn)的，python沒(méi)有辦法看到源碼蚌斩，java版能看到他多位hash的部分邏輯铆惑，有興趣的可以看看。
hash次數(shù)以及內(nèi)存大小的確定送膳，具體計(jì)算方式可以參考這篇博客：
https://my.oschina.net/LucasZhu/blog/1813110
感興趣的可以看看這里我們只關(guān)注結(jié)果：
假如我們需要去重的量capacity=100000000, 可以接受的錯(cuò)誤率error_rate=0.00000001
那么我們所需要的二進(jìn)制位是
m = math.ceil(capacity * math.log2(math.e) * math.log2(1 / error_rate))等于3834023351
需要的內(nèi)存數(shù)是：
mem = math.ceil(m / 8 / 1024 / 1024) 等于458mb
至少需要的hash次數(shù)是：
k = math.ceil(math.log1p(2) * m / capacity) 等于43次
主要有三個(gè)個(gè)方法员魏，hash，add和exits
所以下面開始展示我的代碼(部分)
python：
def get_hashs(self, value):
hashs = list()
for seed in self.seeds:
hash = mmh3.hash(value, seed)
if hash >= 0:
hashs.append(hash)
else:
hashs.append(self.N - hash)
return hashs
def is_exist(self, value):
name = self.key + "_" + str(ord(value[0]) % self.blocknum)
hashs = self.get_hashs(value)
exist = True
for hash in hashs:
exist = exist & self.redis.getbit(name, hash)
return exist
def add(self, value):
name = self.key + "_" + str(ord(value[0]) % self.blocknum)
hashs = self.get_hashs(value)
for hash in hashs:
self.redis.setbit(name, hash, 1)
java:
public boolean add(byte[] bytes) {
if (contains(bytes)) return true;
long hash64 = Hashing.murmur3_128().hashObject(bytes, funnel).asLong();
int hash1 = (int)hash64;
int hash2 = (int)(hash64 >>> 32);
boolean success = true;
for(int i = 1; i <= numHashFunctions; ++i) {
int nextHash = hash1 + i * hash2;
long hashValue;
if(nextHash < 0) {
hashValue = Integer.MAX_VALUE + Math.abs((long) nextHash);
} else {
hashValue = nextHash;
}
success &= mmapData.setBit(hashValue);
}
if (success) mmapData.increment();
return success;
}
public boolean contains(byte[] bytes) {
hashMemNo = additiveHash(bytes,need_memory_time);
long hash64 = Hashing.murmur3_128().hashObject(bytes, funnel).asLong();
int hash1 = (int)hash64;
int hash2 = (int)(hash64 >>> 32);
for(int i = 1; i <= numHashFunctions; ++i) {
int nextHash = hash1 + i * hash2;
long hashValue;
if(nextHash < 0) {
hashValue = ((long) Integer.MAX_VALUE) + Math.abs(nextHash);
} else {
hashValue = nextHash;
}
if(mmapData.getBit(hashValue,hashMemNo) == 0) {
return false;
}
}
return true;
}
優(yōu)勢(shì)和潛在問(wèn)題
優(yōu)勢(shì)
其實(shí)布隆過(guò)濾器本身的結(jié)構(gòu)就是最省內(nèi)存的叠聋，因?yàn)橹挥玫蕉M(jìn)制撕阎，它的每一個(gè)byte上只用0和1，0代表這個(gè)位置上沒(méi)有碌补，1代表代表這個(gè)位置有虏束，當(dāng)數(shù)據(jù)量少的時(shí)候這個(gè)問(wèn)題其實(shí)很好解決棉饶，但當(dāng)去重?cái)?shù)據(jù)量破億的時(shí)候，就會(huì)出現(xiàn)問(wèn)題镇匀。因?yàn)槟阈枰目臻g可能夠照藻，但是計(jì)數(shù)的方式可能會(huì)不夠，在下面我會(huì)再討論坑律。
尋址問(wèn)題
眾所周知岩梳，int類型的長(zhǎng)度2的32次方，因?yàn)榈谝晃槐硎镜氖钦?fù)號(hào)晃择，所以int能表示的最大值是2的31次方減去1也就是2147483647冀值，當(dāng)我們位置的值大于這個(gè)值時(shí)就得換到long類型，long類型的最大值是2的63次方減去1宫屠，看起來(lái)還是ok的列疗。但是當(dāng)我們將這個(gè)值轉(zhuǎn)換為過(guò)濾器中需要的內(nèi)存里空間的時(shí)就有點(diǎn)嚇人了，2的63次方個(gè)byte位需要的空間是2的35次方個(gè)gb的空間浪蹂，這個(gè)空間太大了怎么處理抵栈？以后有機(jī)會(huì)我會(huì)講到。
