Bloom Filter

// JavaScript Bloom Filter implementation
class BloomFilter {
  constructor(size = 100, hashCount = 3) {
    this.size = size;
    this.hashCount = hashCount;
    this.bitArray = new Array(size).fill(0);
  }

  // Hash funktion
  _hash(value, seed) {
    let hash = 0;
    const str = value.toString();
    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) + hash) + str.charCodeAt(i) + seed;
      hash = hash & hash; // Konverter til 32-bit heltal
    }
    return Math.abs(hash) % this.size;
  }

  // Tilføj element
  add(value) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this._hash(value, i);
      this.bitArray[index] = 1;
    }
  }

  // Tjek om element muligvis findes
  mightContain(value) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this._hash(value, i);
      if (this.bitArray[index] === 0) {
        return false; // Bestemt ikke til stede
      }
    }
    return true; // Kan være til stede (mulig falsk positiv)
  }

  // Beregn falsk positiv-rate
  getFalsePositiveRate() {
    const bitsSet = this.bitArray.filter(bit => bit === 1).length;
    const m = this.size;
    const k = this.hashCount;
    const n = bitsSet;
    return Math.pow(1 - Math.exp(-k * n / m), k);
  }
}

// Eksempel på anvendelse
const filter = new BloomFilter(1000, 3);
filter.add('bruger123@email.dk');
filter.add('bruger456@email.dk');

console.log(filter.mightContain('bruger123@email.dk')); // true
console.log(filter.mightContain('bruger999@email.dk')); // false (eller true - falsk positiv)