0%

《数据结构与算法》Bitmap算法与布隆过滤器

之所以把Bitmap算法和布隆过滤器放到同一篇文章,是因为他两有一个共同的特点,就是对空间的利用达到了极致

试想这样一个场景:

给一台普通PC,2G内存,要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数,给出一个整数,问如果快速地判断这个整数是否在文件40亿个数据当中?

40亿个int整型,golang中int就是int32占用4字节,也就是如果40亿全部加载到内存需要 4000000000*4/1024/1024/1024=14.9G 的空间,2G内存的PC完全装不下,那怎么办

首先看问题,问题是判断是否存在,那么就想到每个int数字能不能使用一个bit表明它是否存在,那么就需要下面两个条件:

  1. 每个元素(示例中是int值)有一个独享的空间(值为n对应第n个bit,这样每个int值对应一个bit各不冲突就是Bitmap算法,每个int多个bit相互重复利用就是布隆过滤器)
  2. 找到一个int到这个空间的映射方法(Bitmap算法中是 a/32取整定位到bit数组下标,a%32定位到数组中哪个位置。布隆过滤器是多个hash函数计算出多个bit位置)

Bitmap算法

前面说了Bitmap算法满足第一个条件的做法是:值为n对应第n个bit,这样每个int值对应一个bit各不冲突

那么如果这些值中的最大值大于了bit的个数,那就表示不下了,所以最终bitmap的bit个数实际上是最大值(上面例子中int最大值是4294967295,那么最多需要4294967295个bit,也就是 4294967295/8/1024/1024 = 511MB),bit个数其实是跟随最大值的,最大值越大,用的bit就越多,占用空间就越多

但是最大值当然没有办法知道,这就要求bitmap应该在插入的时候做到自动扩容

废话不多说,看源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package main

import "fmt"

var bitmap = make([]int32, 100) // 先创建一个3200个bit的map

func add(n int32) {
bitmapIndex := n/32 // 找到落在bitmap的数组的哪个位置
for bitmapIndex > int32(len(bitmap) - 1) { // 自动扩容
bitmap = append(bitmap, 0)
}
bitmapBitIndex := n%32 // 找到落在int32的哪个bit
bitmap[bitmapIndex] |= 1 << bitmapBitIndex // 对应位置置为1
}

func has(n int32) bool {
bitmapIndex := n/32
bitmapBitIndex := n%32
return bitmap[bitmapIndex] & (1 << bitmapBitIndex) != 0
}

func main() {
samples := []int32{12, 456, 2462, 5754, 5673, 231, 1, 748, 67, 0} // 40亿个样本

for _, a := range samples {
add(a)
}
fmt.Println(has(748)) // true
fmt.Println(has(749)) // false
fmt.Printf("bit个数:%d\n", len(bitmap) * 32) // bit个数:5760
}

我只写了添加和判断是否存在两个方法,删除方法你可以尝试写一下

布隆过滤器

布隆过滤器的作用基本上就是快速的检查某个元素是否在集合中,但存在一定的误识率(误识率的大小取决于设计的hash算法是否足够均匀)

误识率: 给定一个值,通过布隆过滤器,如果不存在,那不存在的结果是100%确定的,但是如果存在,却不能100%确定确实存在

误识率的原因其实就是多个数值占用的bit位重叠造成的,而Bitmap算法不重叠,就没有误识率

布隆过滤器的原理就是当一个元素被加入到集合的时候,用 K 个 Hash 函数将元素映射到一个位图中的 K 个点,并且把这个点的值设置为 1,在每次检索的时候我们看一下这个点是不是都是 1 ,都是则认为存在集合里(有误判可能),有一个不是1,则一定不存在集合里。

这样说可能比较抽象,举个例子:

我们假设 K 是 2,有 Hash1 和 Hash2 两个哈希函数

Hash1 = n%3
Hash2 = n%8
然后我们创建一个名叫 bitMap 长度是 20 的位图(其实按照上面两个hash算法,只需要8个bit位,虽然占用空间小,但是数据一多,误识率将变得非常高)

bitMap=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
这个时候,我们要将 7,存入到这个集合中

n = 7
分别用 Hash1 和 Hash2 计算 n 哈希后的值

Hash1 -> 1
Hash2 -> 7
我们把 bitMap 对应的值置为 1,从 0 开始

bitMap=[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
这样下次我们来查找 7 在不在这个集合的时候就可以用 Hash1 和 Hash2 计算完以后在 bitMap 集合中查找对应位置是否都是 1,如果都是 1 则大概率在集合中。

如果再在集合中插入 13 分别用 Hash1 和 Hash2 计算 n 哈希后的值

n = 13
Hash1 -> 1
Hash2 -> 5
我们把 bitMap 对应的值置为 1,从 0 开始

bitMap=[0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
这个时候我们发现 1 被映射到了两次,但是并不影响我们在集合[7, 13]中快速找到 7 或者 13。

但是当插入的数据量大幅提升的时候,甚至 bitMap 全部被置为 1 的时候问题就很严重了,误识率就非常高了,这个也是根据不同场景实现布隆过滤器所要考虑的问题。

尽管有这样的问题,但是仍然不能掩盖布隆过滤器的空间利用率和查询时间远超其他算法,插入数据和查询数据的时间复杂度都是 O(k)

布隆过滤器不能删除元素,因为多个元素占用的bit重叠,删除一个元素就是把它占用的bit都置为0,这样做势必影响其他元素

废话一堆,看源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import "fmt"

var bitmap = make([]int32, 1) // 先创建一个布隆过滤器

func hash1(n int) int {
return n % 3
}

func hash2(n int) int {
return n % 8
}

func add(n int) {
hash1Result := hash1(n)
hash2Result := hash2(n)
bitmap[hash1Result/32] |= 1 << hash1Result%32
bitmap[hash2Result/32] |= 1 << hash2Result%32
}

func has(n int) bool {
hash1Result := hash1(n)
hash2Result := hash2(n)
return bitmap[hash1Result/32] & (1 << hash1Result%32) != 0 && bitmap[hash2Result/32] & (1 << hash2Result%32) != 0
}

func main() {
samples := []int{12, 456, 2462, 5754, 5673, 231, 1, 748, 67, 0}

for _, a := range samples {
add(a)
}
fmt.Println(has(748)) // true
fmt.Println(has(749)) // false
}

Bitmap算法与布隆过滤器的比较

不同点:

  1. 布隆过滤器不能删除元素,Bitmap算法可以
  2. 一般情况下布隆过滤器更节省内存,但是具有误识率,而Bitmap算法相反
  3. Bitmap算法占用的空间取决于最大值,而布隆过滤器占用的空间固定,其误识率取决于hash算法以及元素的个数

相同点:

  1. 他们都是为了判断一个值是否存在或不存在,没有其他功能
  2. 他们都是通过削减功能实现内存的极致缩减



微信关注我,及时接收最新技术文章