npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

ca-bloom-filter

v1.0.1

Published

A lightweight, performant bloom filter implementation with a simple API

Downloads

276

Readme

ca-bloom-filter

Coverage Status npm version npm

A lightweight, performant bloom filter implementation with a simple API.

Installing

Via NPM: npm install ca-bloom-filter --save.

Getting Started

After installing

import BloomFilter from 'ca-bloom-filter';

const bloomFilter = new BloomFilter(8, 1); // 8 bit filter using 1 hash.

Example Usage:

import BloomFilter from 'ca-bloom-filter';

const bloomFilter = new BloomFilter(8, 1);

bloom.contains('cheese'); // false
bloom.add('cheese');
bloom.contains('cheese'); // true

Condensed Documentation

Below is a condensed form of the documentation, each is a function that can be found on the BloomFilter object, called like so.

const bloom = new BloomFilter(42, 4);
bloom.contains('cheese'); // false
bloom.add('cheese');
bloom.contains('cheese'); // true

BloomFilter

Basic bloom filter implementation.

const bloom = new BloomFilter(42, 4);
bloom.contains('cheese'); // false
bloom.add('cheese');
bloom.contains('cheese'); // true

| Method | Parameters | Return | | ----------- | -------- | ------ | | .add(key) | key:String | Returns BloomFilter for chaining. | | .contains(key) | key:String | Returns true if the item is within the filter, false otherwise. | | .equals(bloomFilter) | bloomFilter:BloomFilter | Returns true if the bloom filters are equal (same pattern of 1s and 0s), false otherwise.| | .falsePositiveRate() | None | Returns Number false positive rate 0.0 <= fpr <= 1.0. | | .calculateBitIndices(key) | key:String | Returns an array of indices {0 <= index < this.bits} which need to be set. |

SafeBloomFilter

Extends BloomFilter, implements a 'safe' version automatically sized to provide the desired false positive rate over the expected number of inserts. After the expected number of inserts has been passed, attempted inserts will throw errors.

const bloom = new SafeBloomFilter(10000, 0.05);
bloom.contains('cheese'); // false
bloom.add('cheese');
bloom.contains('cheese'); // true

| Method | Parameters | Return | | ----------- | -------- | ------ | | .estimateNumberBits(expectedInserts, falsePositiveRate) | expectedInserts:Number, falsePositiveRate:Number | Returns Number, number of bits this filter requires for safe operation. | | .optimalNumHashFunctions(expectedInserts, bits) | expectedInserts:Number, bits:Number | Returns Number, number of Hash functions this filter requires. | | .add(key) | key:String | Returns BloomFilter for chaining. |

Full Documentation

BloomFilter

const bloom = new BloomFilter(42, 4);
bloom.contains('cheese'); // false
bloom.add('cheese');
bloom.contains('cheese'); // true

add

bloomFilter.add(key)

Adds the given key to the filter and increments the number of inserts.

Parameters
  • key -> An item to add to the filter.
Returns

Returns BloomFilter for chaining.

Example
bloomFilter.add('cheese');

contains

bloomFilter.contains(key)

Tests whether the key is stored in the filter.

Parameters
  • key -> The item to be tested for filter membership.
Returns

Returns true if the item is within the filter, false otherwise.

Example
bloomFilter.contains('cheese');

equals

bloomFilter.equals(bloomFilter)

Tests whether the key is stored in the filter.

Parameters
  • bloomFilter -> A bloom filter instance.
Returns

Returns true if the bloom filters are equal (same pattern of 1s and 0s), false otherwise.

Example
bloomFilter.equals(otherBloom);

falsePositiveRate

bloomFilter.falsePositiveRate() Provides an estimate for the false positive rate with the current inserted elements. This will most likely be lower than the expected false positive rate when the filter is not near the capacity but will trend towards 100% as it fills up.

probFalsePositive = (s / m) ^ k

s - Number of Bits Set.

m - Number of Bits in the Filter

k - Number of Hash Functions used.

http://ws680.nist.gov/publication/get_pdf.cfm?pub_id=903775 http://cglab.ca/~morin/publications/ds/bloom-submitted.pdf

Parameters
  • None
Returns

Returns Number false positive rate 0.0 <= fpr <= 1.0.

Example
bloomFilter.falsePositiveRate();

calculateBitIndices

bloomFilter.calculateBitIndices(key)

Calculate the indices at which we set the bits to 1 in the bit array. https://willwhim.wordpress.com/2011/09/03/producing-n-hash-functions-by-hashing-only-once/

Parameters
  • key -> Item for which we calculate the bits to set.
Returns

Returns an array of indices {0 <= index < this.bits} which need to be set.

Example
bloomFilter.equals(otherBloom);

SafeBloomFilter

const bloom = new SafeBloomFilter(10000, 0.05);
bloom.contains('cheese'); // false
bloom.add('cheese');
bloom.contains('cheese'); // true

add-safe

bloomFilter.add(key)

Only adds an item to the filter if we are below the capacity of the filter, this avoids increasing the actual error rate of the filter above the desired error rate. Throws an error if there are more than expectedInserts made to the filter.

Parameters
  • key -> An item to add to the filter.
Returns

Returns BloomFilter for chaining.

Example
bloomFilter.add('cheese');

estimateNumberBits

SafeBloomFilter.estimateNumberOfBits(expectedInserts, falsePositiveRate)

Estimates the number of bits required to store the given number of elements while maintaining the given false positive rate.

m = - (n Ln P / (Ln 2)^2)

https://en.wikipedia.org/wiki/Bloom_filter

https://stackoverflow.com/questions/658439/how-many-hash-functions-does-my-bloom-filter-need

Parameters
  • expectedInserts -> Expected number of inserts that will be made.
  • falsePositiveRate -> Desired maximum false positive rate.
Returns

Returns Number, number of bits this filter requires for safe operation.

Example
SafeBloomFilter.estimateNumberBits(5000, 0.02);

optimalNumHashFunctions

SafeBloomFilter.optimalNumHashFunctions(expectedInserts, bits)

Calculates the optimal number of hash functions to minimise the false probability for the given m (size) and n (expectedInserts).

k = (m / n) * ln(2).

https://en.wikipedia.org/wiki/Bloom_filter

https://stackoverflow.com/questions/658439/how-many-hash-functions-does-my-bloom-filter-need

Parameters
  • expectedInserts -> Expected number of inserts that will be made.
  • bits -> Number of bits used in the filter.
Returns

Returns Number, number of Hash functions this filter requires.

Example
SafeBloomFilter.optimalNumHashFunctions(5000, 250);

License

See LICENSE file.

Resources