-
Notifications
You must be signed in to change notification settings - Fork 7
/
filter.go
60 lines (51 loc) · 1.47 KB
/
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
54
55
56
57
58
59
60
// Package bloom implements Bloom Filter using double hashing
package bloom
import (
"math"
)
// Filter is a generic Bloom Filter
type Filter interface {
Add([]byte) // add an entry to the filter
Test([]byte) bool // test if an entry is in the filter
Size() int // size of the filter in bytes
Reset() // reset the filter to initial state
}
// Classic Bloom Filter
type classicFilter struct {
b []byte
k int
h func([]byte) (uint64, uint64)
}
// New creates a classic Bloom Filter that is optimal for n entries and false positive rate of p.
// h is a double hash that takes an entry and returns two different hashes.
func New(n int, p float64, h func([]byte) (uint64, uint64)) Filter {
k := -math.Log(p) * math.Log2E // number of hashes
m := float64(n) * k * math.Log2E // number of bits
return &classicFilter{b: make([]byte, int(m/8)), k: int(k), h: h}
}
func (f *classicFilter) getOffset(x, y uint64, i int) uint64 {
return (x + uint64(i)*y) % (8 * uint64(len(f.b)))
}
func (f *classicFilter) Add(b []byte) {
x, y := f.h(b)
for i := 0; i < f.k; i++ {
offset := f.getOffset(x, y, i)
f.b[offset/8] |= 1 << (offset % 8)
}
}
func (f *classicFilter) Test(b []byte) bool {
x, y := f.h(b)
for i := 0; i < f.k; i++ {
offset := f.getOffset(x, y, i)
if f.b[offset/8]&(1<<(offset%8)) == 0 {
return false
}
}
return true
}
func (f *classicFilter) Size() int { return len(f.b) }
func (f *classicFilter) Reset() {
for i := range f.b {
f.b[i] = 0
}
}