本文代码思路来源于Guava，对java版用golang进行了重写，对于超精度的get与put进行了优化，与java版本各有优劣，相关数据对比在文末。

布隆过滤器:以牺牲少量正确率为代价，利用较少的空间实现O(1)的hash查询方式。
与bitmap不同点在于，bloomfilter通过多个哈希映射，利用一组bit判断元素是否存在。
而与bitmap存在相同的缺点，即hash会存在冲突，单纯通过开链法无法解决误差问题，为减小误差，bloomfilter采用开放地址法+双重散列的方式。

代码思路：

1. 通过元素量级与期望准确度计算出bit数目
2. 通过元素量级与bit数计算出哈希函数个数
   易得
   fpp(准确度)公式如下，则给定期望准确度与n个数，即可得到m与k
   

bit数目计算：

float64(n) * math.Log(fpp) / (math.Log(2) * math.Log(2))

hashFunction 个数计算:

math.Round(float64(bitslen)/float64(n)*math.Log(2))

取得核心两个数据后，构造结构体即可

type BloomFilter struct {
	bitCount uint64
	data     [][defaultDataLen]uint64
	//data               []uint64
	numOfBits          uint64
	numOfHashFunctions uint64
}

首先尝试data为普通数组，结果在初始化时效率太低，因此改为双层hash模式，批量append的模式。

put

func (b *BloomFilter) put(element []byte) {
	hash64 := murmurHash64A(element)
	hash1 := hash64
	hash2 := hash64 >> 32
	for i := uint64(1); i <= b.numOfHashFunctions; i++ {
		nextHash := hash1 + int64(i)*hash2
		if nextHash < 0 {
			nextHash = ^nextHash
		}
		b.set(uint64(nextHash) % b.numOfBits)
	}
}

其中，得益于论文《Less Hashing, Same Performance: Building a Better Bloom Filter》，可用2个哈希函数来模拟k个哈希函数，即gi(x) = h1(x) + ih2(x) ，其中0<=i<=k-1，所以可以在代码中看到只存在hash1与hash2对numOfHashFunctions进行循环

get

func (b BloomFilter) mightContain(element []byte) bool {
	hash64 := murmurHash64A(element)
	hash1 := hash64
	hash2 := hash64 >> 32
	for i := uint64(1); i <= b.numOfHashFunctions; i++ {
		nextHash := hash1 + int64(i)*hash2
		if nextHash < 0 {
			nextHash = ^nextHash
		}
		if !b.get(uint64(nextHash) % b.numOfBits) {
			return false
		}
		//if getBit(b.data[uint64(nextHash)%b.NumOfBits>>6], uint64(nextHash)%b.NumOfBits%64) != 1 {
		//	return false
		//}
	}
	return true
}

get与put几乎类似，无非是get的时候不进行位运算赋值

com.google.guava与GoBloomFilter性能对比

在相同num数与精确度期望下，两实现对比如下
num=2000000,Probability=0.0000000001时，

guava:

GoBloomFilter:

可以看到，guava在初始化时性能极高(得益于java自身动态申请[len]),但在极端数据量下，guava在精度与get相对比GoBloomFilter就有逊色了

GoBloomFilter

源码地址:https://github.com/260721735/GoBloomFilter
使用教程:

package main

import (
	"github.com/260721735/GoBloomFilter/BloomFilter"
	"log"
)
func main() {
	total := uint64(2000000) //max total
	Probability := 0.0000000001
	bf, err := BloomFilter.Create(total)
	if err != nil {
		log.Println(err.Error())
	}
	bf.Put("BloomFilter")
	log.Println(bf.MightContain("BloomFilter"))
	//create with fpp
	bf, err = BloomFilter.CreateWithFPP(total, Probability)
	if err != nil {
		log.Println(err.Error())
	}
	bf.Put("BloomFilter")
	log.Println(bf.MightContain("BloomFilter"))
}