Фильтр Блума, очки и девушки

Заметки в тему названия блога. При работе с большими данными люди, некоторые даже не осознавая этого, часто пользуются фильтрами Блума (Bloom Filter). На первый взгляд это очень странная структура данных, которая позволяет очень быстро, не перебирая весь датасет, отвечать на вопрос “есть ли объект x в нашем датасете?” Чем-то сродни словарю (dict) или множеству (set). Но есть нюанс. Один из ответов на вопрос не является точным. Можно сказать, что фильтр Блума - это как очкарики (сам такой, не обижайтесь) или девушки, но наоборот.

Например, если вы спросите девушку “хочешь пойти в кино?”, то ответ “да” - это “да, а ответ “нет” - это “может быть”. Если вы спросите очкарика (без очков) есть ли в помещении какой-то объект, то ответ “да” - это “да” (поскольку этот объект человек видит), а ответ “нет” - еще не означает “нет” (можно и не увидеть небольшой предмет в комнате).

Фильтр Блума действует ровно наоборот: ответ “нет” - это точно “нет”, но ответ “да” означает “может быть”.