布隆过滤器的设计思想原创

算法设计布隆过滤器的设计思想。简介。布隆过滤器是1970年由布隆提出，采用二进制向量和一系列随机映射函数组成，用于快速判断元素是否在集合中。思考一个问题，如果有10亿个随机数，怎么判断某个数是否存在？常规思路放到哈希map中，那么当有一个X，经过一次运算就可以确定在哈希map中的位置。那么因为有11个随机数，那么会带来什么样的问题呢？就是空间上的问题，假如每一个随机占四个字节，总共就要占四个G左右的存储空间，空间消耗非常的大。如何解决呢？就是采用未数组的形式，不直接存储元素，而是存储它是否存在的状态。如果存储零，则表示不存在，一表示存在，节约大量的存储空间。实际的实现原理，有一个集合和初始状态都为零的位数组，集合中的元素经过N个散列函数计算出在数组当中的位置。

并且修改数组当中的位置的元素由零变为一。当有某个元素X同样经过N个散列函数进行运算，得到的结果如果都为一，则判断在集合中，如果存在零，则判断当前元素不存在于集合中。那么优劣分析，首先从优势上面来说，第一点空间利用率非常高，可以存储全局的数据，第二点可以并行散列运算，时间快。它的劣势也非常明显，因为哈希有概率冲突，所以会产生误判。另外，未数组的大小及散列函数的选择复杂性比较高。