作者：我是一颗菠菜 | 来源：互联网 | 2023-09-17 17:23
1 布隆过滤器原理
布隆过滤器一般用来判断一个数据是否在一个很大的数据集合里面。当然可以用数组&＃xff0c;集合&＃xff0c;树等数据结构和各种查找法都可以做同样的事情&＃xff0c;但是布隆过滤器有更好的时间效率和空间效率。比特币实现SPV节点时使用了布隆过滤器来查询交易。布隆过滤器可以判断一个数在不在集合里&＃xff0c;但存在一定的误判率。
布隆过滤器的核心是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k。
以上图为例&＃xff0c;在这里维数组长度为18&＃xff0c;哈希函数个数为3个。首先将维数组所有位全部置0。集合中有的3个数据x,y,z&＃xff0c;通过3个哈希函数对每一个数据进行计算&＃xff0c;得到该数据的哈希值&＃xff0c;这个哈希值对应维数组上面的一个点&＃xff0c;然后将对应位数组的位置1。这样3个数据会生成9个点。对于另外一个数据w&＃xff0c;查询它 在不在集合中的方法是对w通过3个哈希函数映射到位数组上&＃xff0c;判断3个映射位置是否为1。只要有一个位置为0&＃xff0c;就能说明w一定不在集合中。反之如果3个点都为1&＃xff0c;则说明这个元素可能在集合中。此处不能判断元素一定在集合中&＃xff0c;因为存在一定的误判率。比如对于上图中的4,5,6这3个位置都为1&＃xff0c;但是它是不同的数据映射到的点。如果有一个数据刚好映射到这3个位置&＃xff0c;虽然它不在集合中&＃xff0c;但是我们也会误判它。
添加元素
- 将要添加的元素给k个哈希函数进行计算
- 得到位于位数组上面的k个位置
- 将位数组上对应位置1
查询元素
- 将要查询的元素给k个哈希函数
- 得到对应于位数组上的k个位置
- 如果k个位置有一个为0&＃xff0c;则肯定不在集合中
- 如果k个位置全部为1&＃xff0c;则可能在集合中
2 go语言实现
package main
import (
"github.com/willf/bitset"
"fmt"
)
const DEFAULT_SIZE &＃61; 2<<24
var seeds &＃61; []uint{
7, 11, 13, 31, 37, 61}
type BloomFilter struct {
set *bitset.BitSet
funcs [6]SimpleHash
}
func NewBloomFilter() *BloomFilter {
bf :&＃61; new(BloomFilter)
for i:&＃61;0;i bf.funcs[i] &＃61; SimpleHash{
DEFAULT_SIZE,seeds[i]}
}
bf.set &＃61; bitset.New(DEFAULT_SIZE)
return bf
}
func (bf BloomFilter) add(value string){
for _,f:&＃61;range(bf.funcs){
bf.set.Set(f.hash(value))
}
}
func (bf BloomFilter) contains(value string) bool {
if(value &＃61;&＃61; ""){
return false
}
ret :&＃61; true
for _,f:&＃61;range(bf.funcs){
ret &＃61; ret && bf.set.Test(f.hash(value))
}
return ret
}
type SimpleHash struct{
cap uint
seed uint
}
func (s SimpleHash) hash(value string) uint{
var result uint &＃61; 0
for i:&＃61;0;i result &＃61; result*s.seed&＃43;uint(value[i])
}
return (s.cap-1)&result
}
func main(){
filter :&＃61; NewBloomFilter()
fmt.Println(filter.funcs[1].seed)
str1 :&＃61; "hello,bloom filter!"
filter.add(str1)
str2 :&＃61; "A happy day"
filter.add(str2)
str3 :&＃61; "Greate wall"
filter.add(str3)
fmt.Println(filter.contains(str1))
fmt.Println(filter.contains(str2))
fmt.Println(filter.contains(str3))
fmt.Println(filter.contains("blockchain technology"))
}
这里位数组用了一个第三方的bitset库&＃xff0c;见github&＃xff1a;github.com/willf/bitset
打印结果&＃xff1a;
11
true
true
true
false
京公网安备 11010802041100号