MiN*_*EaK 10 c++ database algorithm bloom-filter
任何人都可以通过提供关于哈希函数输出如何映射到布隆过滤器索引的大纲来帮助我吗？这是关于bloomfilters的概述.
关于散列函数输出如何映射到布隆过滤器索引的概述
对于使用中的每个k哈希函数,它们映射到布隆过滤器中的一个位,就像哈希映射到哈希表中的哈希桶一样.因此,很常见的是你可能会说一个哈希函数生成32位整数,然后使用模%运算符得到一个位索引0 << i < n,其中n是布隆过滤器中的位数.
为了使其非常具体,假设哈希函数生成0到2 ^ 32-1之间的数字,并且在bloom过滤器中有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的幂的位数的布隆过滤器,然后切出哈希值的部分以使用,就像独立的哈希函数一样 - 所有在您链接的维基百科文章中都有解释.这需要一个高质量的散列函数,因为散列函数中的任何"聚类"缺陷都将通过未缓冲的输出传递给输出; 具有素数位是减轻这种不良散列的一种方法.尽管如此,使用良好的散列函数,2的幂也可以很容易地使用按位AND运算提取位索引,并且 - 如果需要 - 位移位,这可能比整数模数更快,尽管散列函数可能会使这个问题相形见绌.整体表现形象.
编辑 - 处理评论......
假设您的MD5函数unsigned char*向MD5_DIGEST_LENGTH数据字节返回"p" ,我建议您尝试:
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加上最终数字.
我说这是一个特别糟糕的主意的原因是:
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.
使用非加密哈希函数要容易得多,因为它们通常只返回一个数字而不是数字的可读文本缓冲区表示,因此您可以避免所有这些无意义.