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