README
¶
cbfilter
Golang Counting Bloom Filter Implementation
A counting bloom filter implementation with arbitrary number (1-8) of bits per slot. Uses murmur3 and Kirsch and MitzenMacher method for determining k independent hash functions efficiently.
Usage is simple:
const (
N = <number insertions>
B = <bits-per-slot>
FP = <max-false-positive-prob>
)
f, err := NewFilter(N, B, FP)
if err != nil {
log.Error("error creating filter:", err)
return
}
f.AddKey("a")
f.HasKey("a")
f.RemoveKey("a")
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Filter ¶
type Filter struct {
K uint32 // Number of hashes
N uint32 // Number of insertions
R uint32 // Number of putative removals
B uint32 // Number of bits in each slot
M uint32 // Number of slots in filter
MaxCount uint32 // Maximum count for a slot
Data []byte // Slot data
// contains filtered or unexported fields
}
filter is a counting bloom filter, used to approximate the number of differences between InfoStores from different nodes, with minimal network overhead.
func NewFilter ¶
NewFilter allocates and returns a new filter with expected number of insertions N, Number of bits per slot B, and expected value of a false positive < maxFP. Number of bits must be 0 < B <= 8.
Source Files
Click to show internal directories.
Click to hide internal directories.