Skip to content

Instantly share code, notes, and snippets.

@rrichardsonv
Created April 19, 2018 15:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rrichardsonv/6134d3ab9dc98d970249471dc43120fb to your computer and use it in GitHub Desktop.
Save rrichardsonv/6134d3ab9dc98d970249471dc43120fb to your computer and use it in GitHub Desktop.
class BloomFilter {
static DEFAULT_HASH_FN(size) {
return (hex) => {
const hex32 = XXH.h32(hex);
return (string) => {
return Math.abs(hex32.update(string).digest().toNumber() % size);
};
};
}
static DEFAULT_HEXES = [0xABCD, 0x1234, 0x6789];
constructor(
size = 100,
hashingConstructor = BloomFilter.DEFAULT_HASH_FN,
hexes = BloomFilter.DEFAULT_HEXES
){
const sizedHashGenerator = hashingConstructor(size);
this.bitz = Array(size).fill(0);
this.hashingFns =
hexes.map(sizedHashGenerator)
}
add = (string) => {
this.hash(string)
.forEach((index) => {
this.bitz[index] = 1;
})
}
contains = (string) => {
return this.hash(string).reduce((ans, index) => this.bitz[index] == 1 && ans, true);
}
hash = (string) => {
return this.hashingFns
.map((fn) => fn(string))
}
};
/* UNIT TESTS
describe('BloomFilter', function() {
let bf;
beforeEach(() => {
bf = new BloomFilter();
})
it('returns false when empty', () => {
expect(bf.contains("Brian")).toBe(false);
expect(bf.contains("Sarah")).toBe(false);
expect(bf.contains("Simona")).toBe(false);
});
it('handles one item', () => {
expect(bf.contains("Brian")).toBe(false);
bf.add("Brian");
expect(bf.contains("Brian")).toBe(true);
expect(bf.contains("Sarah")).toBe(false);
expect(bf.contains("Simona")).toBe(false);
});
it('handles many items', () => {
const names = ["Brian", "Simona", "Sarah", "Asim", "John", "Sean", "Jessie", "Paige", "Ashley"];
names.forEach((item) => bf.add(item));
names.forEach((item) => expect(bf.contains(item)).toBe(true));
["Sam", "Chris", "Taylor", "Florence"].forEach((item) => expect(bf.contains(item)).toBe(false));
});
});
*/
@rrichardsonv
Copy link
Author

For my future reference:
Bloom filter probability calculator

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment