如何將散列函數輸出映射到bloomfilter索引？

Question

任何人都可以通過提供關於散列函數輸出如何映射到布隆過濾器索引的大綱來幫助我？這裏是bloomfilters的概述。

Answer 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和1023），那麼在模數運算後，它會是bit_index在0..23的兩倍範圍與24..999相比（因爲例如輸入2和1002均導致模數值爲2，但只有25的輸入產生25的輸出）。出於這個原因，如果你有一個生成32位的散列函數，你可能想要使用一個大小爲2的冪數的布隆過濾器，然後將散列值的各部分分開來使用，就好像獨立的散列函數一樣 - 所有解釋你鏈接的維基百科文章。儘管如此，這需要高質量的散列函數，因爲散列函數中的任何「聚類」缺陷都將通過未釋放傳遞到輸出;具有素數位是減輕這種不良散列的一種方法。儘管哈希函數具有良好的散列函數，但通過使用按位「與」運算和如果需要的話，還可以很容易地提取位索引，該位移可以比整數模數更快，儘管哈希函數可能會使這種考慮變得更加乏味整體表現概況。

編輯 - 解決意見...

假設你的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哈希文本表示的字符大小）的要求至少與系統用於整數類型的字節數相同。 （該大小可能是4個字節，但可能是8個）。該要求旨在確保下一行中的reinterpret_cast是安全的。所做的是從MD5哈希文本表示開始處的字節讀取一個值，就好像這些字節包含int一樣。所以，說你的int大小是 4，MD5哈希是「0cc175b9c0f1b6a831c399e269772661」如在你的評論：前4個字節包含「0cc1」。該文本的ASCII碼是十進制的48,99,99,49。當它們被讀入int時，根據CPU的字節順序，數值可能會有所不同，但基本上可以得到其中一個數字乘以256^3加上另一個256^2加上第三個256加上最終數字數。

的原因，我說，這是一個特別糟糕的主意是：

• 在MD5字符串中的每個字符是一個數字（ASCII碼48-57），或從「A」到「f」的一封信（97-102）。這16個值是一個字節可以具有的變化的十六分之一，並且當您生成的int值佔用32位時，您只能得到2^16個不同的值。
• 在某些計算機上，int必須在內存地址的2,4,8等的倍數處對齊。reinterpret_cast - 如果文本恰巧以不兼容的地址開始，可能會導致計算機崩潰。注：英特爾& AMDs沒有這樣的對齊要求，但他們可能更快地操作正確對齊的數據。

所以，另一項建議：

// 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。

使用非加密散列函數會容易得多，因爲它們通常只會返回一個數字而不是數字的可讀文本緩衝表示形式，因此您可以避免所有這些無稽之談。