How to write a Bloom filter in C++ (opens in new tab)

(blog.michaelschmatz.com)

130 pointsschmatz9y ago19 comments

19 comments

nly9y ago

I feel the use of vector<bool> is an iffy choice.

The Bitcoin codebase has a simple Bloom filter implementation you can take a look at that has been in use for some time

https://github.com/bitcoin/bitcoin/blob/master/src/bloom.h

https://github.com/bitcoin/bitcoin/blob/master/src/bloom.cpp

mavam9y ago

What's wrong with vector<bool> (other than its name)? The interface is exactly what you need to implement a bit-level abstraction in a language where this isn't a first-class primitive.

bmohlenhoff9y ago

std::bitset is also a good choice if the number of desired bits is known at compile time

schmatzOP9y ago

I think this would probably be the best choice after templating the filter

nate_martin9y ago

This example works well for raw data but not for complex types. You could make the filter a template, taking the key and a "hasher" function as template args.

mavam9y ago

Even better: N3980 [1]

This proposal decouples the implementation of hash functions from how types get hashed.

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...

schmatzOP9y ago

Great suggestion; I wasn't sure the idiomatic way to template this, thanks for letting me know!

nate_martin9y ago

Probably something like this:

template< class Key, class Hash = std::hash<Key> > class BloomFilter;

2 more replies

sokoloff9y ago

Learned something today. Thanks for the article.

Minor nit: it will save readers time if you call out that "p is the false positive error rate". (You reference the error rate, but don't attach a variable name to it.) I had to go to an external reference to figure that out, which meant I learned something else of course.

schmatzOP9y ago

Great suggestion, thanks! I've updated the article accordingly :)

barsonme9y ago

Or in C[0] or in Go[1]...

[0] - https://github.com/EricLagergren/bloom [1] - https://github.com/EricLagergren/bloom-c

j_s9y ago

Is there a standard implementation "everybody uses"? Bloomd seems popular as a bloom filter server.

https://github.com/armon/bloomd

m00dy9y ago

I have also experiments about Bloom Filter in python https://github.com/erenyagdiran/BloomFilter

nvcken9y ago

How is your laptop spec ? please

schmatzOP9y ago

Intel Core i7-4980HQ

nvcken9y ago

SSD, RAM ? I think maybe it affects performance

1 more reply

j / k navigate · click thread line to collapse

19 comments

nly9y ago

I feel the use of vector<bool> is an iffy choice.

The Bitcoin codebase has a simple Bloom filter implementation you can take a look at that has been in use for some time

https://github.com/bitcoin/bitcoin/blob/master/src/bloom.h

https://github.com/bitcoin/bitcoin/blob/master/src/bloom.cpp

mavam9y ago

What's wrong with vector<bool> (other than its name)? The interface is exactly what you need to implement a bit-level abstraction in a language where this isn't a first-class primitive.

bmohlenhoff9y ago

std::bitset is also a good choice if the number of desired bits is known at compile time

schmatzOP9y ago

I think this would probably be the best choice after templating the filter

nate_martin9y ago

This example works well for raw data but not for complex types. You could make the filter a template, taking the key and a "hasher" function as template args.

mavam9y ago

Even better: N3980 [1]

This proposal decouples the implementation of hash functions from how types get hashed.

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n398...

schmatzOP9y ago

Great suggestion; I wasn't sure the idiomatic way to template this, thanks for letting me know!

nate_martin9y ago

Probably something like this:

template< class Key, class Hash = std::hash<Key> > class BloomFilter;

2 more replies

sokoloff9y ago

Learned something today. Thanks for the article.