1 简介

布隆过滤器的原理是当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。

检索时，只要看看这些点是不是都是1就大概知道集合中有没有它了;

如果这些点有任何一个0，则被检元素一定不在;
如果都是 1，则被检元素很可能在。

2 实现一个布隆过滤器

布隆过滤器（Bloom Filter）是一种用于检索是否某个元素在集合中的数据结构，它以高效的内存使用来进行集合元素的判断，但允许有一定的误判（假阳性），不会出现漏判（假阴性）。

在Golang中，我们可以使用slice来实现一个简单的布隆过滤器。下面，我们来实现一个10位的布隆过滤器，并举例说明如何使用它。

实现布隆过滤器的步骤：

初始化一个长度为10的位数组，所有值初始化为0。
使用K个哈希函数将元素映射到位数组中的位置，并将对应位置的值设为1。
当检查某个元素是否在集合中时，使用同样的K个哈希函数来计算该元素映射到的位数组中的位置，如果所有位置的值都是1，则认为元素可能在集合中。

示例代码：Golang 实现10位的布隆过滤器

	package main

	import (
	    "fmt"
	    "hash/fnv"
	)

布隆过滤器的结构体

	type BloomFilter struct {
	    bitset []bool // 位数组
	    size   int    // 位数组大小
	}

创建布隆过滤器

	func NewBloomFilter(size int) *BloomFilter {
	    return &BloomFilter{
	        bitset: make([]bool, size), // 初始化位数组
	        size:   size,
	    }
	}

一个简单的哈希函数（使用内置的hash/fnv库）

	func hash(data string, seed uint32) int {
	    h := fnv.New32a()
	    h.Write([]byte(data))
	    return int((h.Sum32() + seed) % uint32(10)) // 返回0-9之间的索引值
	}

向布隆过滤器中添加元素

	func (bf *BloomFilter) Add(data string) {
	    // 使用2个哈希函数示例
	    index1 := hash(data, 0)  // 第一哈希
	    index2 := hash(data, 1)  // 第二哈希
	    
	    bf.bitset[index1] = true
	    bf.bitset[index2] = true
	}

检查元素是否可能存在于布隆过滤器中

	func (bf *BloomFilter) Check(data string) bool {
	    index1 := hash(data, 0)
	    index2 := hash(data, 1)

	    // 检查两个索引位置是否都为1
	    return bf.bitset[index1] && bf.bitset[index2]
	}

创建一个10位的布隆过滤器，然后添加一些元素然后检查元素是否可能存在。 并测试一定不存在的元素。

	func main() {
	    // 
	    bf := NewBloomFilter(10)

	    // 添加一些元素
	    bf.Add("hello")
	    bf.Add("world")
	    bf.Add("golang")

	    // 检查某些元素是否可能存在
	    fmt.Println("Check 'hello':", bf.Check("hello"))   // 可能存在，输出：true
	    fmt.Println("Check 'world':", bf.Check("world"))   // 可能存在，输出：true
	    fmt.Println("Check 'golang':", bf.Check("golang")) // 可能存在，输出：true

	    // 检查不存在的元素
	    fmt.Println("Check 'python':", bf.Check("python")) // 不存在，可能输出：false
	    fmt.Println("Check 'java':", bf.Check("java"))     // 不存在，可能输出：false
	}

布隆过滤器结构体：

bitset: 使用slice来表示位数组（长度为10）。
size: 位数组的大小，固定为10。

哈希函数（hash）：

使用Go的hash/fnv库生成32位的哈希值。
为了模拟不同的哈希函数，使用了不同的seed（即将输入加上一个偏移量）。

添加元素（Add）：

	使用2个哈希函数将元素映射到位数组中的两个位置，并将相应位置的值设为true。

检查元素（Check）：

	使用与添加元素相同的2个哈希函数，检查这两个位置的值是否都为true，如果都为true，则认为该元素可能存在。

示例运行结果：

	Check 'hello': true
	Check 'world': true
	Check 'golang': true
	Check 'python': true
	Check 'java': false

当我们调用bf.Add(“hello”)时，"hello"字符串被两个哈希函数映射到了位数组中的两个位置，并将这两个位置的值设为true。
当我们调用bf.Check(“hello”)时，程序会检查这两个位置是否都为true，如果是，则认为"hello"可能存在。
“python” 和 “java” 没有被添加到布隆过滤器中，所以它们的检查结果预期都应该为false。
但是实际上python为true，这就是布隆过滤器的误报问题。

3 小结

布隆过滤器允许一定的假阳性。

例如，检查一个从未插入的元素可能会返回true，因为哈希函数可能会碰巧将它映射到位数组中所有为true的位置。
但是如果布隆过滤器返回false，可以确定该元素不在集合中。

可以优化的功能点，

	可以增加哈希函数的数量（K值），以提高布隆过滤器的准确性。
增加位数组的长度，可以减少哈希冲突和假阳性的概率。

1.增加和查询元素的时间复杂度为:O(K),(K为哈希函数的个数，一般比较小)，与数据量大小无关
2.哈希函数相互之间没有关系，方便硬件并行运算
3.布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4.在能够承受一定的误判时，布隆过滤器比其他数据结构有很大的空间优势
5.数据量很大时，布隆过滤器可以表示全集，其他数据结构不能表示全集
6.使用同一组散列函数的布隆过滤器可以进行交、并、差运算

但是它的缺点也很明显。

1.有误判率
2.不能获取元素本身
3.一般情况下不能从布隆过滤器中删除元素
4.如果采用计数方式删除，可能会存在计数回绕问题