Documentation
¶
Overview ¶
Package filter defines and implements data structures and interfaces for skipping index.
Index ¶
- Constants
- func OptimalBitsSize(n int) int
- type BloomFilter
- func (bf *BloomFilter) Add(item []byte) bool
- func (bf *BloomFilter) Bits() []uint64
- func (bf *BloomFilter) MightContain(item []byte) bool
- func (bf *BloomFilter) N() int
- func (bf *BloomFilter) Reset()
- func (bf *BloomFilter) ResizeBits(n int)
- func (bf *BloomFilter) SetBits(bits []uint64)
- func (bf *BloomFilter) SetN(n int)
Constants ¶
View Source
const ( // B specifies the number of bits allocated for each item. // Using B=16 (power of 2) maintains memory alignment and enables shift-based math. // With 8k items per block: memory = 8192 * 16 / 8 = 16KB per block. // FPR with k=10, B=16: ~0.042%. B = 16 )
Variables ¶
This section is empty.
Functions ¶
func OptimalBitsSize ¶
OptimalBitsSize returns the optimal number of uint64s needed for n items. With B=16, this is simply n/4 (n >> 2), with a minimum of 1.
Types ¶
type BloomFilter ¶
type BloomFilter struct {
// contains filtered or unexported fields
}
BloomFilter is a probabilistic data structure designed to test whether an element is a member of a set.
func NewBloomFilter ¶
func NewBloomFilter(n int) *BloomFilter
NewBloomFilter creates a new Bloom filter with the number of items n and false positive rate p.
func (*BloomFilter) Add ¶
func (bf *BloomFilter) Add(item []byte) bool
Add adds an item to the Bloom filter.
func (*BloomFilter) Bits ¶
func (bf *BloomFilter) Bits() []uint64
Bits returns the underlying bitset.
func (*BloomFilter) MightContain ¶
func (bf *BloomFilter) MightContain(item []byte) bool
MightContain checks if an item might be in the Bloom filter.
func (*BloomFilter) ResizeBits ¶
func (bf *BloomFilter) ResizeBits(n int)
ResizeBits resizes the underlying bitset.
func (*BloomFilter) SetBits ¶
func (bf *BloomFilter) SetBits(bits []uint64)
SetBits sets the underlying bitset.
Source Files
Click to show internal directories.
Click to hide internal directories.