布隆过滤器的实现思路
3.布隆过滤器的公式
4.实际应用场景
----
1.布隆过滤器简介
布隆过滤器(Bloom Filter)是由一个很长的bit数组和一系列哈希函数组成的。...布隆过滤器的实现思路
①设数据集合A={a1,a2,a3,…,an},含有n个元素作为待操作的集合;
②Bloom Filter用一个长度为m的位向量V表示集合中的元素,位向量初始值全为0;
③k个具有均匀分布特性的散列函数...h1,h2,…,hk;
④对于要加入的元素,首先经过k个散列函数%m,产生k个随机数h1,h2,…,hk,使向量V的相应位置h1,h2,…,hk均
置位为1。...上的值,若全为1,则该元素已经在之前的集合中;若至少有一个0存在,表明此元素不在之前
的集合中,为新元素。...设bit数组大小为m,样本数量为n,失误率为p。
由题可知 n = 100亿,p = 0.01%
根据布隆过滤器的大小m公式,求得 m = 19.19n,向上取整为 20n。