Package bloom implements a Bloom filter, a space-efficient probabilistic data structure used to test whether an eleme...
Package implements a Bloom filter, a space-efficient probabilistic data structure used to test whether an element is a member of a set.
A Bloom filter never returns a false negative. If Contains returns false, the
element was definitely never added. It may return a false positive, Contains can
return true for an element that was never added. This trade-off lets the filter
use far less memory than storing the elements themselves, which makes it useful for
membership checks such as caches, deduplication, or "have I seen this before?" tests.
Repository can be found at jeronimoalbi/gnome,
as part of jeronimoalbi's Gno smart contracts monorepo.
1package main
2
3import "gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/bloom"
4
5func main() {
6 // Create a filter expecting up to 1000 items with a 1% false-positive rate.
7 b := bloom.New(1000, 0.01)
8
9 b.AddString("apple").AddString("banana")
10
11 println("Has apple:", b.ContainsString("apple"))
12 println("Has banana:", b.ContainsString("banana"))
13 println("Has cherry:", b.ContainsString("cherry"))
14}
15
16// Output:
17// Has apple: true
18// Has banana: true
19// Has cherry: false
Package bloom implements a Bloom filter, a space-efficient probabilistic data structure used to test whether an element is a member of a set.
A Bloom filter never reports a false negative; If Contains returns false, the element was definitely never added. It may report a false positive.
Contains can return true for an element that was never added. The chance of a false positive grows as more elements are added and can be traded against memory usage when the filter is created.
New creates a filter sized to hold up to maxItems elements while keeping the false-positive probability around falsePositiveRate (for example 0.01 for 1%). It computes the optimal number of bits and hash functions and delegates to NewWithMK. Invalid inputs (maxItems == 0, or a rate outside the open interval (0, 1)) fall back to a minimal usable filter.
NewWithMK creates a filter with an explicit bit-array size m and hash count k. It is the low-level constructor for callers who already know the parameters; Most users should prefer New. Both m and k are clamped to a minimum of 1.
Bloom is a probabilistic set-membership filter.
Add inserts data into the filter.
AddString inserts string data into the filter.
Capacity returns the capacity "m" of the filter.
Contains checks whether data is possibly in the set. A false result means data was definitely never added. A true result means data was probably added but may be a false positive.
ContainsString checks whether string data is possibly in the set. A false result means data was definitely never added. A true result means data was probably added but may be a false positive.
HashFunctions returns the number of hash functions "k" of the filter.
Reset clears all values from the filter, keeping its capacity and hash count.
