willf/bloom alternatives and similar packages
Based on the "Data Structures" category.
Alternatively, view willf/bloom alternatives based on common mentions on social networks and blogs.
-
gods
GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more -
go-datastructures
A collection of useful, performant, and threadsafe Go datastructures. -
golang-set
A simple, battle-tested and generic set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp. -
roaring
Roaring bitmaps in Go (golang), used by InfluxDB, Bleve, DataDog -
gocache
☔️ A complete Go cache library that brings you multiple ways of managing your caches -
boomfilters
Probabilistic data structures for processing continuous, unbounded streams. -
gostl
Data structure and algorithm library for go, designed to provide functions similar to C++ STL -
hyperloglog
HyperLogLog with lots of sugar (Sparse, LogLog-Beta bias correction and TailCut space reduction) brought to you by Axiom -
trie
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. -
go-geoindex
Go native library for fast point tracking and K-Nearest queries -
ttlcache
An in-memory cache with item expiration and generics [Moved to: https://github.com/jellydator/ttlcache] -
go-adaptive-radix-tree
Adaptive Radix Trees implemented in Go -
Bloomfilter
Face-meltingly fast, thread-safe, marshalable, unionable, probability- and optimal-size-calculating Bloom filter in go -
hilbert
Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves. -
goconcurrentqueue
Go concurrent-safe, goroutine-safe, thread-safe queue -
cuckoo-filter
Cuckoo Filter go implement, better than Bloom Filter, configurable and space optimized 布谷鸟过滤器的Go实现,优于布隆过滤器,可以定制化过滤器参数,并进行了空间优化 -
ring
Package ring provides a high performance and thread safe Go implementation of a bloom filter. -
go-rquad
:pushpin: State of the art point location and neighbour finding algorithms for region quadtrees, in Go -
set
A simple Set data structure implementation in Go (Golang) using LinkedHashMap. -
nan
Zero allocation Nullable structures in one library with handy conversion functions, marshallers and unmarshallers -
goset
Set is a useful collection but there is no built-in implementation in Go lang. -
hide
ID type with marshalling to/from hash to prevent sending IDs to clients.
WorkOS - The modern identity platform for B2B SaaS
Do you think we are missing an alternative of willf/bloom or a related project?
README
Bloom filters
A Bloom filter is a concise/compressed representation of a set, where the main requirement is to make membership queries; i.e., whether an item is a member of a set. A Bloom filter will always correctly report the presence of an element in the set when the element is indeed present. A Bloom filter can use much less storage than the original set, but it allows for some 'false positives': it may sometimes report that an element is in the set whereas it is not.
When you construct, you need to know how many elements you have (the desired capacity), and what is the desired false positive rate you are willing to tolerate. A common false-positive rate is 1%. The lower the false-positive rate, the more memory you are going to require. Similarly, the higher the capacity, the more memory you will use. You may construct the Bloom filter capable of receiving 1 million elements with a false-positive rate of 1% in the following manner.
filter := bloom.NewWithEstimates(1000000, 0.01)
You should call NewWithEstimates
conservatively: if you specify a number of elements that it is
too small, the false-positive bound might be exceeded. A Bloom filter is not a dynamic data structure:
you must know ahead of time what your desired capacity is.
Our implementation accepts keys for setting and testing as []byte
. Thus, to
add a string item, "Love"
:
filter.Add([]byte("Love"))
Similarly, to test if "Love"
is in bloom:
if filter.Test([]byte("Love"))
For numerical data, we recommend that you look into the encoding/binary library. But, for example, to add a uint32
to the filter:
i := uint32(100)
n1 := make([]byte, 4)
binary.BigEndian.PutUint32(n1, i)
filter.Add(n1)
Discussion here: Bloom filter
Godoc documentation: https://pkg.go.dev/github.com/bits-and-blooms/bloom
Installation
go get -u github.com/bits-and-blooms/bloom/v3
Contributing
If you wish to contribute to this project, please branch and issue a pull request against master ("GitHub Flow")
This project includes a Makefile that allows you to test and build the project with simple commands. To see all available options:
make help
Running all tests
Before committing the code, please check if it passes all tests using (note: this will install some dependencies):
make deps
make qa
Design
A Bloom filter has two parameters: m, the number of bits used in storage, 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.
Given the particular hashing scheme, it's best to be empirical about this. Note that estimating the FP rate will clear the Bloom filter.