Ecosyste.ms: Packages
An open API service providing package, version and dependency metadata of many open source software ecosystems and registries.
Top 0.3% dependent packages on proxy.golang.org
Top 0.3% dependent repos on proxy.golang.org
Top 1.9% forks on proxy.golang.org
Top 0.1% docker downloads on proxy.golang.org
proxy.golang.org : github.com/bits-and-blooms/bloom/v3
Package bloom provides data structures and methods for creating Bloom filters. A Bloom filter is a representation of a set of _n_ items, where the main requirement is to make membership queries; _i.e._, whether an item is a member of a set. A Bloom filter has two parameters: _m_, a maximum size (typically a reasonably large multiple of the cardinality of the set to represent) and _k_, the number of hashing functions on elements of the set. (The actual hashing functions are important, too, but this is not a parameter for this implementation). A Bloom filter is backed by a BitSet; a key is represented in the filter by setting the bits at each value of the hashing functions (modulo _m_). Set membership is done by _testing_ whether the bits at each value of the hashing functions (again, modulo _m_) are set. If so, the item is in the set. If the item is actually in the set, a Bloom filter will never fail (the true positive rate is 1.0); but it is susceptible to false positives. The art is to choose _k_ and _m_ correctly. In this implementation, the hashing functions used is murmurhash, a non-cryptographic hashing function. This implementation accepts keys for setting as testing as []byte. Thus, to add a string item, "Love": Similarly, to test if "Love" is in bloom: For numeric data, I recommend that you look into the binary/encoding library. But, for example, to add a uint32 to the filter: Finally, there is a method to estimate the false positive rate of a Bloom filter with _m_ bits and _k_ hashing functions for a set of size _n_: You can use it to validate the computed m, k parameters: or You would expect ActualfpRate to be close to the desired fp in these cases. The EstimateFalsePositiveRate function creates a temporary Bloom filter. It is also relatively expensive and only meant for validation.
Registry
-
Source
- Documentation
- JSON
purl: pkg:golang/github.com/bits-and-blooms/bloom/v3
Keywords: bloom, bloom-filters, go
License: BSD-2-Clause
Latest release: 8 months ago
First release: over 1 year ago
Namespace: github.com/bits-and-blooms/bloom
Dependent packages: 314
Dependent repositories: 391
Stars: 1,841 on GitHub
Forks: 215 on GitHub
Docker dependents: 186
Docker downloads: 1,836,823,330
See more repository details: repos.ecosyste.ms
Funding links: https://donate.mcc.org/
Last synced: 7 days ago