枯渇したときにブルームフィルタを拡張するには？

Question

私はブルームフィルタアルゴリズムを研究しています。概念はかなり単純ですが、以下はJavaの「ブルームフィルタ構造」の簡単な実装です。
私の質問は、ビットセットがほぼ満杯になったときに容量を拡張する方法です。ビットセットのサイズを変更すると、明らかにハッシュ関数を考慮する必要があり、それらの存在要素を再配置する必要があります。
もう一つの考えは、ブルームフィルタの別のインスタンスを初期化することです。 しかし、これは私の考えだけです、誰もこれらを助けることができますか？ありがとう！

public class BloomFilter { 

    private static final int DEFAULT_SIZE = 2 << 24; 
    private static final int[] seeds = {7, 11, 13, 31, 37, 61}; 

    static class SimpleHash { 
     private int cap; 
     private int seed; 

     public SimpleHash(int cap, int seed) { 
      this.cap = cap; 
      this.seed = seed; 
     } 

     public int hash(String str) { 
      int result = 0; 
      int length = str.length(); 
      for (int i = 0; i < length; i++) { 
       result = seed * result + str.charAt(i); 
      } 
      return (cap - 1) & result; 
     } 
    } 

    private BitSet bitSet; 
    private SimpleHash[] hashes; 

    public BloomFilter() { 
     bitSet = new BitSet(DEFAULT_SIZE); 
     hashes = new SimpleHash[seeds.length]; 
     for (int i = 0; i < seeds.length; i++) { 
      hashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); 
     } 
    } 

    public void add(String str) { 
     for (SimpleHash hash : hashes) { 
      bitSet.set(hash.hash(str), true); 
     } 
    } 

    public boolean mightContains(String str) { 
     if (str == null) { 
      return false; 
     } 
     boolean result = true; 
     for (SimpleHash hash : hashes) { 
      result = result && bitSet.get(hash.hash(str)); 
     } 

     return result; 
    } 
} 

Answer 1

ブルームフィルタは、事前に挿入する要素の数を知っている場合にのみ機能します。通常、偽陽性のエラーPと挿入する要素の数はNです。これらを使用して、ハッシュ関数の数を計算します。Hと容量Mです。

事前に要素の数がわからない場合、唯一の方法は、すべての要素をBloomフィルタ（ファイルなど）に追加するときに外部のどこかに格納することです。追加要素の数が安全なしきい値Nを超えた場合、あなた：

1. は、現在のブルームフィルタのインスタンスを削除
2. 新しいMとHP由来とN*2（またはN*3/2）
3. 読み取りと新しいブルームフィルタのインスタンスを作成しますファイルからのすべての要素を新しいBloomフィルタインスタンスに挿入する