原创不易，转载请注名出处：//www.greatytc.com/p/c98427267fb4
为什么用
去重是数据采集中很重要的一个点，如果一个任务被反复放到任务列表中，这无疑是对资源最大的浪费。同样一个结果反复的入库也是对数据库资源的浪费，且先不说内存占用会很大，数据变很乱，你存表的时候唯一键也会让在写存表的脚本时异常考虑占用到你过多的时间。
但是别慌我们有办法，conner下面介绍一个很有用的工具，布隆过滤器，会让你的代码结构变得更加的清晰，也可以应对大批量的去重任务。
原理
当我判断一张脸的时候，如果眼睛，鼻子，嘴巴，眉毛，耳朵都和我们脑海中的某个人的这些特征是一模一样的话，我们就有理由相信，这张脸我们认识。
同样这种方式我们放到算法中去，其实也是蛮好理解的。如果有个数据它通过不同方式来进行hash（hash可以理解为找这一张脸的五官），我们将每次hash后的值都存放到某个空间中。如果每次hash之后的值，都能在我们的空间中能找到的话，我们就有足够的理由相信，这个数据是在我们库中存在的。
有人会问，既然这样我们为什么不把整张脸存到数据库中，然后来比较？你需要先思考清楚，存一张脸和存五官哪个占用的内存大哪个方便？当然只通过几个特征就想来识别一张脸，是会存在一定程度的误判。这种误判可能会将不存在的某个数据错判断为存在的数据，但是它一定不会将存在的值判断为不存在，而且这个误判率其实是一个概率，但其实我们可以控制这个概率。
所以可以理解为布隆过滤器的数据结构就是在你的程序里有一堆在记录有和没有的东西，如下图：
假装有个图（好吧其实我懒得画)
实现
关键其实需要抓住以下几个点：
1，hash(生成我们需要的特征，包括hash的次数，以及我们需要hash的方法)。
2，exits判断这个值的hash结果是否都在我们的空间中。
3，add将hash后到结果加入到我们的空间中。
hash算法确定
下面我分别使用python和java实现一次
hash方法我们选择使用google的mmh3方法，这个方法的好处是能将一个值hash成多个值，而且这个值我们可以指定为64位还是32位，比较方便。这个方法是用c++来实现的，python没有办法看到源码，java版能看到他多位hash的部分逻辑，有兴趣的可以看看。
hash次数以及内存大小的确定，具体计算方式可以参考这篇博客：
https://my.oschina.net/LucasZhu/blog/1813110
感兴趣的可以看看这里我们只关注结果：
假如我们需要去重的量capacity=100000000, 可以接受的错误率error_rate=0.00000001
那么我们所需要的二进制位是
m = math.ceil(capacity * math.log2(math.e) * math.log2(1 / error_rate))等于3834023351
需要的内存数是：
mem = math.ceil(m / 8 / 1024 / 1024) 等于458mb
至少需要的hash次数是：
k = math.ceil(math.log1p(2) * m / capacity) 等于43次
主要有三个个方法，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;
}
优势和潜在问题
优势
其实布隆过滤器本身的结构就是最省内存的，因为只用到二进制，它的每一个byte上只用0和1，0代表这个位置上没有，1代表代表这个位置有，当数据量少的时候这个问题其实很好解决，但当去重数据量破亿的时候，就会出现问题。因为你需要的空间可能够，但是计数的方式可能会不够，在下面我会再讨论。
寻址问题
众所周知，int类型的长度2的32次方，因为第一位表示的是正负号，所以int能表示的最大值是2的31次方减去1也就是2147483647，当我们位置的值大于这个值时就得换到long类型，long类型的最大值是2的63次方减去1，看起来还是ok的。但是当我们将这个值转换为过滤器中需要的内存里空间的时就有点吓人了，2的63次方个byte位需要的空间是2的35次方个gb的空间，这个空间太大了怎么处理？以后有机会我会讲到。
