Bloomfilter alternatives and similar packages
Based on the "Data Structures" category.
Alternatively, view Bloomfilter alternatives based on common mentions on social networks and blogs.
-
golang-set
A simple, battle-tested and generic set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp. -
hyperloglog
HyperLogLog with lots of sugar (Sparse, LogLog-Beta bias correction and TailCut space reduction) brought to you by Axiom -
ttlcache
DISCONTINUED. An in-memory cache with item expiration and generics [Moved to: https://github.com/jellydator/ttlcache] -
hilbert
DISCONTINUED. Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves. -
cuckoo-filter
Cuckoo Filter go implement, better than Bloom Filter, configurable and space optimized 布谷鸟过滤器的Go实现,优于布隆过滤器,可以定制化过滤器参数,并进行了空间优化 -
go-rquad
:pushpin: State of the art point location and neighbour finding algorithms for region quadtrees, in Go -
nan
Zero allocation Nullable structures in one library with handy conversion functions, marshallers and unmarshallers -
hide
A Go type to prevent internal numeric IDs from being exposed to clients using HashIDs and JSON.
CodeRabbit: AI Code Reviews for Developers
Do you think we are missing an alternative of Bloomfilter or a related project?
README
Important: Zeroth, consider if a Cuckoo filter could be right for your use-case.
Face-meltingly fast, thread-safe, marshalable, unionable, probability- and optimal-size-calculating Bloom filter in go
Copyright © 2014-2016,2018 Barry Allard
[MIT license](MIT-LICENSE.txt)
WTF is a bloom filter
TL;DR: **Probabilistic, extra lookup table to track a set of elements kept elsewhere to reduce expensive, unnecessary set element retrieval and/or iterator operations **when an element is not present in the set. It's a classic time-storage tradeoff algoritm.
Properties
See wikipedia for algorithm details
Impact | What | Description |
---|---|---|
Good | No false negatives | know for certain if a given element is definitely NOT in the set |
Bad | False positives | uncertain if a given element is in the set |
Bad | Theoretical potential for hash collisions | in very large systems and/or badly hash.Hash64-conforming implementations |
Bad | Add only | Cannot remove an element, it would destroy information about other elements |
Good | Constant storage | uses only a fixed amount of memory |
Naming conventions
(Similar to algorithm)
Variable/function | Description | Range |
---|---|---|
m/M() | number of bits in the bloom filter (memory representation is about m/8 bytes in size) | >=2 |
n/N() | number of elements present | >=0 |
k/K() | number of keys to use (keys are kept private to user code but are de/serialized to Marshal and file I/O) | >=0 |
maxN | maximum capacity of intended structure | >0 |
p | maximum allowed probability of collision (for computing m and k for optimal sizing) | >0..<1 |
- Memory representation should be exactly
24 + 8*(k + (m+63)/64) + unsafe.Sizeof(RWMutex)
bytes. - Serialized (
BinaryMarshaler
) representation should be exactly72 + 8*(k + (m+63)/64)
bytes. (Disk format is less due to compression.)
Binary serialization format
All values in Little-endian format
Offset | Offset (Hex) | Length (bytes) | Name | Type |
---|---|---|---|---|
0 | 00 | 8 | k | uint64 |
8 | 08 | 8 | n | uint64 |
16 | 10 | 8 | m | uint64 |
24 | 18 | k | (keys) | [k]uint64 |
24+8*k | ... | (m+63)/64 | (bloom filter) | [(m+63)/64]uint64 |
24+8*k+8*((m+63)/64) | ... | 48 | (SHA384 of all previous fields, hashed in order) | [48]byte |
bloomfilter.Filter
conforms toencoding.BinaryMarshaler
and `encoding.BinaryUnmarshaler'
Usage
import "github.com/steakknife/bloomfilter"
const (
maxElements = 100000
probCollide = 0.0000001
)
bf, err := bloomfilter.NewOptimal(maxElements, probCollide)
if err != nil {
panic(err)
}
someValue := ... // must conform to hash.Hash64
bf.Add(someValue)
if bf.Contains(someValue) { // probably true, could be false
// whatever
}
anotherValue := ... // must also conform to hash.Hash64
if bf.Contains(anotherValue) {
panic("This should never happen")
}
err := bf.WriteFile("1.bf.gz") // saves this BF to a file
if err != nil {
panic(err)
}
bf2, err := bloomfilter.ReadFile("1.bf.gz") // read the BF to another var
if err != nil {
panic(err)
}
Design
Where possible, branch-free operations are used to avoid deep pipeline / execution unit stalls on branch-misses.
Get
go get -u github.com/steakknife/bloomfilter # master is always stable
Source
On the web: https://github.com/steakknife/bloomfilter
Git:
git clone https://github.com/steakknife/bloomfilter
Contact
License
[MIT license](MIT-LICENSE.txt)
Copyright © 2014-2016 Barry Allard
*Note that all licence references and agreements mentioned in the Bloomfilter README section above
are relevant to that project's source code only.