Categories
interview

Bloomfilter in Js

We use multiple hash functions below to evenly space out the keys in the Bloom filter.

const arr = Array(Math.pow(2, 22) - 1).fill(0);
const HASHES_COUNT = 6;
const keys = ['John', 'Smith', 'Adam'];

const getHashes = (inp) => {
  const hashes = [];
  for (let i = 0; i < HASHES_COUNT; i++) {
    hashes.push(Math.abs(inp.split('').reduce((acc, curr) =>
      (acc >> i) - acc + curr.charCodeAt(0) | 0, 0)));
  }
  return hashes;
};

for (let key of keys) {
  const hashes = getHashes(key);
  for (const hash of hashes) {
    arr[hash] = 1;
  }
}

const isPresent = (key) => {
  const hashes = getHashes(key);
  for (const hash of hashes) {
    if (!arr[hash]) {
      return false;
    }
  }
  return true;
};

console.log(isPresent('John')); // true
console.log(isPresent('Smith')); // true
console.log(isPresent('Adam')); // true
console.log(isPresent('Sam')); // false
console.log(isPresent('Harry')); // false

Demo