-
Notifications
You must be signed in to change notification settings - Fork 0
/
filter.go
53 lines (44 loc) · 949 Bytes
/
filter.go
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
package grpc_prom
import (
"github.com/donetkit/contrib-gin/pkg/bitset"
)
const defaultSize = 2 << 24
var seeds = []uint{7, 11, 13, 31, 37, 61}
type BloomFilter struct {
Set *bitset.BitSet
Funks [6]simpleHash
}
func NewBloomFilter() *BloomFilter {
bf := new(BloomFilter)
for i := 0; i < len(bf.Funks); i++ {
bf.Funks[i] = simpleHash{defaultSize, seeds[i]}
}
bf.Set = bitset.New(defaultSize)
return bf
}
func (bf *BloomFilter) Add(value string) {
for _, f := range bf.Funks {
bf.Set.Set(f.hash(value))
}
}
func (bf *BloomFilter) Contains(value string) bool {
if value == "" {
return false
}
ret := true
for _, f := range bf.Funks {
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
}