任何人都可以通过提供有关如何将哈希函数输出映射到布隆过滤器索引的大纲来帮助我吗？这是bloomfilters的概述。
问问题
847 次
1 回答
9
关于如何将哈希函数输出映射到布隆过滤器索引的概述
对于使用的每个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 之间（含），那么在模运算之后，bit_index 的可能性会增加一倍与 24..999 相比，在 0..23 范围内（因为例如输入 2 和 1002 都导致后模值 2，但只有输入 25 会产生输出 25）。出于这个原因，如果您有一个生成 32 位的散列函数，您可能希望使用一个布隆过滤器，其大小为 2 的幂的位数，然后切出散列值的部分以像独立散列函数一样使用- 所有在您链接的维基百科文章中都有解释。不过，这需要一个高质量的散列函数，因为任何“聚类” 散列函数中的缺陷将直接传递到输出；具有质数位是减轻这种不良散列的一种方法。尽管如此，对于良好的散列函数，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 散列的文本表示的字符大小——至少与系统用于int整数类型的字节数一样长。（该大小可能是 4 个字节，但也可能是 8 个字节。）该要求旨在确保reinterpret_cast下一行中的 the 是安全的。这样做是从 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 个值只是一个字节可以具有的变化的 16 分之一，虽然
int您生成的值占用 32 位，但您实际上只能得到 2^16 个不同的值。 - 在某些计算机上，
ints 必须与 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。
使用非加密哈希函数要容易得多，因为它们通常只会返回一个数字而不是数字的可读文本缓冲区表示，因此您可以避免所有这些废话。
于 2012-07-27T01:19:29.900 回答