D56D01CA2034A0…4C8AD501A0AB

Arguments · 9

1. #1bloom
2. #2README.md
3. #3# Bloom Package 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](https://github.com/jeronimoalbi/gnome), as part of `jeronimoalbi`'s Gno smart contracts monorepo. ## Usage [embedmd]:# (filetests/readme_filetest.gno go) ```go package main import "gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/bloom" func main() { // Create a filter expecting up to 1000 items with a 1% false-positive rate. b := bloom.New(1000, 0.01) b.AddString("apple").AddString("banana") println("Has apple:", b.ContainsString("apple")) println("Has banana:", b.ContainsString("banana")) println("Has cherry:", b.ContainsString("cherry")) } // Output: // Has apple: true // Has banana: true // Has cherry: false ```
4. #4bloom.gno
5. #5// 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. package bloom import ( "math" "gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/bitset" "gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/murmur3" ) // Bloom is a probabilistic set-membership filter. type Bloom struct { bits bitset.BitSet m uint64 // Number of bits in the filter k uint64 // Number of hash positions set per element } // 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. func NewWithMK(m, k uint64) *Bloom { if m < 1 { m = 1 } if k < 1 { k = 1 } return &Bloom{ bits: bitset.New(m), m: m, k: k, } } // 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. func New(maxItems uint64, falsePositiveRate float64) *Bloom { if maxItems == 0 || falsePositiveRate <= 0 || falsePositiveRate >= 1 { return NewWithMK(1, 1) } n := float64(maxItems) ln2 := math.Ln2 // m = ceil( -(n * ln(p)) / (ln2)^2 ) m := uint64(math.Ceil(-(n * math.Log(falsePositiveRate)) / (ln2 * ln2))) // k = round( (m/n) * ln2 ) k := uint64(math.Round((float64(m) / n) * ln2)) return NewWithMK(m, k) } // Capacity returns the capacity "m" of the filter. func (b *Bloom) Capacity() uint64 { return b.m } // HashFunctions returns the number of hash functions "k" of the filter. func (b *Bloom) HashFunctions() uint64 { return b.k } // Reset clears all values from the filter, keeping its capacity and hash count. func (b *Bloom) Reset() *Bloom { b.bits.ClearAll() return b } // Add inserts data into the filter. func (b *Bloom) Add(data []byte) *Bloom { h1, h2 := hashes(data) for i := uint64(0); i < b.k; i++ { b.bits.Set(b.index(h1, h2, i)) } return b } // AddString inserts string data into the filter. func (b *Bloom) AddString(data string) *Bloom { return b.Add([]byte(data)) } // 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. func (b *Bloom) Contains(data []byte) bool { h1, h2 := hashes(data) for i := uint64(0); i < b.k; i++ { if !b.bits.IsSet(b.index(h1, h2, i)) { return false } } return true } // 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. func (b *Bloom) ContainsString(data string) bool { return b.Contains([]byte(data)) } // index returns the i-th bit position for an element using double hashing. func (b *Bloom) index(h1, h2 uint32, i uint64) uint64 { return (uint64(h1) + i*uint64(h2)) % b.m } // hashes splits a single 64-bit MurmurHash3 hash of data into two 32-bit halves // used as the seeds for double hashing. func hashes(data []byte) (h1, h2 uint32) { sum := murmur3.Sum64(data) return uint32(sum >> 32), uint32(sum) }
6. #6gnomod.toml
7. #7module = "gno.land/p/g17khqpukees4237dtn3astzapmp462vjhsz6st4/bloom" gno = "0.9"
8. #8/gno.MemPackageType
9. #9 MPUserAll