共计 3619 个字符，预计需要花费 10 分钟才能阅读完成。
2.1. 概念
为了缩小遍历汇合中的数据来确定查找的数据在不在该汇合中，能够采纳布隆过滤器来优化。布隆过滤器是一个概率数据结构，它无奈给出要找的数据的地位，只能给出要找的数据是否在外面，并且给出的后果可能会假阳性 (false positives)，即通知查找的数据在该汇合外面，理论数据不在外面。
布隆过滤器是由一个很长的 bit 数组和一系列哈希函数组成的。数组的每个元素都只占 1bit 空间，并且每个元素只能为 0 或 1。布隆过滤器领有 K 个哈希函数，当一个元素要退出布隆过滤器时，会应用 K 个哈希函数对其进行 K 次计算，失去 K 个哈希值，并且依据失去的哈希值，在一维数组中把对应下标的值置位 1。
判断某个数是否在布隆过滤器中，就对该元素进行 K 次哈希计算，失去的值在位数组中判断每个元素是否都为 1，如果每个元素都为 1，就阐明这个值可能在布隆过滤器中，须要进一步确认。注：Bloom filter 只能插入与查找，不能删除。
🌰：一个 8 -bit bloom filter，插入 RZA，通过两个 hash 函数找到两个 bit 位，如果该 bit 位是 0，则将其变为 1；如果曾经是 1，则该 bit 位不变。再插入 GZA。
🌰：查找 Raekwon，两个 hash 失去的 bit 位有一个 0，则示意 Raekwon 不存在表中。查找 ODB，两个 hash 到的 bit 为都是 1，则示意 ODB 在表中，但理论不存在(即假阳性)，这其实并不影响，最多到 hash 表中再查一下。
2.2. 误报率
哈希函数越多，那么一个 Key 就能够用数组中的多个地位来标记，整体抵触的概率越低。然而在这个数组中的各个 Bit 位，同时也会被其余数据标记位来影响。如果 Hash 数量给的过多，那么每个 Key 都会有多个 Bit 位来标记它是否存在。极其状况下，过多的 Hash 数量，可能导致整个数组中大量的 bit 位被置为 1。那么在这种状况下，误报率就会越高。
同时，如果在 hash 个数确定的状况下，数组长度越长，数据量越小也越稠密。
假如 Hash 函数以等概率条件抉择并设置 Bit Array 中的某一位，m 是该位数组的大小 (即 m 个 Bit 位)，k 是 Hash 函数的个数，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位为 ”1″ 的概率是：\(1-1/m \)。在所有 k 次 Hash 操作后，该位仍没有被置 ”1″ 的概率是:\((1-1/m)^k \)。如果插入了 n 个元素，那么某一位仍没有被置 ”1″ 的概率是:\((1-1/m)^{kn} \)，因此该位为 ”1″ 的概率是:\(1-(1-1/m)^{kn} \)。当初检测某一元素是否在该汇合中，表明某个元素是否在汇合中所需的 k 个地位都依照如上的办法设置为 ”1″，然而该办法可能会使算法谬误的认为某一本来不在汇合中的元素却被检测为在该汇合中(False Positives)，该概率由以下公式确定：\([1-(1-1/m)^{kn}]^k\approx (1-e^{-kn/m})^k \)。
随着 m(位数组大小)的减少，假阳性的概率会降落，同时随着插入元素个数 n 的减少，假阳性的的概率又会回升。
对于给定的 m 和 n，Hash 函数个数 k 能够由下推出：令 \(a=n/m \)，对 \((1-e^{-kn/m})^k \)求导：
$$
\begin{aligned}y &=\left(1-e^{-a x}\right)^{x} \\\ln y &=x \ln \left(1-e^{-a x}\right)\end{aligned}
$$
$$
\begin{array}{c}\frac{1}{y} y^{\prime}=\ln \left(1-e^{-a x}\right)+x \frac{a e^{-a x}}{1-e^{-a x}} \\y^{\prime}=\left[\ln \left(1-e^{-a x}\right)+x \frac{a e^{-a x}}{1-e^{-a x}}\right]\left(1-e^{-a x}\right)^{x}\end{array}
$$
而 \((1-e^{-ax})^x >0\)，因而：
$$
\begin{array}{l}\ln \left(1-e^{-a x}\right)+x \frac{a e^{-a x}}{1-e^{-a x}}=0 \\\ln \left(1-e^{-a x}\right)=-a x \frac{e^{-a x}}{1-e^{-a x}}\end{array}
$$
令 \(u=1-e^{-ax} \)，可得：
$$
\begin{aligned}\ln u &=\frac{1-u}{u} \ln (1-u) \\u^{u} &=(1-u)^{(1-u)}\end{aligned}
$$
所以，\(u=1/2\)时，找到最低的误报率，此时哈希函数个数 \(k=ln2/a=mln2/n\)。
对于给定的 False Positives 概率 p，最优的位数组大小 m 为：\(m=-nlnp/(ln2)^2\)。
2.3. 实现
在给定汇合中可存的数据的个数 n 与假阳性率 fp 的状况下，返回 m /n，注：\(ln2\approx0.69314718056\)
func BloomBitsPerKey(numEntries int, fp float64) int {
// 传入参数 numEntries 是 bloom 中存储的数据个数，fp 是 false positive 假阳性率
size := -1 * float64(numEntries) * math.Log(fp) / math.Pow(float64(0.69314718056), 2)
locs := math.Ceil(size / float64(numEntries))
return int(locs)
}
设计的布隆过滤器中，应用 []byte 进行存储，并应用最初一个 byte 保留哈希函数个数。而为了节俭内存，一个地位应用一个 bit 位就能够，没必要应用 byte 来示意。所以可将剩下的[]byte 看成一个二维的 bit 数组。🌰：哈希值对 m 取模后失去 12，12/8=1，12%8=4，能够晓得在第 1 行的第 4 列。
为汇合增加布隆过滤器：
func appendFilter(keys []uint32, bitsPerKey int) []byte {
// 将多个 Key 值放入到 bloom 过滤器中
if bitsPerKey < 0 {bitsPerKey = 0}
k := uint32(float64(bitsPerKey) * 0.69) // k = mln2/n
if k < 1 {k = 1}
if k > 30 {k = 30} // 给哈希函数个数设置上上限
nBits := len(keys) * int(bitsPerKey)
if nBits < 64 {nBits = 64} // 确定 m
nBytes := (nBits + 7) / 8 // + 7 是避免 nBits 小于 8
nBits = nBytes * 8
filter := make([]byte, nBytes+1) // 留下 1byte(8bit)记录哈希函数个数
for _, h := range keys {
delta := h>>17 | h<<15 // 繁难 hash 函数
for j := uint32(0); j < k; j++ { // 进行 k 个哈希函数
bitPos := h % uint32(nBits) // 确定列
filter[bitPos/8] |= 1 << (bitPos % 8) // 确定行后设置该位为 1
h += delta // 繁难 hash 函数
}
}
filter[nBytes] = uint8(k) // 留下 1byte(8bit)记录哈希函数个数
return filter
}
func NewFilter(keys []uint32, bitsPerKey int) Filter {return Filter(appendFilter(keys, bitsPerKey))
}
在布隆过滤器中查找元素是否在汇合中：
func (f Filter) MayContain(h uint32) bool {
// 判断一个数据是否在 bloom 过滤器中
// 通过 K 个 Hash 函数计算，判读对应地位是否被标记为 1
if len(f) < 2 { // 因为 1byte 存储哈希函数个数，小于 2 阐明过滤器不存在
return false
}
k := f[len(f)-1] // 获取哈希函数个数
if k > 30 { // 假如超出这个下限，整个过滤器中位数全为 1
return true
}
nBits := uint32(8 * (len(f) - 1)) // 获取过滤器中位数个数 m
delta := h>>17 | h<<15 // 繁难的 hash 函数
for j := uint8(0); j < k; j++ {
bitPos := h % nBits // 查找所在位置
if f[bitPos/8]&(1<<(bitPos%8)) == 0 { // 转换为行和列后，通过 & 比拟是否为 1，return false
}
h += delta // 繁难的 hash 函数
}
return true
}
func (f Filter) MayContainKey(k []byte) bool {return f.MayContain(Hash(k))
}
type Filter []byte
