如何将散列函数输出映射到bloomfilter索引？

Question

任何人都可以通过提供关于散列函数输出如何映射到布隆过滤器索引的大纲来帮助我？这里是bloomfilters的概述。

Answer 1

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

对于每个在使用中的ķ散列函数的轮廓，它们映射到在布隆过滤器只是作为一个位哈希映射到散列表中的散列桶。因此，非常常见的情况下，您可能会说一个生成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在0..23的两倍范围与24..999相比（因为例如输入2和1002均导致模数值为2，但只有25的输入产生25的输出）。出于这个原因，如果你有一个生成32位的散列函数，你可能想要使用一个大小为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哈希文本表示的字符大小）的要求至少与系统用于整数类型的字节数相同。 （该大小可能是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个值是一个字节可以具有的变化的十六分之一，并且当您生成的int值占用32位时，您只能得到2^16个不同的值。
• 在某些计算机上，int必须在内存地址的2,4,8等的倍数处对齐。reinterpret_cast - 如果文本恰巧以不兼容的地址开始，可能会导致计算机崩溃。注：英特尔& AMDs没有这样的对齐要求，但他们可能更快地操作正确对齐的数据。

所以，另一项建议：

// 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。

使用非加密散列函数会容易得多，因为它们通常只会返回一个数字而不是数字的可读文本缓冲表示形式，因此您可以避免所有这些无稽之谈。