1 package bloom
2
3 import (
4 "github.com/bits-and-blooms/bitset"
5 )
6
7 const defaultSize = 2 << 24
8
9 var seeds = []uint{7, 11, 13, 31, 37, 61}
10
11 type BloomFilter struct {
12 Set *bitset.BitSet
13 Funcs [6]simpleHash
14 }
15
16 func NewBloomFilter() *BloomFilter {
17 bf := new(BloomFilter)
18 for i := 0; i < len(bf.Funcs); i++ {
19 bf.Funcs[i] = simpleHash{defaultSize, seeds[i]}
20 }
21 bf.Set = bitset.New(defaultSize)
22 return bf
23 }
24
25 func (bf *BloomFilter) Add(value string) {
26 for _, f := range bf.Funcs {
27 bf.Set.Set(f.hash(value))
28 }
29 }
30
31 func (bf *BloomFilter) Contains(value string) bool {
32 if value == "" {
33 return false
34 }
35 ret := true
36 for _, f := range bf.Funcs {
37 ret = ret && bf.Set.Test(f.hash(value))
38 }
39 return ret
40 }
41
42 type simpleHash struct {
43 Cap uint
44 Seed uint
45 }
46
47 func (s *simpleHash) hash(value string) uint {
48 var result uint = 0
49 for i := 0; i < len(value); i++ {
50 result = result*s.Seed + uint(value[i])
51 }
52 return (s.Cap - 1) & result
53 }
54
View as plain text