关于哈希函数输出如何映射到布隆过滤器索引的概述
对于每个k在使用哈希函数时，它们映射到布隆过滤器中的一个位，就像哈希映射到哈希表中的哈希桶一样。因此，很常见的是，您可能会说生成 32 位整数的哈希函数，然后使用模数%运算符获取位索引0 << i < n where n是布隆过滤器中的位数。
为了使这一点更加具体，假设哈希函数生成从 0 到 2^32-1 的数字，并且布隆过滤器中有 1000 位：
int bit_index = hash_function(input_value) % 1000;
这里需要注意的是，2^32-1 远大于 1000。假设散列函数生成的数字相当均匀分布，但仅在 0 到 1023 之间（包含 0 和 1023），那么在模数运算之后，bit_index 的可能性会增加两倍与 24..999 相比，在 0..23 范围内（因为例如输入 2 和 1002 都会产生后模值 2，但只有输入 25 才会产生输出 25）。因此，如果您有一个生成 32 位的哈希函数，您可能需要使用大小为 2 的幂位数的布隆过滤器，然后切出哈希值的各个部分以像独立哈希函数一样使用- 所有内容都在您链接的维基百科文章中进行了解释。但这需要一个高质量的哈希函数，因为哈希函数中的任何“聚类”缺陷都将毫无保留地传递到输出；拥有素数位数是减轻这种糟糕的散列的一种方法。尽管如此，使用良好的散列函数，二的幂也可以轻松地使用按位与运算提取位索引，并且如果需要的话还可以使用位移位，这可以比整数模更快，尽管散列函数可能会使这种考虑相形见绌。整体性能概况。
编辑 - 处理评论...
假设您的 MD5 函数返回unsigned char* "p" to 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 size is4，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 个不同的值。
- 在某些计算机上，
ints 必须在 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。
使用非加密哈希函数要容易得多，因为它们通常只会返回一个数字，而不是该数字的可读文本缓冲区表示形式，因此您可以避免所有这些废话。
