ブルームフィルタハッシュがあまりにも多くの衝突を返す

Question

私は自分の（単純な）ブルームフィルタを実装しようとしていますが、ハッシングに固執しています。

しかし、私は私のハッシングで1トンの衝突を見ています。（現在のナノ秒に基づいて）1つのハッシュアルゴリズム（私はFNV、murmurhash、そして現在はファームハッシュを試しています）を使用しています。

私は間違ったことをしているに違いありません。私は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]）を以前に衝突としてカウントしたようです。 @Thomasは当然の代わりに（新しい配列を作成します）.map()を使用しての、あなたが.forEach()を使用する必要があり、彼のコメントで指摘するように

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++; 
}); 

：

以下（未テスト）のコードは、実際の衝突を数える必要があります。

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

そしてgetBufferIndices()に、あなたは.map()代わりの.forEach()使用することができます。

を

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