bloomfilter.js

function BloomFilter(bitSet, filterSize, numHashes) {
  if (!!filterSize && !!numHashes) {
    if (!bitSet) {
      var numBins = filterSize / 32;
      this._bitSet = new Array(numBins);
      var i;
      for (i = 0; i < numBins; i++) {
        this._bitSet[i] = 0;
      }
    } else {
      this._bitSet = bitSet;
    }
    this._filterSize = filterSize;
    this._numHashes = numHashes;
  }
}

BloomFilter.prototype.add = function(text) {
    var hashes = calcHashes(this._numHashes, text, this._filterSize);
    var i;
    for (i = 0; i < hashes.length; i++) {
        var hash = hashes[i];
        var idx = Math.floor(hash / 32);
        var bit = 1 << (hash % 32);
        this._bitSet[idx] = this._bitSet[idx] | bit;
    }
};

BloomFilter.prototype.addAll = function(textSet) {
    var i;
    for (i = 0; i < textSet.length; i++) {
        var text = textSet[i];
        this.add(text);
    }
};

BloomFilter.prototype.mayContain = function(text) {
    var hashes = calcHashes(this._numHashes, text, this._filterSize);
    var pops = hashes.map(function(hash) {
        var idx = Math.floor(hash / 32);
        var bit = 1 << (hash % 32);
        return (bit & this._bitSet[idx]);
    }.bind(this));
    var pop = true;
    for (i = 0; i < hashes.length; i++) {
        pop = pop && pops[i]
    }
    return pop;
};

function calcHashes(N, text, filterSize) {
    var hashes = calcRollingHashes(text);
    var hash1 = hashes[0],
        hash2 = hashes[1];
    var i, result = [];
    for (i = 0; i < N, i++) {
        var h = 0;
        h += hash2;
        h *= i;
        h %= filterSize;
        h += hash1;
        h %= filterSize;
        result.push(h);
    }
    return result;
}

function calcRollingHashes(text) {
    var j,
        h1 = 0,
        h2 = 0,
        p1 = 1;
        p2 = 1;
    for (j = 0; j < text.length; j++) {
        h1 += (text.charCodeAt(text.length - j - 1) * p1) % (1e9 + 9);
        h2 += (text.charCodeAt(text.length - j - 1) * p2) % (1e9 + 9);
        p1 *= 257;
        p2 *= 419;
        p1 %= 1e9 + 9;
        p2 %= 1e9 + 9;
    }
    h1 %= 1e9 + 9;
    h2 %= 1e9 + 9;
    return [h1, h2];
}