位数组与Hash函数的联合使用。是一个包含m位的位数组,每位初始化为0,有k个不同的Hash函数,可将集合元素映射到位数组的某一位。插入元素需根据k个hash函数得到k个位,置为1。查询时判断这k个位(有0则该元素肯定不在集合中,都为1则该元素有可能在集合中)
尽管BloomFilter已经尽可能的减小hash碰撞的概率了,但是,并不能彻底消除,因此正如上面提到的: 如果对应的bit位值都为1,那么也不能肯定这个url一定存在 也就是说,BloomFilter其实是存在一定的误判的,这个误判的概率显然和数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关
因为我们在计算开的bit位数组空间大小和哈希函数个数时候m和k都会向上取整,所以真实失误率数值就会变化
参考https://blog.csdn.net/wangpeng322/article/details/100883323