布隆过滤器

概要

Bloom Filter布隆过滤器用法。

如果被判断不是集合的，一定是真；
被判断为集合的，不一定是真；
不能删除数据；

做过一个工程数据记录
bloom filter 加载了60,910 条数据；
序列化成json: 111,856 长度
内存中占用 670,955 bytes

核心比喻：光影剧场 (The Shadow Play)

幕布：存储空间

Bloom Filter 本质是一块巨大的黑色幕布（位数组 Bit Array），初始状态全黑（全为 0）。

投影：写入过程

当“登记”一个字符串时，它经过几盏聚光灯（Hash 函数）的照射，同时在幕布的特定坐标上打下白点（置 1）。

注：幕布不记录字符串本身，只记录它留下的光点坐标。

验票：查询逻辑

要核验一个字符串是否“来过”，我们再次打开聚光灯照射：

如果有落点是黑的：

🛑 绝对不存在。

逻辑：如果是登记过的字符串，那个位置早就该被点亮了。
如果落点全都是亮的：

⚠️ 可能存在（Maybe Exists）。

逻辑：这些白点可能是它自己留下的，也可能是被之前的几个字符串凑巧共同点亮的（误判/Hash碰撞）。

总结

Bloom Filter 是一种 “宁可错信（存在），不可漏判（不存在）” 的空间压缩艺术。它牺牲了微小的准确率（存在假阳性），换取了极致的存储空间。

一点点数学

布隆过滤器的容量应该足够大以容纳你要存储的样本数据。在这种情况下，如果你有600万个比特币地址作为样本数据，你需要考虑以下几点来确定布隆过滤器的容量：

数据量大小： 600万个比特币地址。
错误率： 你需要考虑你可以接受的误判率。通常，误判率越低，需要的内存就越多。在你的应用中，选择一个合理的误判率，通常是根据应用场景和性能要求来决定的。

布隆过滤器的容量应该足够大，以至于填充600万个比特币地址后，误判率仍然可以保持在可接受的范围内。但具体需要多大的容量取决于所选的误判率。你可以使用布隆过滤器的理论公式来估算所需的位数组大小。

具体计算公式如下：

$m = -\frac{n \ln p}{(\ln 2)^2}$

其中：

( m ) 是位数组的大小（容量）。
( n ) 是预期要插入的元素数量，即比特币地址的数量。
( p ) 是所需的误判率。

在这个例子中，( n = 600万 )，( p ) 是你选择的误判率。假设你选择了一个相对较小的误判率，比如0.001（或0.1%），那么你可以将 ( p = 0.001 ) 带入计算公式。

$m = -\frac{6000000 \times \ln(0.001)}{(\ln 2)^2}$

计算出 ( m ) 后，你会得到所需的位数组大小（容量），你可以将其用作布隆过滤器的初始化参数之一。

需要注意的是，这个计算只是一个估算，实际应用中可能需要根据实际情况进行调整。如果内存资源允许，可以选择更大的容量以减小误判率。

工程实践

package main

import (
	"fmt"
	"github.com/bits-and-blooms/bloom/v3"
)

func main() {
	// 创建一个布隆过滤器，设置容量为 1000，错误率为 0.01
	filter := bloom.NewWithEstimates(1000, 0.01)

	// 添加一些元素到布隆过滤器中
	filter.Add([]byte("foo"))
	filter.Add([]byte("bar"))
	filter.Add([]byte("baz"))

	// 检查元素是否存在于布隆过滤器中
	fmt.Println("foo exists:", filter.Test([]byte("foo"))) // 应该返回 true
	fmt.Println("hello exists:", filter.Test([]byte("hello"))) // 应该返回 false
}

引用

[1]github-bloom-fight