布隆过滤器是什么? 布隆过滤器是一个高效的数据结构,用于集合成员查询,具有非常低的空间复杂度。 标准布隆过滤器(Standard Bloom Filters,SBF) 基本情况 布隆过滤器是一个含有 m 个元素的位数组(元素为0或1),在刚开始的时候,它的每一位都被设为0。同时还有 k 个独立的哈希函数 h1, h2,..., hk 。需要将集合中的元素加入到布隆过滤器中,然后就可以支持查询了。说明如下: 计算h1(x), h2(x),...,hk(x),其计算结果对应数组的位置,并将其全部置1。一个位置可以被多次置1,但只有一次有效。 当查询某个元素是否在集合中时,计算这 k 个哈希函...