Ένα Bloom filter είναι μια δομή δεδομένων πιθανοθεωρητική που εξοικονομεί χώρο και απαντά σε ερωτήματα συμμετοχής συνόλου με μια στροφή: μπορεί να έχει ψευδώς θετικά αλλά ποτέ ψευδώς αρνητικά. "Σίγουρα δεν υπάρχει" είναι σίγουρο· "πιθανώς υπάρχει" χρειάζεται έναν πραγματικό έλεγχο.
Πώς λειτουργεί
Ένας πίνακας bit από bits και συναρτήσεις κατακερματισμού. Για να ένα στοιχείο, ορίστε τα bits στα οποία κατακερματίζεται. Για να , ελέγξτε εκείνα τα bits — εάν κάποιο είναι 0, το στοιχείο είναι σίγουρα απών.
