布隆过滤器

判断value是否存在

常用判断某个value是否存在特定集合中，一般用hashmap，但hashmap存储量较高。
布隆过滤器相对于hashmap而言，牺牲了准确性，但大大降低了空间利用率。
布隆过滤器对值的判断存在两种情况，可能存在和绝对不存在。

原理

布隆过滤器两个要素，长度为n的bit array和m个独立的hash function。对需要写入的数值value进行所有的hash function运算，得到的值和n进行取模运算，得到m个位置，把bit array的这些位置置为1，就完成了一次写入。

举个简单的例子

需要存入的值为’huangyisan’，bit arrary长度为10。
存在三个hash方法，分别对huangyisan运算。
然后对函数执行得到的结果，和长度10取模。
取模得到的值，在bit arrary中对应位置至于1。
那么只要bit arrary的3 5 9 位为1，则代表huangyisan这个字符串存在。

存在的问题

布隆过滤器的两个状态，一个为绝对不存在(negative)，还有一个为可能存在(positive)。所以这个可能存在的状态，会使得得到的结果不一定准确。
出现这个情况，主要是存入数据比较多，导致bit位重叠，所以单单根据bit位为1判断某个字符串是否存在，只能判断为可能存在。
所以在对准确性有一定容忍度的环境，是可以使用布隆选择器的。

问题最大可能进行避免

问题肯定能存在，但可以降低产生的概率，此时就要在使用之前对bit arrary长度，hash function数量等因素进行设定。
一个可以进行评估设定的站点: https://hur.st/bloomfilter/?n=4000&p=1.0E-7&m=&k=2

python实现布隆过滤器

import hashlib

class BloomFilter(object):
    def __init__(self,size):
        self.size = size
        self.arrarylist = [0]*size
        self.hash_func = [hashlib.md5, hashlib.sha1, hashlib.sha224]

    def add_data(self,data):
        for func in self.hash_func:
            index = int(func(data.encode()).hexdigest(),16) % self.size
            self.arrarylist[index] = 1

    def is_data_exist(self,data):
        result = 1 #起始位为1，如果为0，则肯定最终结果为0了。
        for func in self.hash_func:
            index = int(func(data.encode()).hexdigest(),16) % self.size
            #三个index对应value，&操作为1，则返回true
            result &= self.arrarylist[index]
        return True if result == 1 else False

if __name__ == '__main__':
    # 调整bf_size大小，可以改变False positive的值
    bf_size = 1000

    bloom_filter = BloomFilter(bf_size)

    arrarylist = []

    # 添加数值0-99
    for i in range(100):
        bloom_filter.add_data(str(i))
    
    # 对100-999进行is_data_exist方法运算，若返回true，则count+1，计算False positive的值。
    count = 0
    for i in range(100,1000):
        if bloom_filter.is_data_exist(str(i)):
            count+=1

    print('False positive is {0:.2f}%'.format(count/len(range(100,1000))*100))

refer

https://medium.com/@Kadai/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%A4%A7%E4%BE%BF%E7%95%B6-bloom-filter-58b0320a346d
https://hur.st/bloomfilter/?n=4000&p=1.0E-7&m=&k=2
https://zhuanlan.zhihu.com/p/43263751