布隆过滤器
参考文档:
https://github.com/hugh2632/bloomfilter
布隆过滤器介绍
判断目标值是否在一个集合中是比较常见的业务场景。在Go语言中通常使用map来实现给功能。但是当集合比较大时，使用map会消耗大量的内存。 这种情况下可使用BitMap来代替map。BitMap虽然能够在一定情况下减少的内存的消耗，但是BitMap也存在以下局限性：
- 当样本分布极度不均匀的时候，BitMap会造成很大空间上的浪费。 若数据的类型Int64，并且数据分布的跨度比较大，则也无法满足对内存的要求。
- 当元素不是整型的时候，BitMap就不适用了。 BitMap只能保存整形数据，对于字符串类型的数据则不合适使用。
BitMap只能处理整形数据，对于字符串则不能说适用。若能够把字符串映射为整形，就可以使用BitMap来存储字符串的状态了。 hash函数可以将字符串映射为整形数据，但是hash函数映射为整形是存在hash冲突。为了减少hash冲突，可以使用多个hash函数来将一个字符串映射为多个整数，并将映射后的整数存在BitMap中。在查询字符串时，使用同样的hash函数来计算hash值，并使用同样的hash值来查询BitMap，若其中有一个hash值没有命中，则该url不存在。
上述思路就是布隆过滤器的核心思路。布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的，它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率:即布隆过滤器报告某个值存在于BitMap中中，但是实际上该值可能并不在集合中。但是布隆过滤器若报告某个值不在BitMap中，则该值肯定不在集合中。
减少布隆过滤器误识别率的方法
布隆过滤器误识别的原因在于hash冲突，因此减少hash冲突可以降低布隆过滤器误识别率。hash冲突和BitMap数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关。可以采用以下方法降低hash冲突的概率：
- 多个hash，增大随机性，减少hash碰撞的概率。
- 扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率。
BitMap介绍
BitMap可以理解为通过一个bit数组来存储特定数据的一种数据结构。BitMap常用于对大量整形数据做去重和查询。 在这类查找中，我们可以通过map数据结构进行查找。但如果数据量比较大map数据结构将会大量占用内存。 BitMap用一个比特位来映射某个元素的状态，所以这种数据结构是非常节省存储空间的。
BitMap用途
- BitMap用于数据去重 BitMap可用于数据的快速查找，判重。
- BitMap用于快速排序 BitMap由于其本身的有序性和唯一性，可以实现快速排序：将其加入bitmap中，然后再遍历获取出来，从而得到排序的结果。
如何判断数字在bit数组的位置
在后面的代码中，我们使用[]byte来存储bit数据，由于一个byte有8个二进制位。因此：
- 数字/8=数字在字节数组中的位置。
- 数字%8=数字在当前字节中的位置。
例如：数字10，
- 10/8=1，即数字10对应的字节数组的位置为：1
- 10%8=2，即数字10对应的当前字节的位置为：2
设置数据到bit数组
- num/8得到数字在字节数组中的位置 => row
- num%8得到数字在当前字节中的位置 => col
- 将1左移col位，然后和以前的数据做|运算，这样就可以将col位置的bit替换成1了。
从bit数组中清除数据
- num/8得到数字在字节数组中的位置 => row
- num%8得到数字在当前字节中的位置 => col
- 将1左移col位，然后对取反，再与当前值做&，这样就可以将col位置的bit替换成0了。
数字是否在bit数组中
- num/8得到数字在字节数组中的位置 => row
- num%8得到数字在当前字节中的位置 => col
- 将1左移col位，然后和以前的数据做&运算，若该字节的值!=0，则说明该位置是1，则数据在bit数组中，否则数据不在bit数组中。
Go语言位运算
在Go语言中支持以下几种操作位的方式：
- & 按位与：两者全为1结果为1，否则结果为0
- | 按位或：两者有一个为1结果为1，否则结果为0
- ^ 按位异或：两者不同结果为1，否则结果为0
- &^ 按位与非：是"与"和"非"操作符的简写形式
- « 按位左移：
>>按位右移：
左移
将二进制向左移动，右边空出的位用0填补，高位左移溢出则舍弃该高位。 由于每次移位数值会翻倍，所以通常用代替乘2操作。当然这是建立在移位没有溢出的情况。 例如：1«3 相当于1×8=8，3«4 相当于3×16=48
右移
将整数二进制向右移动，左边空出的位用0或者1填补。正数用0填补，负数用1填补。 负数在内存中的二进制最高位为符号位——使用1表示，所以为了保证移位之后符号位的正确性，所以需要在高位补1。 相对于左移来说，右移通常用来代替除2操作。 例如：24»3 相当于24÷8=3
使用&^和位移运算来给某一位置0
这个操作符通常用于清空对应的标志位，例如 a = 0011 1010，如果想清空第二位，则可以这样操作:
a &^ 0000 0010 = 0011 1000
布隆过滤器的Go语言实现
接下来我们给出布隆过滤器的Go语言实现，目前代码已经上传到github中，下载地址
定义
首先给出BitMap结构的定义：
type BitMap struct {
bits []byte
vmax uint
}
创建BitMap结构
func NewBitMap(max_val ...uint) *BitMap {
var max uint = 8192
if len(max_val) > 0 && max_val[0] > 0 {
max = max_val[0]
}
bm := &BitMap{}
bm.vmax = max
sz := (max + 7) / 8
bm.bits = make([]byte, sz, sz)
return bm
}
将数据添加到BitMap
func (bm *BitMap)Set(num uint) {
if num > bm.vmax {
bm.vmax += 1024
if bm.vmax < num {
bm.vmax = num
}
dd := int(num+7)/8 - len(bm.bits)
if dd > 0 {
tmp_arr := make([]byte, dd, dd)
bm.bits = append(bm.bits, tmp_arr...)
}
}
//将1左移num%8后，然后和以前的数据做|，这样就替换成1了
bm.bits[num/8] |= 1 << (num%8)
}
从BitMap中删除数据
func (bm *BitMap)UnSet(num uint) {
if num > bm.vmax {
return
}
//&^:将1左移num%8后，然后进行与非运算，将运算符左边数据相异的位保留，相同位清零
bm.bits[num/8] &^= 1 << (num%8)
}
判断BitMap中是否存在指定的数据
func (bm *BitMap)Check(num uint) bool {
if num > bm.vmax {
return false
}
//&:与运算符，两个都是1，结果为1
return bm.bits[num/8] & (1 << (num%8)) != 0
}