1
P(某位 = 0) = (1 - 1/m)^(kn) ≈ e^(-kn/m)

1
ε ≈ (1 - e^(-kn/m))^k

1
package bloomfilter
2

3
import "hash/fnv"
4

5
// BloomFilter 用 m 位位数组和 k 个哈希函数实现
6
type BloomFilter struct {
7
    bits []uint64   // 位存储，每个 uint64 含 64 位
8
    k    int        // 哈希函数数量
9
    m    uint       // 位数组总大小
10
}
11

12
// New 创建布隆过滤器，m 为位数组大小，k 为哈希函数数量
13
func New(m uint, k int) *BloomFilter {
14
    return &BloomFilter{
15
        bits: make([]uint64, (m+63)/64),
16
        k:    k,
17
        m:    m,
18
    }
19
}
20

21
// Add 将元素加入过滤器
22
func (bf *BloomFilter) Add(data []byte) {
23
    h1, h2 := bf.baseHashes(data)
24
    for i := 0; i < bf.k; i++ {
25
        // Kirsch-Mitzenmacher 双哈希：h_i = h1 + i*h2
26
        pos := (h1 + uint64(i)*h2) % uint64(bf.m)
27
        bf.bits[pos/64] |= 1 << (pos % 64)
28
    }
29
}
30

31
// Test 检查元素是否可能存在
32
func (bf *BloomFilter) Test(data []byte) bool {
33
    h1, h2 := bf.baseHashes(data)
34
    for i := 0; i < bf.k; i++ {
35
        pos := (h1 + uint64(i)*h2) % uint64(bf.m)
36
        if bf.bits[pos/64]&(1<<(pos%64)) == 0 {
37
            return false // 有位为 0，一定不存在
38
        }
39
    }
40
    return true // 所有位为 1，可能存在
41
}
42

43
// baseHashes 用两次 FNV 哈希生成两个独立哈希值
44
func (bf *BloomFilter) baseHashes(data []byte) (uint64, uint64) {
45
    h := fnv.New128a()
46
    h.Write(data)
47
    sum := h.Sum(nil)
48
    return uint64(sum[0])<<56 | uint64(sum[8]), // 取前 8 字节作为 h1
49
           uint64(sum[1])<<56 | uint64(sum[9])  // 取后 8 字节作为 h2
50
}

1
class BloomFilter {
2
  private bits: Uint8Array;  // 位存储，按字节组织
3
  private k: number;         // 哈希函数数量
4

5
  constructor(private m: number, k: number) {
6
    this.bits = new Uint8Array(Math.ceil(m / 8));
7
    this.k = k;
8
  }
9

10
  // 用两个种子做简单哈希，模拟双哈希
11
  private hash(data: string, seed: number): number {
12
    let h = seed;
13
    for (let i = 0; i < data.length; i++) {
14
      // FNV-1a 变体，不同种子产生不同哈希
15
      h = ((h ^ data.charCodeAt(i)) * 0x01000193) >>> 0;
16
    }
17
    return h % this.m;
18
  }
19

20
  add(data: string): void {
21
    for (let i = 0; i < this.k; i++) {
22
      const pos = this.hash(data, i * 0x811c9dc5);
23
      this.bits[pos >> 3] |= 1 << (pos & 7);
24
    }
25
  }
26

27
  test(data: string): boolean {
28
    for (let i = 0; i < this.k; i++) {
29
      const pos = this.hash(data, i * 0x811c9dc5);
30
      if ((this.bits[pos >> 3] & (1 << (pos & 7))) === 0) {
31
        return false;  // 有位为 0，一定不存在
32
      }
33
    }
34
    return true;  // 可能存在
35
  }
36
}
37

38
// 使用示例：10 万位，7 个哈希函数
39
const bf = new BloomFilter(100_000, 7);
40
bf.add("hello");
41
console.log(bf.test("hello")); // true
42
console.log(bf.test("world")); // false（大概率）