手写布隆过滤器 第一场第一镜

随着最后一缕春风拂过,空气中弥漫起了夏天的味道,又该滚去学习了。
最近在学习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是否已经被置成1
func (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次hash
func (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
}

好了,就是这样。其实我只是想说,学习任何东西,要从原理抓起,要疯狂地实践。不要拿半路转行的码农不当程序员哦。

最后,分享一个公众号吧,叫做算法梦想家,来跟我一起玩算法,玩音乐,聊聊文学创作,咱们一起天马行空!
图片描述

评论

暂无评论