随着最后一缕春风拂过，空气中弥漫起了夏天的味道，又该滚去学习了。最近在学习Redis，发现了一个好玩的东西叫布隆过滤器。可是我的水平又不足以研究源码，那我就自己写一个简单的玩玩。原理请原谅我的班门弄斧。我认为布隆过滤器就是用来判断key是否存在的，基于位图。有一个特点是，如果我说key不存在，那么您可以完全信任我，如果我说key存在，您可能就要掂量一下啦。恩恩，具体说来就是来了一个key，我们对其进行n次不同的hash，生成n个bit的索引，在位图里将这几个bit置成1，再来了另一个key，对其进行相同的hash，看看生成的索引对应的bit是否都为1，都为1即为（可能）存在，反之（一定）不存在。至于为什么会出现这种不准确的情况，可以去google一下，比我讲得清楚多了。开工首先，我们需要一个位图，既然决定纯手写，那就从0开始DIY了。老爷请上码：type BM int64//用切片来充当位图，切片的每个位与二级制位方向正好相反type BitMap struct { BitSlice []BM BitNum uint}//求一个BM的bit数，肯定有更好的计算方法var bmBitNum = uint(unsafe.Sizeof(BM(1)) * 8)//n为需要的bit数func NewBitMap(n int) *BitMap { //计算需要几个元素bit才能够 bitNum := uint(n) / bmBitNum + 1 return &BitMap { BitSlice : make([]BM,bitNum,bitNum), BitNum : uint(n), }}//n为位图的索引func (bm *BitMap) Set (n uint) { if n > bm.BitNum { return } //求出应该是切片的第几个元素 byteIndex := n / bmBitNum //求出是此元素的第几个bit bitIndex := n % bmBitNum //通过位运算将该bit置成1 bm.BitSlice[byteIndex] |= BM(uint(1) << bitIndex)}//同样的思路去找所在bit是否已经被置成1func (bm *BitMap) Get (n uint) bool{ if n > bm.BitNum { return false } byteIndex := n / bmBitNum bitIndex := n % bmBitNum return (bm.BitSlice[byteIndex] & BM(uint(1) << bitIndex)) != 0}OK，就这样我们完成了一个简单的位图。至于以后的各种优化只能等我水平高一些来再续前缘了。有了位图就可以搞布隆过滤器了。老弟来了：//这里的两个切片是用来hash的，mod里最大的质数为101，我准备用3个hash生成3个bit，hash过后生成的最大的bit为101。var cap = []uint{7, 11, 13}var mod = []uint{31, 37, 101}//刚刚手写的位图派上用场了type BloomFilter struct { BitMap *bitMap.BitMap}//n依旧为需要的位数func NewBloomFilter(n int) *BloomFilter { return &BloomFilter { BitMap:bitMap.NewBitMap(n), }}//经过3次hashfunc (bf BloomFilter) Set(value string) { for i := 0; i < len(cap); i++ { bf.BitMap.Set(hash(value,i)) }}//同样规则的三次hash判是否存在func (bf BloomFilter) Exist(value string) bool { for i := 0; i < len(cap); i++ { if !bf.BitMap.Get(hash(value,i)) { return false } } return true}//我自己写的hash算法，浓浓的乡土气息。等我再学习一段时间肯定能搞一个更好的！func hash(s string,index int) uint { bit := uint(1) for i := 0; i < len(s); i++ { bit = (bit * cap[index] + (uint(s[i] - ‘a’) + uint(1))) % mod[index] } return bit}好了，就是这样。其实我只是想说，学习任何东西，要从原理抓起，要疯狂地实践。不要拿半路转行的码农不当程序员哦。最后，分享一个公众号吧，叫做算法梦想家，来跟我一起玩算法，玩音乐，聊聊文学创作，咱们一起天马行空！