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

Question

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

Answer 1

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

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