c++ - 如何将哈希函数输出映射到Bloom筛选器索引？

Question

谁能通过提供有关哈希函数输出如何映射到布隆过滤器索引的概述来帮助我？这是bloomfilters的概述。

Answer 1

an outline on how the hash function output is mapped to a bloom filter indices

对于所使用的k个哈希函数中的每一个，它们都映射到Bloom筛选器中的某个位上，就像哈希映射到哈希表中的哈希存储桶上一样。因此，通常，您可能会说一个散列函数生成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的可能性将是原来的两倍。相较于24..999，它在0..23范围内(因为例如输入2和1002都导致模后值2，但只有25的输入产生25的输出)。因此，如果您有一个生成32位的哈希函数，则可能要使用大小为2的幂的Bloom过滤器，然后将哈希值的各个部分切开，就好像独立的哈希函数一样使用-您链接的Wikipedia文章中的所有解释。但是，这需要高质量的哈希函数，因为哈希函数中的任何“聚类”缺陷都将通过未缓解的状态传递到输出中。具有素数位是减轻这种不良哈希的一种方法。尽管如此，凭借良好的哈希函数，使用2的幂也可以轻松地使用按位与运算以及(如果需要)位移位来提取位索引，这可能比整数模数更快，尽管哈希函数可能会使该考虑因素相形见war。整体绩效概况。

编辑-解决评论...

假设您的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安全。这样做是从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个不同的值。

在某些计算机上，

必须将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。

使用非加密哈希函数要容易得多，因为它们通常只会向您返回一个数字，而不是该数字的可读文本缓冲区表示形式，因此您可以避免所有这些废话。