这篇文章将为大家介绍如何使用Go语言自己实现一个简单的bitmap。
一.Bitmap简介
1
2
| bitmap也就是位图.它的作用一般是用来标记对应元素是否存在的.下面我们来举一个简单的例子:
假设我现在在我的系统当中插入了1,3,7,8,11这五个数字.我需要很快速的判断这五个数字存在与否,那么我们可以使用位图来判断.如下图:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| 如上图所示,我们将1,3,7,8,11首先通过hash函数映射可以得到他们的位置:
hash(1) = 1 % 11 = 1
hash(3) = 3 % 11 = 3
hash(7) = 7 % 11 = 7
hash(8) = 8 % 11 = 8
hash(11) = 11 % 11 = 0
于是我们把对应位置标记为1,因此比如下次我们要查看1是否存在,我们使用bitmap(hash(1)) = 1;
可知其是存在的.但是这种方案存在一种弊端就是可能出现误判,比如我们判断12是否存在,那么
bitmap(hash(12)) = 1;会判断12也存在.这种现象叫做假阳性.所以我们需要知道一点就是位图可
以用于判断一个元素不存在(也就是bitmap对应位置为0,那么久必然不存在),但是无法准确判断一个元素
一定存在.假阳性存在的本质是由于hash冲突导致,为了减小假阳性发生的概率,可以考虑设计好的hash函数
和根据对假阳性率要求设定位图大小.这些详细的优化有兴趣的读者请参考:
https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf 本文不做深入解读.
|
二. 动手实现一个简单的Bitmap
在数据库系统当中,当我们对某一列做聚合操作的时候,我们有时候需要快速判断某一行值是否为NULL来做特殊处理，这里就会使用到位图。
1
2
3
4
5
6
7
8
9
10
11
12
13
| type Bitmap struct {
Len int
Any bool
Data []byte
}
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| package bitmap
import "fmt"
func New(n int) *Bitmap {
return &Bitmap{
Len: n,
Any: false,
Data: make([]byte, (n-1)/8+1),
}
}
func (n *Bitmap) IsEmpty() bool {
return !n.Any
}
func (n *Bitmap) Add(row uint64) {
n.Data[row>>3] |= 1 << (row & 0x7)
n.Any = true
}
func (n *Bitmap) Del(row uint64) {
n.Data[row>>3] &= ^(uint8(1) << (row & 0x7))
}
func (n *Bitmap) Contains(row uint64) bool {
return (n.Data[row>>3] & (1 << (row & 0x7))) != 0
}
func (n *Bitmap) Filter(sels []int64) *Bitmap {
m := New(n.Len)
for i, sel := range sels {
if n.Contains(uint64(sel)) {
m.Add(uint64(i))
}
}
return m
}
func (n *Bitmap) Rows() []uint64 {
var rows []uint64
for i, j := uint64(0), uint64(n.Len); i < j; i++ {
if n.Contains(i) {
rows = append(rows, i)
}
}
return rows
}
func (n *Bitmap) String() string {
return fmt.Sprintf("%v", n.Rows())
}
|
1
2
3
| 优化点:
1.Bitmap在实际使用当中利用内存池分配和释放
2.修改Bitmap结构保证删除时更新Any
|