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.
npm install bloomxx
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.