你无法调整布隆过滤器的大小。以下是可行的做法。

Source: Dev.to

请提供您希望翻译的正文内容（除代码块和 URL 之外的文本），我将按照要求保持原有的 Markdown 格式和技术术语进行简体中文翻译。

什么是 Bloom 过滤器？

Bloom 过滤器是一种 概率数据结构，使用位数组和哈希函数来减轻主数据库的负载。
你可能会想，为什么不直接使用像 Redis 这样的缓存系统。答案归结为 准确性 与 内存效率 之间的权衡：

规划 Bloom 过滤器

在使用 Bloom 过滤器之前，你必须决定：

1. 位数组的大小 (m) – 一旦设定，之后无法更改。
2. 哈希函数的数量 (k) – 同样在创建后固定。

这两个参数都取决于：

• n – 预计要存储的项目数量。
• p – 可接受的误报概率。

选择哈希函数的数量

哈希函数的数量不能太低（导致大量冲突），也不能太高（快速填满数组并且同样导致冲突）。
最佳值由以下公式给出：

[ k = \frac{m}{n},\ln 2 ]

在 Go 中计算最佳参数

package main

import (
	"math"
)

// CalculateOptimalParams returns the optimal bit‑array size (m) and
// number of hash functions (k) for a given item count (n) and false‑positive
// rate (p).
func CalculateOptimalParams(n int, p float64) (uint, uint) {
	// 1. Ideal bit‑array size (m)
	//    m = - (n * ln(p)) / (ln(2))²
	m := -float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)

	// 2. Ideal number of hash functions (k)
	//    k = (m / n) * ln(2)
	k := (m / float64(n)) * math.Log(2)

	return uint(math.Ceil(m)), uint(math.Ceil(k))
}

func main() {
	n := 1000          // Expected number of items
	p := 0.01          // Desired false‑positive rate (1%)
	m, k := CalculateOptimalParams(n, p)

	// Print the recommended parameters
	println("Recommended Bit Array Size (m):", m)
	println("Recommended Hash Functions (k):", k)
}

Bloom 过滤器的核心逻辑

Bloom 过滤器回答的问题是 “这个项目可能存在于集合中吗？”

如果答案是 肯定不，我们可以跳过数据库查询。
如果答案是 可能，则必须在真实数据源中进行验证。

示例场景：用户名可用性

1. 传统方法 – 执行 SQL 查询：

   SELECT 1 FROM users WHERE username = 'ayush' LIMIT 1;

   即使有索引，查询成本大约是 O(log n)。

2. Bloom 过滤器方法 –
   先检查过滤器。
   如果它返回 不，立即接受该用户名。
   如果它返回 可能，则回退到数据库查询。

这可以显著降低数据库负载。

Bloom Filter 的工作原理

Bloom Filter 由两个组件组成：

1. Bit Array – 由 0 和 1 组成的数组（例如 [0,0,0,0,0]）。
2. Hash Functions – 将一个值映射到 Bit Array 中索引的确定性函数。

步骤演示

假设有一个 10 位 的 Bit Array，初始全部为 0。

简单布隆过滤器的 Go 实现

package main

import (
	"fmt"
	"hash/fnv"
)

// BloomFilter holds the bit array and its size.
type BloomFilter struct {
	bitset []bool // 0/1 array
	size   int    // length of the array
}

// NewBloomFilter creates a filter with the given size.
func NewBloomFilter(size int) *BloomFilter {
	return &BloomFilter{
		bitset: make([]bool, size),
		size:   size,
	}
}

// hash1 – first hash function (FNV‑1a).
func (bf *BloomFilter) hash1(s string) int {
	h := fnv.New32a()
	h.Write([]byte(s))
	return int(h.Sum32()) % bf.size
}

// hash2 – second hash function (FNV‑1a with a salt).
func (bf *BloomFilter) hash2(s string) int {
	h := fnv.New32a()
	h.Write([]byte(s + "salt")) // simple salt to get a different hash
	return int(h.Sum32()) % bf.size
}

// Add inserts an item into the filter.
func (bf *BloomFilter) Add(item string) {
	i1 := bf.hash1(item)
	i2 := bf.hash2(item)
	bf.bitset[i1] = true
	bf.bitset[i2] = true
	fmt.Printf("Added: %s (indices %d, %d)\n", item, i1, i2)
}

// Exists checks whether an item *might* be in the set.
func (bf *BloomFilter) Exists(item string) bool {
	i1 := bf.hash1(item)
	i2 := bf.hash2(item)

	// Both bits must be true for a "maybe" answer.
	if bf.bitset[i1] && bf.bitset[i2] {
		return true // maybe
	}
	return false // definitely not
}

func main() {
	filter := NewBloomFilter(100)

	// 1. Add "Ayush"
	filter.Add("Ayush")

	// 2. Query "Ayush"
	fmt.Println("Does Ayush exist?", filter.Exists("Ayush")) // true (maybe)

	// 3. Query "Kumar"
	fmt.Println("Does Kumar exist?", filter.Exists("Kumar")) // false (definitely not)
}

实际应用

要点

• Bloom 过滤器以可控的低误报率换取 巨大的内存节省 和 快速的成员检测。
• 它们是 写入一次（不支持删除）且在创建后 大小固定 的数据结构。
• 使用上文公式正确地确定 m 和 k 的大小，对于实现期望的错误率至关重要。

欢迎将示例 Go 代码移植到自己的项目中，调整哈希函数的数量，或用更强的哈希算法（如 MurmurHash、SipHash）替代简单的 FNV 哈希，以获得更好的分布效果。祝过滤愉快！

实践中的布隆过滤器

• Web 浏览器 – 当 URL 太长或可疑时，Chrome 会将其存入布隆过滤器。

  • 访问时，Chrome 检查该过滤器。
  • 如果过滤器返回 “可能危险”，Chrome 会联系 Google 的服务器进行确认。

• 数据库（Cassandra / PostgreSQL） – 在扫描硬盘块以查找行之前，数据库引擎会检查布隆过滤器。

  • 如果过滤器表明该行不存在，则可以避免昂贵的磁盘 I/O。

可伸缩布隆过滤器

布隆过滤器的大小（数组长度 m 和哈希函数数量 k）通常基于假设的最大项目数 n 和目标误报率 p 来选择。
当实际数据集超出原先假设时，需要对过滤器进行扩容。

可伸缩布隆过滤器 (SBF)

Redis Stack 实现了 堆叠布隆过滤器（也称为 可伸缩布隆过滤器）。
堆叠中每新增的过滤器都更大，并且 精度严格高于 前一个过滤器。

Source: …

堆叠算法工作原理

A. 写入规则 – 添加数据

为什么？ 冻结的过滤器保留其原始的误报保证；只有最新的过滤器处理新插入。

B. 读取规则 – 检查数据

要回答查询 “Ayush 是否存在？”：

1. 检查过滤器 3 – 结果：否（Ayush 不在最新的过滤器中）。
2. 检查过滤器 2 – 结果：否。
3. 检查过滤器 1 – 结果：是（Ayush 是两个月前添加的）。

最终答案是所有检查的逻辑 或：

Result = F3.Exists() || F2.Exists() || F1.Exists()

Naïve Stacking 的问题

• 每增加一个过滤器，就会引入其自身的误报概率。
• 如果每个过滤器的错误率为 1 %，两个过滤器的总体错误率约为 2 %，十个过滤器约为 10 %——这是一种不可接受的增长。

Redis 如何解决该问题

Redis 使每个后续过滤器都 更严格（误报率更低），比前一个过滤器更紧：

由于后面的过滤器精度显著提升，即使堆叠 20 个过滤器，整体误报率仍远低于 1 %。

要点

• 布隆过滤器被广泛用于避免代价高昂的查找。
• 当数据集增长时，可伸缩布隆过滤器（堆叠的、逐渐更严格的过滤器）让你在不重建整个结构的情况下保持低整体错误率。
• Redis 的实现表明，逐步更紧的过滤器是实现实用、低错误率扩展的关键。