问如何将hashfunction输出映射到bloomfilter索引？

EN

概述如何将哈希函数输出映射到布隆过滤器索引

对于正在使用的k个散列函数中的每一个，它们都映射到布隆过滤器中的一个位上，就像散列映射到哈希表中的散列桶一样。所以，通常你可能有一个生成32位整数的哈希函数，然后使用模数%运算符来获得位索引0 << i < n，其中n是布隆过滤器中的位数。

具体来说，假设哈希函数生成从0到2^32-1的数字，bloom过滤器中有1000位：

int bit_index = hash_function(input_value) % 1000;

这里需要注意的是，2^32-1大大大于1000。假设哈希函数生成了相当均匀的分布数字，但仅在0和1023之间(包括0和1023之间)，那么在模运算之后，与24..999相比，bit_index在0..23范围内的可能性是24..999的两倍(因为例如，输入2和1002都会导致后模数值为2，但只有输入25才会产生25的输出)。因此，如果你有一个生成32位的散列函数，你可能想要使用一个布隆过滤器，大小为2的幂的位数，然后切出散列值的部分，就像使用独立的散列函数一样-所有这些都在你链接的维基百科文章中解释过。然而，这需要一个高质量的散列函数，因为散列函数中的任何“聚类”缺陷都会被原封不动地传递到输出；拥有质数位是缓解这种糟糕散列的一种方法。尽管如此，有了好的哈希函数，2的幂也使得使用逐位AND操作和位移位(如果需要的话)来提取位索引变得容易，这可以比整数模快，尽管哈希函数在整体性能方面可能会让这种考虑因素相形见绌。

编辑-注解...

假设您的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;

这实际上是一个特别糟糕的想法--对不起--我稍后会解释其中的两个原因。首先，回答您关于它做什么的问题:如果传递的表达式的计算结果为false，则BOOST_STATIC_ASSERT()会给您一个编译错误。在这里，它基本上是一种记录要求，即MD5_DIGEST_LENGTH - MD5散列的文本表示的字符大小-至少与系统用于int整数类型的字节数一样长。(该大小可能是4个字节，但也可能是8个字节。)该要求旨在确保下一行中的reinterpret_cast是安全的。这样做的目的是从MD5散列的文本表示形式开始处的字节中读取值，就好像这些字节包含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 -如果文本恰好从不兼容的地址开始，可能会使您的计算机崩溃。注:英特尔和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。

使用非加密哈希函数要容易得多，因为它们通常只返回一个数字，而不是数字的可读文本缓冲区表示，因此您可以避免所有这些胡说八道的情况。