Зачем нужен фильтр Блума?

Question

[polar_winter]

Зачем нужен фильтр Блума?
В чем премиущества фильтра Блума перед таким решением?
1 Заводим хэш таблицу в медленной памяти.
2 Для каждого возможного значия хэша заводим соответствующий бит в массиве бит в быстрой памяти.
3 1 - есть элемент, 0- нет элемента.
Преимущества этого решения над фильтром Блума:
1 отсутвие неопределенности, но коллизии также остаются
2 более высокая битовая плотность 1 к 1
3 расчет только одной хэш функции
Недостатков я невижу.
Так зачем нужен фильтр Блума?
В чем премиущества фильтра Блума перед таким решением?

Answer 1

[Дмитрий Беляев]

преимущество в размерах, фильтр Блума может иметь массив бит произвольного размера, предложенное же Вами решение будет иметь массив бит напрямую зависящий от размерности хэша, например для crc32 понадобится 512МБ
Это очень много для структуры, которая не говорит ни о чем кроме наличия

1 отсутвие неопределенности, но коллизии также остаются

раз коллизии остаются, то неопределенность все же есть

2 более высокая битовая плотность 1 к 1

это вообще как относится к решаемой задаче?

3 расчет только одной хэш функции

расчет 10-15 хэшей будет быстрее чем расчет одного + чтение с диска с произвольным доступом. И да, читать битмап придется с диска, ибо столько оперативы под решаемую задачу не даст ни один админ

Comments

[polar_winter]

Спасибо за ответ.
же Вами решение будет иметь массив бит напрямую зависящий от размерности хэша, например для crc32 понадобится 512МБ
--
кончено имелось ввиде что размер фильра блума и массива бит одинаковый или сопавстовимый. Рамерность хорошего хэша можно ументшить отбрасыванием.