dblchk

README

dblchk

Zero-dependency implementation of a two-bit, single-hash function Bloom filter in Go, achieving significantly better accuracy than a traditional Bloom filter of the same size with excellent performance.

Installation

go get -u github.com/mattwiller/dblchk

Usage

import "github.com/mattwiller/dblchk"

// Create filter with default size (256 KiB): good for up to
// a few hundred of thousand entries with few false positives (< 5-10%)
filter := dblchk.NewFilter(0) 

// Add an item to the filter
filter.Add([]byte("hello, world!"))

// Check whether an item may be included in the filter
if filter.MayContain(item) {
  // Item is (probably) included in the set approximated by the filter
}

Benchmarks

Tested against popular Bloom filter and Cuckoo filter implementations:

goos: linux
goarch: amd64
cpu: 12th Gen Intel(R) Core(TM) i5-12400T

              │    dblchk    │                bloom                 │                  cuckoo                   │
              │    sec/op    │    sec/op     vs base                │     sec/op      vs base                   │
AddElement-12   20.45n ± 16%   26.55n ±  0%  +29.80% (p=0.001 n=10)   5761.50n ±  0%  +28073.59% (p=0.000 n=10)
MayContain-12   21.57n ± 10%   22.72n ±  0%   +5.38% (p=0.022 n=10)     11.99n ±  2%     -44.42% (p=0.000 n=10)

False-Positive Rate

Library	Size	Number of Entries	False Positive Rate
github.com/mattwiller/dblchk	256 KiB	100k	1.3%
github.com/bits-and-blooms/bloom	256 KiB	100k	4.7%
github.com/seiflotfy/cuckoofilter	256 KiB	100k	1.2%

License

Copyright 2026 Matt Willer. Licensed under the 3-Clause BSD License.

Documentation

Index

• Constants
• type Filter
  • func NewFilter(capacity uint) Filter
  • func (filter Filter) Add(element []byte)
  • func (filter Filter) MayContain(element []byte) bool
  • func (filter Filter) Reset()

Constants

const DEFAULT_CAPACITY uint = 1 << 16 /* 256 KiB / sizeof(uint32) */

Types

type Filter

type Filter []uint32

func NewFilter

func NewFilter(capacity uint) Filter

Create a new filter with the given number of 32-bit blocks.

If capacity is set to 0, the default capacity of 64k (=256 KiB) is used.

func (Filter) Add

func (filter Filter) Add(element []byte)

Add the given element to the filter.

func (Filter) MayContain

func (filter Filter) MayContain(element []byte) bool

Check the filter for an element.

If the method returns `true`, the element may be present in the filter. Otherwise, it is guaranteed not to be in the filter.

func (Filter) Reset

func (filter Filter) Reset()

Clear the filter, resetting it back to an empty state.