bloomFilter和哈希函数murmur3

Murmur哈希算法是一种非加密hash算法，适用于哈希查找。

• 优点是时间和空间消耗较少，可检索一个元素是否在集合中
• 缺点是误识别率和删除困难

bloomFilter原理

​ 元素被加入集合时，选择k个哈希函数，对元素进行散列，映射到一个位数组中的k个点，并将其置为1。

​ 查找时，只判断这个元素经过哈希的k个点是否为1，如果等于1，不一定包含该元素，不等于1，一定不包含元素。只会产生两个结果：可能存在或者一定不存在。

BloomFilter实现和使用注意事项

使用时，需要考虑数据量n和误判率fpp

实现时，需要考虑hash函数的选择和bit数组大小，常见的是选取一个hash函数，输入k个参数产生映射点。

murmur3应用-BloomFilter

参数取值

假设BloomFilter中元素总bit数量为m（即bit array大小）,插入的元素个数为n，hash函数的个数为k，误判率为p

如果最小化误判率，则k的取值：
$$k=\frac{m}{n}\ast ln2$$
而p的取值又和m,n有如下关系：
$$m=-\frac{n\ast lnp}{(ln2{)}^2}$$

将m的计算公式带入上式，可得给定n和p，k的取值应为：
$$k=-\frac{lnp}{ln2}$$

应用

murmur3_32的实现

#define ROT32(x, y) ((x << y) | (x >> (32 - y)))

// c1,c2,n是三个特别的常量，用大量测试数据测出来的
uint32_t murmur3_32(uint8_t *key, uint32_t len, uint32_t seed) {
	const uint32_t c1 = 0xcc9e2d51;
	const uint32_t c2 = 0x1b873593;
    const uint32_t r1 = 15;
    const uint32_t r2 = 13;
	const uint32_t m = 5;
	const uint32_t n = 0xe6546b64;

	uint32_t hash = seed;

	const int nblocks = len / 4;
    printf("nblocks= %d\n", nblocks);
	const uint32_t *blocks = (const uint32_t *) key;
    printf("blocks = %d\n", blocks);
	int i;
	uint32_t k;
	for (i = 0; i < nblocks; i++) {
        printf("i= %d\n", i);
		k = blocks[i];
		k *= c1;
		k = ROT32(k, r1);
		k *= c2;

		hash ^= k;
		hash = ROT32(hash, r2) * m + n;
	}

	const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);
    printf("tail = %d\n", tail);
	uint32_t k1 = 0;

	switch (len & 3) {
	case 3:
		k1 ^= tail[2] << 16;
	case 2:
		k1 ^= tail[1] << 8;
	case 1:
		k1 ^= tail[0];

		k1 *= c1;
		k1 = ROT32(k1, r1);
		k1 *= c2;
		hash ^= k1;
	}

	hash ^= len;
	hash ^= (hash >> 16);
	hash *= 0x85ebca6b;
	hash ^= (hash >> 13);
	hash *= 0xc2b2ae35;
	hash ^= (hash >> 16);

	return hash;
}

参考链接

https://llimllib.github.io/bloomfilter-tutorial/（BloomFilter教程，可加深理解）

http://oserror.com/backend/bloomfilter/（对BloomFilter的原理和优化讲的很详细的一篇技术博客）

https://blog.csdn.net/thinkmo/article/details/26833565