Blobloom

A Bloom filter package for Go (golang) with no compile-time dependencies.

This package implements a version of Bloom filters called blocked Bloom filters,
which get a speed boost from using the CPU cache more efficiently
than regular Bloom filters.

Unlike most Bloom filter packages for Go,
this one doesn’t run a hash function for you.
That’s a benefit if you need a custom hash
or you want pick the fastest one for an application.

Usage

To construct a Bloom filter, you need to know how many keys you want to store
and what rate of false positives you find acceptable.

f := blobloom.NewOptimized(blobloom.Config{
    Capacity: nkeys, // Expected number of keys.
    FPRate:   1e-4,  // Accept one false positive per 10,000 lookups.
})

To add a key:

// import "github.com/cespare/xxhash/v2"
f.Add(xxhash.Sum64(key))

To test for the presence of a key in the filter:

if f.Has(xxhash.Sum64(key)) {
    // Key is probably in f.
} else {
    // Key is certainly not in f.
}

The false positive rate is defined as usual:
if you look up 10,000 random keys in a Bloom filter filled to capacity,
an expected one of those is a false positive for FPRate 1e-4.

See the examples/ directory and the
package documentation
for further usage information and examples.

Hash functions

Blobloom does not provide hash functions. Instead, it requires client code to
represent each key as a single 64-bit hash value, leaving it to the user to
pick the right hash function for a particular problem. Here are some general
suggestions:

If you use Bloom filters to speed up access to a key-value store, you might
want to look at xxh3 or xxhash.
If your keys are cryptographic hashes, consider using the first 8 bytes of those hashes.
If you use Bloom filters to make probabilistic decisions, a randomized hash
function such as maphash should prevent
the same false positives occurring every time.

When evaluating a hash function, or designing a custom one,
make sure it is a 64-bit hash that properly mixes its input bits.
Casting a 32-bit hash to uint64 gives suboptimal results.
So does passing integer keys in without running them through a mixing function.

License

Licensed under the Apache License, Version 2.0 (the “License”);
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

 http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an “AS IS” BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.