布隆过滤器

概要

Bloom Filter布隆过滤器用法。

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

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

一点点数学

布隆过滤器的容量应该足够大以容纳你要存储的样本数据。在这种情况下，如果你有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