布隆过滤器：一种低空间成本的判断元素是否存在的方式( 二 )

2022-09-13 布隆过滤器

// capacity：容量// falsePositiveRate：误判率func New(capacity uint64, falsePositiveRate float64) *Filter { // bit数量 ln2 := math.Log(2.0) factor := -math.Log(falsePositiveRate) / (ln2 * ln2) bitsCnt := mmath.Max(1, uint64(float64(capacity)*factor)) // 哈希函数数量 hashsCnt := mmath.Max(1, int(ln2*float64(bitsCnt)/float64(capacity))) hashs := make([]*hash.Hash, hashsCnt) for i := 0; i < hashsCnt; i++ {hashs[i] = hash.New() } return &Filter{bits:make([]uint64, (bitsCnt+63)/64),bitsCnt: bitsCnt,hashs:hashs, }}复制代码添加元素添加元素的时候，把每个哈希函数映射的位置都设置为1 。这里需要注意，因为是用的uint64的数组，因此需要把按照bit计算的偏移，转换为按照64位计算的数组下标和对应下标元素里面的偏移。
// 添加元素func (f *Filter) Add(b []byte) { for _, h := range f.hashs {index, offset := f.pos(h, b)f.bits[index] |= 1 << offset }}// 获取对应元素下标和偏移func (f *Filter) pos(h *hash.Hash, b []byte) (uint64, uint64) { hashValue := h.Sum64(b) // 按照位计算的偏移 bitsIndex := hashValue % f.bitsCnt // 因为一个元素64位，因此需要转换 index := bitsIndex / uint64Bits // 在一个元素里面的偏移 offset := bitsIndex % uint64Bits return index, offset}复制代码判断元素是否存在同理，只是这里我们如果发现某一位不为1则可以直接返回false 。
// 元素是否存在// true表示可能存在func (f *Filter) Contains(b []byte) bool { for _, h := range f.hashs {index, offset := f.pos(h, b)mask := uint64(1) << offset// 判断这一位是否位1if (f.bits[index] & mask) != mask {return false} } return true}

【布隆过滤器：一种低空间成本的判断元素是否存在的方式】