布隆過濾器散列返回太多的碰撞

Question

我一直在試圖實現我自己的（簡單）布隆過濾器，但我堅持哈希，我理解多次散列項目和填充位數組與索引的概念。我使用1種散列算法（我嘗試過FNV，murmurhash，現在farmhash）和各種子（基於當前的納秒）。但是，我發現在我的散列中有大量的衝突。

我必須做一些錯誤的，我通過以下的information here和設置種子等量計算k功能。

任何幫助將是偉大的，謝謝。

const farmhash = require('farmhash'); 
 

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

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

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

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

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

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

 
\t getBufferIndices(value) 
 
\t { 
 
\t \t let indicies = []; 
 

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

 
\t \t return indicies; 
 
\t } 
 
} 
 

 
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理所當然地指出了他的意見，而不是使用.map()（這將創建一個新的數組），你應該使用.forEach()：

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

而且在getBufferIndices()，你可以使用.map()代替.forEach()：

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