Probabilistic data structures give you approximate answers to questions about the data they handle. Does the set contain a certain item? How many unique items are in the collection? Which items appear most often? Unlike regular data structures, the answers might not be exact, and you can choose the acceptable error rate.
The unsure module implements probabilistic data structures in Go. It's simple (the core logic for each data structure is 100–300 LOC), fast (often several times faster than other implementations), and has no dependencies except for the standard library.
Bloom filter and Binary fuse filter check if an item is in a set. The binary fuse is more compact, but unlike Bloom, it can't be changed after creation.
Count-min sketch estimates how many times each item has occurred.
HyperLogLog estimates the number of distinct items.
Log-linear histogram and T-digest estimate quantiles of a stream of numbers. The histogram is more accurate, but the T-digest is more compact.
Top-k sketch finds the most frequent items in a stream.
All data structures use the local wyhash implementation for hashing. It performs roughly the same as xxh3 but has a much simpler implementation, without SIMD or assembly.
If there's a feature you need that's missing, please open an issue to discuss it. Only open issues for real use cases you actually have, not for hypothetical situations or features that would just be nice to have.
If you find a bug, open an issue or send a PR. Please don't send PRs with new features — open an issue instead.
Created by Anton Zhiyanov. Released under the MIT License.