Un Bloom filter est une structure probabiliste efficace en espace qui répond aux questions d'appartenance à un ensemble avec un détail : il peut avoir des faux positifs mais jamais de faux négatifs. « Définitivement absent » est certain ; « possiblement présent » nécessite une vérification réelle.
Un tableau de bits de bits et fonctions de hachage. Pour un élément, définir les bits qu'il hache. Pour , vérifier ces bits — si l'un d'eux est 0, l'élément est définitivement absent.
mkkkbits: [0 0 0 0 0 0 0 0]
add "cat": hash->bits 1,4,6 -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
class BloomFilter:
def __init__(self, m, hashes):
self.bits = [0]*m
self.m, self.hashes = m, hashes # list of hash fns
def add(self, x):
for h in self.hashes:
self.bits[h(x) % self.m] = 1
def __contains__(self, x): # False = certain; True = maybe
return all(self.bits[h(x) % self.m] for h in self.hashes)
| Opération | Temps | Espace |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |
Pas de faux négatifs ; le taux de faux positifs diminue à mesure que m (et k ajusté) augmentent.
Les Bloom filters évitent bon marché des travaux coûteux : les bases de données (p. ex. Cassandra, HBase) les utilisent pour éviter les lectures sur disque pour les clés qui définitivement ne sont pas sur disque.
Ils incarnent un compromis classique des systèmes — accepter un petit taux d'erreur borné en échange d'une énorme réduction en mémoire et E/S.