1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| package main
import (
"github.com/willf/bitset"
"fmt"
)
const DEFAULT_SIZE = 2<<24
var seeds = []uint{7, 11, 13, 31, 37, 61}
type BloomFilter struct {
set *bitset.BitSet
funcs [6]SimpleHash
}
func NewBloomFilter() *BloomFilter {
bf := new(BloomFilter)
for i:=0;i< len(bf.funcs);i++{
bf.funcs[i] = SimpleHash{DEFAULT_SIZE,seeds[i]}
}
bf.set = bitset.New(DEFAULT_SIZE)
return bf
}
func (bf BloomFilter) add(value string){
for _,f:=range(bf.funcs){
bf.set.Set(f.hash(value))
}
}
func (bf BloomFilter) contains(value string) bool {
if(value == ""){
return false
}
ret := true
for _,f:=range(bf.funcs){
ret = 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 = 0
for i:=0;i< len(value);i++{
result = result*s.seed+uint(value[i])
}
return (s.cap-1)&result
}
func main(){
filter := NewBloomFilter()
fmt.Println(filter.funcs[1].seed)
str1 := "hello,bloom filter!"
filter.add(str1)
str2 := "A happy day"
filter.add(str2)
str3 := "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库，见[github](github.com/willf/bitset)
- 打印结果：
```bash
11
true
true
true
false
|
