Documentation ¶
Overview ¶
Package bloomflt is implementation of bloom filter with no 3rd party dependencies.
Example ¶
// We expect the set to contains up to 100 elements with acceptable false-positive rate of 0.01% b := New(100, 0.01) b.AddString("value1") if b.ContainsString("value1") { fmt.Println("The set now has 'value1'.") } someID := uint64(123) b.AddUInt64(someID) if b.ContainsUInt64(someID) { fmt.Printf("The set now has ID %v.", someID) }
Output: The set now has 'value1'. The set now has ID 123.
Index ¶
- func CalcOptimalMK(n int, falsePositiveRate float64) (int, int)
- type BloomFilter
- func (b *BloomFilter) AddBytes(value []byte)
- func (b *BloomFilter) AddString(value string)
- func (b *BloomFilter) AddUInt32(value uint32)
- func (b *BloomFilter) AddUInt64(value uint64)
- func (b *BloomFilter) ContainsBytes(value []byte) bool
- func (b *BloomFilter) ContainsString(value string) bool
- func (b *BloomFilter) ContainsUInt32(value uint32) bool
- func (b *BloomFilter) ContainsUInt64(value uint64) bool
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type BloomFilter ¶
type BloomFilter struct {
// contains filtered or unexported fields
}
BloomFilter is an efficient data structure, used to test whether an element is a member of a set.
Bloom filters are probabilistic, which means that false positives are tolerated, but it is guaranteed there will be no false negatives.
In other words, if the bloom filter says an element is NOT in the set, then it is guaranteed the element is not in the set.
If the bloom filter says an element IS in the set, then that means the element is probably there, but it is not guaranteed.
This implementation uses the big.Int type as bitset storage and FNV-1a (Fowler–Noll–Vo) and CRC32 from the builtin hash package as the base hash functions. Additional hash functions are simulated with "Double Hashing Scheme" by Kirsch and Mitzenmacher as explained in "Less Hashing, Same Performance: Building a Better Bloom Filter".
func New ¶
func New(n int, falsePositiveRate float64) *BloomFilter
New creates a new bloom filter with optimal values of m and k for the given given acceptable false-positive rate (value from 0.0 to 1.0).
func NewMK ¶
func NewMK(m int, k int) *BloomFilter
NewMK creates a new bloom filter with bucket size equal to m and number of hash functions equal to k.
func (*BloomFilter) AddBytes ¶
func (b *BloomFilter) AddBytes(value []byte)
AddBytes inserts a bytes value to the set
func (*BloomFilter) AddString ¶
func (b *BloomFilter) AddString(value string)
AddString inserts a string value to the set
func (*BloomFilter) AddUInt32 ¶
func (b *BloomFilter) AddUInt32(value uint32)
AddUInt32 inserts an int value to the set
func (*BloomFilter) AddUInt64 ¶
func (b *BloomFilter) AddUInt64(value uint64)
AddUInt64 inserts an int value to the set
func (*BloomFilter) ContainsBytes ¶
func (b *BloomFilter) ContainsBytes(value []byte) bool
ContainsBytes tests if the set contains the given bytes value
func (*BloomFilter) ContainsString ¶
func (b *BloomFilter) ContainsString(value string) bool
ContainsString tests if the set contains the given string value
func (*BloomFilter) ContainsUInt32 ¶
func (b *BloomFilter) ContainsUInt32(value uint32) bool
ContainsUInt32 tests if the set contains the given int value
func (*BloomFilter) ContainsUInt64 ¶
func (b *BloomFilter) ContainsUInt64(value uint64) bool
ContainsUInt64 tests if the set contains the given int value