Go语言实现布隆过滤器

package main
import (
"github.com/willf/bitset"
"fmt"
)
const DEFAULT_SIZE &＃61; 2<<24
var seeds &＃61; []uint{
7, 11, 13, 31, 37, 61}
type BloomFilter struct {
set *bitset.BitSet
funcs [6]SimpleHash
}
func NewBloomFilter() *BloomFilter {
bf :&＃61; new(BloomFilter)
for i:&＃61;0;i bf.funcs[i] &＃61; SimpleHash{
DEFAULT_SIZE,seeds[i]}
}
bf.set &＃61; bitset.New(DEFAULT_SIZE)
return bf
}
func (bf BloomFilter) add(value string){
for _,f:&＃61;range(bf.funcs){
bf.set.Set(f.hash(value))
}
}
func (bf BloomFilter) contains(value string) bool {
if(value &＃61;&＃61; ""){
return false
}
ret :&＃61; true
for _,f:&＃61;range(bf.funcs){
ret &＃61; ret && bf.set.Test(f.hash(value))
}
return ret
}

type SimpleHash struct{
cap uint
seed uint
}
func (s SimpleHash) hash(value string) uint{
var result uint &＃61; 0
for i:&＃61;0;i result &＃61; result*s.seed&＃43;uint(value[i])
}
return (s.cap-1)&result
}
func main(){
filter :&＃61; NewBloomFilter()
fmt.Println(filter.funcs[1].seed)
str1 :&＃61; "hello,bloom filter!"
filter.add(str1)
str2 :&＃61; "A happy day"
filter.add(str2)
str3 :&＃61; "Greate wall"
filter.add(str3)
fmt.Println(filter.contains(str1))
fmt.Println(filter.contains(str2))
fmt.Println(filter.contains(str3))
fmt.Println(filter.contains("blockchain technology"))
}


这里位数组用了一个第三方的bitset库&＃xff0c;见github&＃xff1a;github.com/willf/bitset

打印结果&＃xff1a;

11
true
true
true
false