大家好，我是蓝胖子，我一直相信编程是一门实践性的技术，其中算法也不例外，初学者可能往往对它可望而不可及，觉得很难，学了又忘，忘其实是由于没有真正搞懂算法的应用场景，所以我准备出一个系列，囊括我们在日常开发中常用的算法，并结合实际的应用场景，真正的感受算法的魅力。
今天，我们就来学习下位图bitmap的原理以及作用。
代码已经上传github
https://github.com/HobbyBear/codelearning/tree/master/bitmap
位图作用
bitmap 是一种高效的且占用内存很小的 判断 某个值 存在与否的数据结构。它用二进制的某一位去表示某个值是否存在。
比如我们需要统计10亿用户是否签到，正常的做法是你可以设计一个10亿长度的map，将用户的uid设置为key，是否签到设计为value，假设uid是int64 类型，占用8个字节，10亿用户就需要大约8G的内存 ,而如果 设计成bitmap去存储，则只需要大约125M 。极大的节约了内存。
原理
因为bitmap中用二进制位代表某个uid是否存在，所以一个字节能够代表8个uid是否存在，如下图所示:
bit位为1代表所在uid的用户已经签到，0则代表未签到。图中，uid为1和5的用户都没有签到，uid为2,3,4,6,7,8的用户都已经签到。
实现
要实现这样一个bitmap，我们可以用一个字节数组来保存所有的bit位，将bit位 设置为1 就是确认某个数字或者说是像例子里的uid，定位uid对应在这个字节数组的哪个位置，将特定位置的字节定位到以后，再定位这个uid在字节中的bit位是在什么位置。
整个过程看代码会更加清晰，如下代码所示，我们在bitmap的构造函数里定义了整个bitmap的最大长度。
type BitMap struct {
f服务器托管网lags []byte
}
func New(max int64) *BitMap {
flagLen := max/8 + 1
return &BitMap{flags: make([]byte, flagLen)}
}
接着看下它的set方法,找到某个数字index再bitmap中的bit位，将其设置为1，一个字节是8位，通过index/8 得到其bit位是在哪个字节上，通过index%8 取余得到设置的bit位 在字节的第几个bit为上，然后通过或运算将特定bit位设置为1。
func (b *BitMap) Set(index int64) {
arrIndex := index / 8
offset := index % 8
// 将offset位置设置为1,或运算,0 | 1 = 1 1|1= 1, 0|0 =0, 1的| 将原值设置为1 ，0的| 不改变原值
b.flags[arrIndex] = b.flags[arrIndex] | (0x1 我还定义了Exits 方法快速判断某个值是否被bitmap记录，同样也是先找到index对应的bit位 在数组中的位置，然后通过与运算去判断特定bit位是0还是1。
func (b *BitMap) Exits(index int64) bool {
arrIndex := index / 8
offset := index % 8
res := b.flags[arrIndex] & (0x1 除此以外，你还可以定义一个remove方法，用于清除特定bit位上的值，
func (b *BitMap) Clean(index int64) {
arrIndex := index / 8
offset := index % 8
// 0 & 1 = 0 ,0 & 0 = 0, 1&1 =1 1的& 不会改变原来的值， 0的& 将原值变为0
b.flags[arrIndex] = b.flags[arrIndex] & ^(0x1 你可以看到bitmap用到的位运算其实本质上是用到下面的性质:
1， 1 与 0或者 1的 & 运算不会改变原值, 0 的& 会将特定bit位设置为0。
2， 0的或运算 不会改变原来的值， 1的或运算是将原来的bit位设置为1。
整个实现并不难，但服务器托管网这种结构的确在大数据量下达到了节约内存进行排重的目的，后续讲到的布隆过滤器也是在这种数据结构上实现的。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
