Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BloomFilter ¶
type BloomFilter struct {
// contains filtered or unexported fields
}
BloomFilter https://en.wikipedia.org/wiki/Bloom_filter
func New ¶
func New(n, p int) *BloomFilter
New creates a new Bloom Filter. n is number of elements you want to store and p is false-positive probability.
When you store data on m bits array, the probability of collision is 1/m, so not-collision is 1 - (1/m).
When you use k hash functions and store n elements, the probalibity of not collision is:
(1 - (1/m))^(k*n)
In this case, when you inject non-mebers elements, the probalitity of all bit becames 1 is:
(1 - (1 - (1/m))^(k*n) )^k = (1 - e^(-kn/m))^k
For a given m and n, the value of the number of hash functions k that minimizes the false positive probability is,
k = (m/n)ln(2)
The required number of bits m, the number of inserted elements and a desired false positive probability p (and assuming the optimal value of k is used) can be)
m = n * log2(e) * log2(1/p)
func (*BloomFilter) Contains ¶
func (f *BloomFilter) Contains(data []byte) bool
Contains returns the given data is added or not.
Source Files