Как отобразить вывод хэш-функции для индексов bloomfilter?

Ответ 1

схема о том, как вывод функции хэш-функции отображается на индексы фильтра цветения

Для каждой из используемых х хэш-функций они отображаются на бит в фильтре цветка, как хэш-карта на хэш-ведрах в хеш-таблице. Таким образом, очень часто вы могли бы сказать, что хеш-функция генерирует 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 integer, (Этот размер, вероятно, 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 не требуется.

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