布隆过滤器

布隆过滤器，可以简单的理解为布隆过滤器=一个位数组+一系列哈希函数，位数组就是数组中的值只能为0或1，每个值只占用一个bit的数组，初始时位数组中的值全部置为0。

布隆过滤器适合用来在大数据量的场景下判断一个元素是否存在，判断的依据是：对该元素分别使用每个hash函数，根据计算出来的hash值检查位数组中对应位置的值为0还是1，如果所有hash值位置的值都为1，则说明这个元素可能存在；如果有任一hash值位置为0，则说明这个元素一定不存在。

可以这样判断的原因是，布隆过滤器在保存数据时，是将待保存的元素分别放到各个hash函数计算，并根据各个hash函数计算出来的hash值将位数组对应位置的值置为1。正是因为这样，所以在查询的时候如果这个元素存在，则各位置的值一定都为1，因为hash函数一个输入只能对应一个输出。反过来，即使各位置的值都为1也不能说明这个元素一定存在，因为hash函数一个输出可以对应多个输入。

从数据保存的过程也可以看到，布隆过滤器保存数据时并没有保存数据本身，只是在位数组中对这个数据做了个存在的标记。

因为布隆过滤器在数据保存和数据查询时都是根据固定的hash函数计算查找，所以时间复杂度为常数阶，空间效率方面因为本身位数组，且位数组中的每个位置得到了很好的复用，所以空间效率也很高。

布隆过滤器在数据删除方面比较困难，逻辑层面因为删除一个元素的前提是这个元素存在，但布隆过滤器并不能保证这个元素存在。技术层面上在一些资料上看到虽然可以将位数组变成整数数组，数据保存删除时通过累计计数的方式实现，但数据量过大时可能会出现回环计数的情况，回环计数指的是当计数值累加到计算机所能表示的最大值时继续增加会重新从0开始，这个和计算机底层数值运算有关。

因此总结下布隆过滤器的特点：
1.不准确预测。判定不在一定不在，判定在大概率在，也可能不在。
2.不保存数据本身。
3.数据保存和查询效率高，但很难实现删除。

Demo

java中提供了位数组BitSet这个类，python中没有数组的概念，下面是用列表模拟数组实现的一个python版本的布隆过滤器，可以判断给定的url是否已存在。

class BloomFilterDemo():
    __MAX_SIZE = 2 << 20
    __bits = []
    __seeds = [3, 5, 7, 11, 13, 31, 37, 61]
    __functions = []

    def __init__(self):
        self.__bits = [0 for i in range(self.__MAX_SIZE)]
        self.__functions = [HashFunction(self.__MAX_SIZE, self.__seeds[j]) for j in range(len(self.__seeds))]

    def add(self, url):
        if url is not None and url != "":
            for fun in self.__functions:
                self.__bits[fun.hash_code(url)] = 1

    def existed(self, url):
        if url is not None and url != "":
            result = True
            for fun in self.__functions:
                result = result & (True if self.__bits[fun.hash_code(url)] == 1 else False)
            return result


class HashFunction():
    __size = 0
    __seed = 0

    def __init__(self, size, seed):
        self.__size = size
        self.__seed = seed

    def hash_code(self, value):
        result = 0
        for i in range(len(value)):
            result = self.__seed * result + ord(value[i])
        return self.__size - 1 & result


if __name__ == '__main__':
    filter = BloomFilterDemo()
    print(filter.existed("www.baidu.com"))
    filter.add("www.baidu.com")
    print(filter.existed("www.baidu.com"))