bloom filters backed by xxhash
Yet another Bloom filter implementation for node.js. Everybody has to write one, as you know. Backed by Xxhash via node-xxhash. Xxhash is a fast general-purpose hash, which is all a bloom filter needs. Three variations are provided: a straight Bloom filter, a counting filter (from which items can be removed), and a straight Bloom filter backed by redis. The first two have synchronous APIs. The redis one perforce requires callbacks.
Not published on npm yet because I'm not yet satisfied with the cleanliness of the API.
To create a filter, pass an options hash to the constructor:
var options =bits: 1024hashes: 7seeds: 1 2 3 4 5 6 7;filter = options;
You can pass in seeds for the hash functions if you like, or they'll be randomly generated. Seeds must be integers.
To create a filter optimized for the number of items you'll be storing and a desired error rate:
filter = BloomFilter.createOptimal(estimatedItemCount, errorRate);
The error rate parameter is optional. It defaults to 0.005, or a 0.5% rate.
Adds the given item to the filter. Can also accept buffers and arrays containing strings or buffers:
filter.add(['cat', 'dog', 'coati', 'red panda']);
To test for membership:
To clear the filter:
Uses about 8 times as much space as the regular filter. Basic usage is exactly the same as the plain Bloom filter:
filter = hashes: 8 bits: 1024 ;`filter2 = CountingFilter.createOptimal(estimatedItemCount, optionalErrorRate);
Add a list, test for membership, then remove:
filteradd'cat' 'dog' 'coati' 'red panda';filterhas'cat'; // returns truefilterremove'cat';filterhas'cat'; // returns false most of the time
The counting filter tracks its overflow count in
filter.overflow. Overflow will be non-zero if any bit has been set more than 255 times. Once the filter has overflowed, removing items is no longer reliable.
Check for overflow:
filterhasOverflowed; // returns booleanfilteroverflow; // integer count of number of times overflow occurred
This is a plain vanilla bloom filter backed by redis. Its api is asychronous.
RedisFiltercreateOrReadkey: 'cats' // the key used to store data in redis; will also set 'cats:meta'bits: 1024 // filter size in bitshashes: 8 // number of hash functionsredis: rediscreateClientport host // redis client to usefilteradd'cat' 'jaguar' 'lion' 'tiger' 'leopard'filterhas'caracal'assertresult === false;;;;
The options hash can also specify
port, which will be used to create a redis client.
createOrRead() will attempt to find a filter saved at the given key and create one if it isn't found.
Returns a filter sized for the given item count and desired error rate, with other options as specified in the
Clear all bits.
Delete the filter from redis.