ОТВЕТ от Эта ссылка
Из Википедия :
Фильтры Блума имеют значительное преимущество перед другими структурами данных для представлениянаборы, такие как самобалансирующиеся бинарные деревья поиска, попытки, хеш-таблицы или простые массивы или связанные списки записей.Большинство из них требуют хранения, по крайней мере, самих элементов данных, что может потребовать в любом месте от небольшого числа битов для небольших целых чисел до произвольного числа битов, например для строк (попытки являются исключением, поскольку они могут совместно использовать память междуэлементы с одинаковыми префиксами).Связанные структуры влекут за собой дополнительное линейное пространство для указателей.С другой стороны, для фильтра Блума с ошибкой 1% и оптимальным значением k требуется всего около 9,6 бит на элемент - независимо от размера элементов.Это преимущество отчасти связано с его компактностью, унаследованной от массивов, и частично с его вероятностным характером.Если 1% ложных срабатываний кажется слишком высоким, каждый раз, когда мы добавляем около 4,8 бит на элемент, мы уменьшаем его в десять раз.
Довольно ясно для меня.
Фильтр Блумане хранит сами элементы, это решающий момент.Вы не используете фильтр Блума, чтобы проверить, присутствует ли элемент, вы используете его, чтобы проверить, действительно ли он присутствует , а не , так как он гарантирует отсутствие ложных негативов.Это позволяет вам не выполнять дополнительную работу для элементов, которые не существуют в наборе (например, дисковый ввод-вывод для их поиска).
И все это занимает значительно меньше места, чем что-то вроде хеш-таблицы (что, вероятно,собирается быть частично на диске для больших наборов данных).Хотя вы можете использовать фильтр Блума в сочетании со структурой, подобной хеш-таблице, как только вы убедитесь, что элемент может присутствовать.
Так что пример использования шаблона может быть:
У вас на диске много данных - вы решаете, какую погрешность вы хотите (например, 1%), которая предписывает значение m .Затем определяется оптимальный k (из формулы, приведенной в статье).Вы заполняете свой фильтр из этих привязанных к диску данных один раз.
Теперь у вас есть фильтр в оперативной памяти.Когда вам нужно обработать какой-либо элемент, вы запрашиваете фильтр, чтобы узнать, есть ли у него шанс на существование в вашем наборе данных.Если этого не произойдет, дополнительная работа не выполняется.Нет чтения с диска и т. Д. (Что бы вы сделали, если бы это был хеш или дерево и т. Д.).
В противном случае, если фильтр говорит: «Да, он там», есть вероятность 1%, чтоэто неправильно, поэтому вы делаете необходимую работу, чтобы выяснить это.В 99% случаев это действительно будет , поэтому работа была не напрасной.