bloom

Documentation

Index

• type Filter
  • func New(value []byte, k int) *Filter
  • func NewWithProbability(n int, p float64) *Filter
  • func (bf *Filter) Add(data []byte)
  • func (bf *Filter) Bytes() []byte
  • func (bf *Filter) Hashes() int
  • func (bf *Filter) MayContain(data []byte) bool
  • func (bf *Filter) Size() int

Types

type Filter

type Filter struct {
	// contains filtered or unexported fields
}

Filter is an implementation of a Bloom filter. It uses k hash functions to hash the data and set the corresponding bits to 1. The bits are stored in a byte slice. The size of the byte slice is m/8, where m is the number of bits in the filter.

func New

func New(value []byte, k int) *Filter

New returns a new Bloom filter. The size is defined by the length of the value, which is a byte slice that stores the bits. Therefore the size is always a multiple of 8. K defines the number of hash functions used to hash the data.

func NewWithProbability

func NewWithProbability(n int, p float64) *Filter

NewWithProbability returns a new Bloom filter with the given number of expected elements and the probability of a false positive.

func (*Filter) Add

func (bf *Filter) Add(data []byte)

Add adds the data to the Bloom filter. The data is hashed k times and the corresponding bits are set to 1. It modifies the original byte slice.

func (*Filter) Bytes

func (bf *Filter) Bytes() []byte

Bytes returns a copy of the byte slice that stores the bits.

func (*Filter) Hashes

func (bf *Filter) Hashes() int

func (*Filter) MayContain

func (bf *Filter) MayContain(data []byte) bool

MayContain checks if the data is in the Bloom filter. The data is hashed k times and the corresponding bits are checked. If any of the bits is 0, the data is not in the Bloom filter. If all the bits are 1, the data may be in the Bloom filter, but there is a chance of a false positive.

func (*Filter) Size

func (bf *Filter) Size() int