Фільтри Блума та ймовірнісні структури даних

Коротко: Фільтр Блума ощадливо перевіряє, чи може елемент перебувати у множині. Він відповідає або «точно ні», або «ймовірно так», але ніколи не каже «ні» помилково.

Докладніше: Фільтр — бітовий масив із кількома геш-функціями. Під час вставлення встановлюються k бітів; під час пошуку мають бути встановлені всі k бітів. Можливі хибнопозитивні спрацювання, хибнонегативні — ні. Видалення неможливе (крім варіантів з лічильниками).