Bloom filter არის სივრცის თვალსაზრისით ეფექტური ალბათური სტრუქტურა, რომელიც პასუხობს სიმრავლის წევრობას ერთი მაქნიშვრით: შეიძლება ჰქონდეს ცრუ დადებითი შედეგი, მაგრამ არასდროს ცრუ უარყოფითი. "რა თქმა უნდა არ არის იქ" დაზუსტებულია; "შესაძლოა იქ არის" საჭიროებს რეალურ შემოწმებას.
როგორ მუშაობს
ბიტის და hash ფუნქციის bit მასივი. ელემენტის , დააყენეთ ბიტი, რომელზეც იგი hash-ის. , შეამოწმეთ ის ბიტი — თუ რომელიმე არის 0, ელემენტი რა თქმა უნდა არ არის.
