btcutil/bloom 代码阅读 ​

MurmurHash3 介绍 ​

这里的bloom过滤器用到了一个和平时不一样的hash算法,就是MurmurHash,以下来自Murmur维基百科,

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。 由Austin Appleby在2008年发明， 并出现了多个变种， 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好

特点: 速度快 分布良好

适用于,比如Map的key之类的

MurmurHash3 这里固定生成一个32位整数,

注意他与MD5,SHA3等目标完全不同,不抗攻击,因为结果只有32位,所以是不抗碰撞的.

Filter的工作原理 ​

type Filter struct {
	mtx           sync.Mutex
	msgFilterLoad *wire.MsgFilterLoad
}
type MsgFilterLoad struct {
	Filter    []byte //bloom数据存储位置
	HashFuncs uint32 //进行多少轮hash
	Tweak     uint32 //一个随机数
	Flags     BloomUpdateType
}

添加数据 Add ​

1. 将数据+第i轮+Tweak 使用MurmurHash3做hash值得到一个32位整数,然后取模Fiter的长度, 2 ) 得到数据映射位置
2. 因为一个位置里面有8位,那么映射的那一位就是1<<7&hash值

整体来说只是一个挺巧妙的bloom方法,

校验数据是否存在bloom过滤器中 ​

方法和Add几乎一样,相应的位置是1,就表明有. 同样进行HashFuncs轮校验,每轮得到的位置都是1,表明数据存在.

bloom过滤器 ​

只能起到否定存在的作用,校验结果不存在,那数据一定不在这里. 如果存在,则未必就真存在. 需要再次确认.