Bloom Filter

Probabilistisk

En space-efficient probabilistisk datastruktur til at teste om et element er medlem af en mængde.

Kompleksitet

Operation	Tidskompleksitet
Access	`N/A`
Search	`O(k)`
Insertion	`O(k)`
Deletion	`N/A`

Beskrivelse

Et Bloom Filter er en fascinerende probabilistisk datastruktur der tillader hurtige membership tests med minimal hukommelse. Den bruger multiple hash funktioner til at sætte bits i et bit array når elementer tilføjes. Ved lookup hasher man elementet med samme funktioner og checker om alle tilsvarende bits er sat. Bloom filters har en interessant egenskab: false positives er mulige (siger elementet findes når det ikke gør), men false negatives er umulige (hvis den siger nej, er elementet garanteret ikke der). Dette trade-off gør dem perfekte til scenarier hvor hukommelse er begrænset og occasional false positives er acceptable. Bloom filters bruges i databaser til at undgå dyre disk lookups, i netværk til at reducere trafik, og i caching systemer. De kan ikke slette elementer (brug Counting Bloom Filter til det) men er ekstremt space-efficient sammenlignet med hash tables.

Kode Eksempel

// 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; // Convert to 32-bit integer
    }
    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;
    }
  }

  // Check 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; // Definitely not present
      }
    }
    return true; // Might be present (possible false positive)
  }

  // Beregn false positive 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 anvendelse
const filter = new BloomFilter(1000, 3);
filter.add('user123@email.com');
filter.add('user456@email.com');

console.log(filter.mightContain('user123@email.com')); // true
console.log(filter.mightContain('user999@email.com')); // false (eller true - false positive)

Anvendelsesområder

•Database query optimization (undgå disk lookups)
•Web crawler duplicate URL detection
•Spam email filtering
•Bitcoin wallet address checking
•CDN cache checking

Fordele

✓Ekstremt space-efficient (bits vs full data)
✓Konstant tid operationer O(k)
✓Ingen false negatives
✓Hurtigere end disk/network lookups
✓Skalerbar til milliarder af elementer

Ulemper

✗False positives er mulige
✗Kan ikke slette elementer (standard version)
✗Kan ikke liste indhold
✗Precision degraderer med flere elementer
✗Kræver tuning af parametre

Eksempler fra den virkelige verden

•Google Chrome safe browsing (malware URLs)
•Medium.com læste artikler tracking
•Akamai CDN cache existence check
•Cassandra database SSTable filtering
•Bitcoin lightweight clients

Relaterede strukturer

Counting Bloom FilterCuckoo FilterQuotient FilterHyperLogLog