-
Notifications
You must be signed in to change notification settings - Fork 0
/
bloom.go
69 lines (56 loc) · 1.52 KB
/
bloom.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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package monokage
import (
"strconv"
"github.com/bits-and-blooms/bitset"
)
type bloomFilter struct {
m uint
k uint
b *bitset.BitSet
}
func (bf *bloomFilter) Add(key []byte) {
hash := getMD5Hash(key)
hashA := hash[:int(len(hash)/2)]
hashB := hash[int(len(hash)/2):]
i64_hashA, _ := strconv.ParseInt(hashA, 16, 64)
i64_hashB, _ := strconv.ParseInt(hashB, 16, 64)
for i := uint(0); i < bf.k; i++ {
bf.b.Set(uint(doubleHashing(i64_hashA, i64_hashB, int(i), int(bf.m))))
}
}
func (bf *bloomFilter) Test(key []byte) bool {
hash := getMD5Hash(key)
hashA := hash[:int(len(hash)/2)]
hashB := hash[int(len(hash)/2):]
i64_hashA, _ := strconv.ParseInt(hashA, 16, 64)
i64_hashB, _ := strconv.ParseInt(hashB, 16, 64)
for i := uint(0); i < bf.k; i++ {
if !bf.b.Test(uint(doubleHashing(int64(i64_hashA), int64(i64_hashB), int(i), int(bf.m)))) {
return false
}
}
return true
}
func (bf *bloomFilter) TestAndAdd(key []byte) bool {
var result bool
result = true
hash := getMD5Hash(key)
hashA := hash[:int(len(hash)/2)]
hashB := hash[int(len(hash)/2):]
i64_hashA, _ := strconv.ParseInt(hashA, 16, 64)
i64_hashB, _ := strconv.ParseInt(hashB, 16, 64)
for i := uint(0); i < bf.k; i++ {
if bf.b.Test(uint(doubleHashing(int64(i64_hashA), int64(i64_hashB), int(i), int(bf.m)))) {
result = false
}
bf.b.Set(uint(doubleHashing(int64(i64_hashA), int64(i64_hashB), int(i), int(bf.m))))
}
return result
}
func newBloomFilter(m uint, k uint) *bloomFilter {
return &bloomFilter{
m: m,
k: k,
b: bitset.New(uint(m)),
}
}