README
¶
Bloom
This project bloom filter implementation using Murmur3 hash by github.com/spaolacci/murmur3.
Usage
Importing package
import "github.com/AccelByte/bloom"
Creating new bloom filter
// create new filter with size of 100
// with default Murmur3 hashing strategy
// and 1.e-5 expected false positive probability
b := bloom.New(100)
Putting item into bloom filter
b.Put([]byte("an_item"))
Checking if an item exists
b.MightContain([]byte("an_item"))
Exporting bloom filter to JSON
exported, _ := b.MarshalJSON()
Constructing bloom filter from exported JSON
bloomFilterJSON := &bloom.FilterJSON{}
json.Unmarshal(exported, bloomFilterJSON)
newB := bloom.From(bloomFilterJSON.B, bloomFilterJSON.K)
Documentation
¶
Index ¶
- func EstimateParameters(n uint, p float64) (m uint, k uint)
- type Filter
- func (f *Filter) B() []uint64
- func (f *Filter) K() uint
- func (f *Filter) M() uint
- func (f *Filter) MarshalJSON() ([]byte, error)
- func (f *Filter) MightContain(data []byte) bool
- func (f *Filter) Put(data []byte) *Filter
- func (f *Filter) SetStrategy(s Strategy)
- func (f *Filter) UnmarshalJSON(data []byte) error
- type FilterJSON
- type MURMUR128MITZ64
- type Strategy
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
Filter is wrapper for bloom filter. Cheat sheet:
m: total bits n: expected insertions b: m/n, bits per insertion p: expected false positive probability k: number of hash functions
1) Optimal k = b * ln2 2) p = (1 - e ^ (-kn/m))^k 3) For optimal k: p = 2 ^ (-k) ~= 0.6185^b 4) For optimal k: m = -nlnp / ((ln2) ^ 2)
func From ¶
From populates a bloom filter. bits: long array represents bits k: number of hash functions
func FromWithStrategy ¶
FromWithStrategy populates a bloom filter with strategy. bits: long array represents bits k: number of hash functions s: index strategy
func NewWithFPP ¶
NewWithFPP creates a new bloom filter. n: expected insertions p: expected false positive probability
func NewWithStrategy ¶
NewWithStrategy creates a new bloom filter with strategy. n: expected insertions p: expected false positive probability s: index strategy
func (*Filter) MarshalJSON ¶
MarshalJSON implements json.Marshaler interface.
func (*Filter) MightContain ¶
MightContain query data existence.
func (*Filter) SetStrategy ¶
SetStrategy sets strategy. Do not set it manually except only you unmarshal a bloom filter that using different strategy.
func (*Filter) UnmarshalJSON ¶
UnmarshalJSON implements json.Unmarshaler interface.
type FilterJSON ¶
FilterJSON class wrapper for marshaling/unmarshaling Filter struct.
type MURMUR128MITZ64 ¶
type MURMUR128MITZ64 struct {
}
MURMUR128MITZ64 is a hashing strategy using murmur3
Source Files