如何散列函数的输出映射到布隆过滤器索引？(How to map hashfunction outpu

谁能帮我提供的散列函数的输出是如何映射到布隆过滤器索引大纲？这里是一个概述bloomfilters 。

散列函数输出如何被映射到一个布隆过滤器索引的概略

对于每一个在使用中的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会是在0..23范围相比24..999（因为例如输入2和1002两者结果的2的模量后的值，但是只有25的输入产生的25的输出）。因此，如果你有一个哈希函数生成的32位，你可能需要使用尺寸为：其位数那是二的幂布隆过滤器，然后切片出来的哈希值的部分作为仿佛独立的哈希函数使用 - 您链接维基百科文章中的所有解释。这需要一个质量好的散列函数，虽然，作为哈希函数的任何“集群”缺陷将通过不折不扣的输出通过; 具有位的素数是减轻这种恶劣的散列的一种方式。不过，具有良好的散列函数的两个大国也可以很容易地使用位与运算，并提取位的索引 - 如果需要的话 - 位移，可以比整数模快，虽然散列函数很可能会相形见绌在考虑整体的性能配置。

编辑 - 解决意见...

假设你的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个值ONY一个字节可以有变化的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。

这是很容易使用非加密散列函数，因为他们通常会通过只返回你一个号码，而不是数量的readble文本缓冲区表示，这样就可以避免了这么多废话。