Redis BloomFilter佈隆過濾器原理與實現

package main
import (
	"fmt"
	"github.com/bits-and-blooms/bitset"
)
//設置哈希數組默認大小為16
const DefaultSize = 16
//設置種子，保證不同哈希函數有不同的計算方式
var seeds = []uint{7, 11, 13, 31, 37, 61}
//佈隆過濾器結構，包括二進制數組和多個哈希函數
type BloomFilter struct {
	//使用第三方庫
	set *bitset.BitSet
	//指定長度為6
	hashFuncs [6]func(seed uint, value string) uint
}
//構造一個佈隆過濾器，包括數組和哈希函數的初始化
func NewBloomFilter() *BloomFilter {
	bf := new(BloomFilter)
	bf.set = bitset.New(DefaultSize)

	for i := 0; i < len(bf.hashFuncs); i++ {
		bf.hashFuncs[i] = createHash()
	}
	return bf
}
//構造6個哈希函數，每個哈希函數有參數seed保證計算方式的不同
func createHash() func(seed uint, value string) uint {
	return func(seed uint, value string) uint {
		var result uint = 0
		for i := 0; i < len(value); i++ {
			result = result*seed + uint(value[i])
		}
		//length = 2^n 時，X % length = X & (length - 1)
		return result & (DefaultSize - 1)
	}
}
//添加元素
func (b *BloomFilter) add(value string) {
	for i, f := range b.hashFuncs {
		//將哈希函數計算結果對應的數組位置1
		b.set.Set(f(seeds[i], value))
	}
}
//判斷元素是否存在
func (b *BloomFilter) contains(value string) bool {
	//調用每個哈希函數，並且判斷數組對應位是否為1
	//如果不為1，直接返回false，表明一定不存在
	for i, f := range b.hashFuncs {
		//result = result && b.set.Test(f(seeds[i], value))
		if !b.set.Test(f(seeds[i], value)) {
			return false
		}
	}
	return true
}
func main() {
	filter := NewBloomFilter()
	filter.add("asd")
	fmt.Println(filter.contains("asd"))
	fmt.Println(filter.contains("2222"))
	fmt.Println(filter.contains("155343"))
}