java - 当布隆过滤器空间不足时如何扩展布隆过滤器？

Question

我正在研究布隆过滤器算法。这个概念非常简单，下面是我用 Java 实现的“布隆过滤器结构”的简单实现。
我的问题是当bitset快满时如何扩展容量？如果我更改位集的大小，显然我必须再次考虑哈希函数，并且我必须重新排列这些现有元素。
第二个想法是初始化布隆过滤器的另一个实例。 但这只是我的想法，有人可以帮忙吗？谢谢!

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。

如果您事先不知道元素的数量，那么唯一的方法是将所有元素添加到布隆过滤器时将它们存储在外部某处(例如，在文件中)。当添加的元素数量超过安全阈值N时，您:

1. 删除当前的布隆过滤器实例
2. 使用从 P 和 N*2 派生的新 M 和 H 创建新的布隆过滤器实例(或者N*3/2)
3. 从文件中读取所有元素并将它们插入到新的布隆过滤器实例中