@polar_winter

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

Зачем нужен фильтр Блума?
В чем премиущества фильтра Блума перед таким решением?
1 Заводим хэш таблицу в медленной памяти.
2 Для каждого возможного значия хэша заводим соответствующий бит в массиве бит в быстрой памяти.
3 1 - есть элемент, 0- нет элемента.
Преимущества этого решения над фильтром Блума:
1 отсутвие неопределенности, но коллизии также остаются
2 более высокая битовая плотность 1 к 1
3 расчет только одной хэш функции
Недостатков я невижу.
Так зачем нужен фильтр Блума?
В чем премиущества фильтра Блума перед таким решением?
  • Вопрос задан
  • 575 просмотров
Решения вопроса 1
bingo347
@bingo347
Crazy on performance...
преимущество в размерах, фильтр Блума может иметь массив бит произвольного размера, предложенное же Вами решение будет иметь массив бит напрямую зависящий от размерности хэша, например для crc32 понадобится 512МБ
Это очень много для структуры, которая не говорит ни о чем кроме наличия
1 отсутвие неопределенности, но коллизии также остаются
раз коллизии остаются, то неопределенность все же есть
2 более высокая битовая плотность 1 к 1
это вообще как относится к решаемой задаче?
3 расчет только одной хэш функции
расчет 10-15 хэшей будет быстрее чем расчет одного + чтение с диска с произвольным доступом. И да, читать битмап придется с диска, ибо столько оперативы под решаемую задачу не даст ни один админ
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы