Реализация универсальной хеш-функции для фильтров Блума в C

Question

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

Answer 1

Не беспокойтесь о коллизии хеш-функций при использовании с фильтрами Блума. вам не нужно обрабатывать столкновения в этом случае. просто у k разные есть функции, которые устанавливают k бит в массиве m бит, когда вы вставляете элемент. во время запроса вы снова используете все k хеш-функций для проверки всех k-битов; если какой-либо из них не установлен, тогда поиск будет ложным. если все они установлены, вы не можете ничего сделать (ложноположительные результаты). Это ясно объяснено в вики:

http://en.wikipedia.org/wiki/Bloom_filter