Как сопоставить вывод хеш-функции с индексами фильтра цветения?

схема того, как выходные данные хеш-функции сопоставляются с индексами фильтра Блума

Каждая из k используемых хеш-функций сопоставляется с битом в фильтре Блума так же, как хэши сопоставляются с сегментами хэшей в хэш-таблице. Таким образом, очень часто вы можете сказать, что хеш-функция генерирует 32-битные целые числа, а затем использовать оператор модуля % для получения битового индекса 0 << i < n, где n — количество битов в вашем фильтре Блума.

Чтобы сделать это очень конкретным, скажем, хеш-функция генерирует числа от 0 до 2 ^ 32-1, а в вашем фильтре Блума 1000 бит:

int bit_index = hash_function(input_value) % 1000;

Здесь важно отметить, что 2^32-1 намного больше, чем 1000. Скажем, вместо этого хэш-функция генерирует довольно равномерно распределенные числа, но только от 0 до 1023 включительно, тогда после операции по модулю вероятность того, что бит_индекс будет в два раза выше быть в диапазоне 0..23 по сравнению с 24..999 (поскольку, например, входные данные 2 и 1002 приводят к значению постмодуля, равному 2, но только ввод 25 дает выход 25). По этой причине, если у вас есть хеш-функция, генерирующая 32 бита, вы можете захотеть использовать фильтр Блума, размер которого равен количеству битов, равному степени двойки, а затем вырезать секции хеш-значения, чтобы использовать их как независимые хеш-функции. - все объяснено в статье в Википедии, на которую вы ссылаетесь. Однако для этого требуется хеш-функция хорошего качества, так как любые недостатки «кластеризации» в хеш-функции будут переданы на выходе без устранения; наличие простого числа битов - один из способов смягчить такое плохое хеширование. Тем не менее, с хорошими хэш-функциями степени двойки также облегчают извлечение битовых индексов с использованием побитовых операций И ​​и, при необходимости, битового сдвига, который может быть быстрее, чем целочисленный модуль, хотя хеш-функции, вероятно, затмят это соображение в общий профиль производительности.

Изменить - обработка комментариев...

Предполагая, что ваша функция MD5 возвращает от unsigned char* "p" до MD5_DIGEST_LENGTH байт данных, я предложил вам попробовать:

BOOST_STATIC_ASSERT(MD5_DIGEST_LENGTH >= sizeof(int));
int bit_index = *reinterpret_cast<unsigned int*>(p) % num_of_bloom_filter_bits;

На самом деле это была особенно плохая идея — извините — я объясню две причины, почему. Во-первых, чтобы ответить на ваш вопрос о том, что он делает: BOOST_STATIC_ASSERT() предназначен для выдачи вам ошибки компиляции, если переданное выражение оценивается как false. Здесь это в основном способ документирования требования, чтобы MD5_DIGEST_LENGTH — размер в символах текстового представления хеша MD5 — был по крайней мере таким же длинным, как количество байтов, которое ваша система использует для целочисленного типа int. (Этот размер, вероятно, составляет 4 байта, но может быть и 8.) Это требование предназначено для обеспечения безопасности reinterpret_cast в следующей строке. Это считывает значение из байтов в начале текстового представления хеша MD5, как если бы эти байты содержали int. Итак, скажем, ваш размер int равен 4, хэш MD5 - "0cc175b9c0f1b6a831c399e269772661", как в вашем комментарии: первые 4 байта содержат "0cc1". Коды ASCII для этого текста: 48, 99, 99, 49 десятичных знаков. Когда они считываются в int, в зависимости от порядка байтов ЦП значение может отличаться, но в основном вы получите одно из этих чисел, умноженное на 256^3, плюс еще одно, умноженное на 256^2, плюс третье, умноженное на 256, плюс последнее. количество.

Причины, по которым я назвал это особенно плохой идеей, следующие:

• каждый символ в строке MD5 является либо цифрой (коды ASCII 48–57), либо буквой от «a» до «f» (97–102). Эти 16 значений являются лишь 16-й частью вариации, которую может иметь байт, и хотя сгенерированное вами значение int занимает 32 бита, вы действительно получаете только 2^16 различных значений.
• на некоторых компьютерах int должны быть выровнены по адресу памяти, кратному 2, 4, 8 и т. д. reinterpret_cast - если текст начинается с несовместимого адреса, это может привести к сбою компьютера. Примечание. У Intel и AMD нет такого требования к выравниванию, хотя для них может быть быстрее работать с правильно выровненными данными.

Итак, еще одно предложение:

// create a buffer of the right size to hold a valid unsigned long in hex representation...
char data[sizeof(unsigned long) * 2 + 1];

// copy as much of the md5 text as will fit into the buffer, NUL terminating it...
sprintf(data, "%.*s", sizeof data - 1, md5);

// convert to an unsigned long...
m = strtoul(data, /*endptr*/ NULL, /*base*/ 16);

Здесь, если бы представление md5 было короче, чем буфер данных, только его начальная часть была бы безопасно скопирована, поэтому BOOST_STATIC_ASSERT не требуется.

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