javascript - Bloom Filter 哈希返回太多的冲突

Question

我一直在尝试实现我自己的(简单的)Bloom Filter，但一直坚持哈希，我理解多次对项目进行哈希并用索引填充位数组的概念。

但是，我在我的散列中看到了大量的冲突，我正在使用一种散列算法(我已经尝试过 FNV、murmurhash 和现在的 farmhash)和各种种子(基于当前的纳秒)。

我一定是做错了什么，我正在按照 information here 计算 k 函数并设置相同数量的种子。

任何帮助都会很棒，谢谢。

const farmhash = require('farmhash');

class BloomFilter {
	constructor(items, input)
	{
		const BITS_PER_ITEM = 15; //~0.1% false positive rate
		this.m = Buffer.alloc(items.length * BITS_PER_ITEM); // setup bit array
		this.k = Math.ceil(BITS_PER_ITEM * 0.7); // amount of hash functions we need to use
		this.seeds = [];
		this.input = input;
		this.items = items;

		this.setSeeds();
		this.insertItems();
	}

	get time()
	{
		let hrTime = process.hrtime()
		return hrTime[1];
	}

	setSeeds()
	{
		for(let i = 0; i <= this.k; i++) this.seeds.push(this.time);
	}
	
	insertItems()
	{
		console.log('Total buffer size: ' + this.m.length);

		let collisions = 0;
		this.items.forEach(value => {			
			this.getBufferIndices(value).map(index => {
				if(this.m[index] === 1) collisions++;
				this.m[index] = 1;
			});
		});

		console.log('Total collisions: ' + collisions);
	}

	getBufferIndices(value)
	{
		let indicies = [];

		this.seeds.forEach(seed => indicies.push(farmhash.hash32WithSeed(value, seed) % this.m.length));

		return indicies;
	}
}

module.exports = BloomFilter;

Answer 1

根据我对布隆过滤器的内存，当特定值的 所有 k 索引与不同值的索引匹配时，就会发生冲突。

看起来您将一个单个 桶 (this.m[index]) 视为先前已设置为碰撞。

以下(未经测试的)代码应计算实际碰撞次数:

let collisions = 0;

this.items.forEach(value => {           
  let overlap = 0;
  this.getBufferIndices(value).map(index => {
    if(this.m[index] === 1) overlap++;
    this.m[index] = 1;
  });
  if (overlap === this.k) collisions++;
});

正如@Thomas 在他的评论中正确指出的那样，您应该使用 .forEach()，而不是使用 .map()(创建一个新数组):

this.getBufferIndices(value).forEach(index, ...);

并且在getBufferIndices()中，您可以使用.map()代替.forEach():

getBufferIndices(value) {
  return this.seeds.map(seed => (farmhash.hash32WithSeed(value, seed) % this.m.length));
}