首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

位图(bitmap)原理以及实现

!! 大家好,我是蓝胖子,我一直相信编程是一门实践性的技术,其中算法也不例外,初学者可能往往对它可望而不可及,觉得很难,学了又忘,忘其实是由于没有真正搞懂算法的应用场景,所以我准备出一个系列,囊括我们在日常开发中常用的算法,并结合实际的应用场景,真正的感受算法的魅力。

今天,我们就来学习下位图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是否存在,如下图所示:

image.png

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 {

flags []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 

if res == 0 {

return false

}

return true

}

除此以外,你还可以定义一个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。

整个实现并不难,但这种结构的确在大数据量下达到了节约内存进行排重的目的,后续讲到的布隆过滤器也是在这种数据结构上实现的。

  • 发表于:
  • 原文链接https://page.om.qq.com/page/OIPWkvMMnQMUDecqaErKP-6g0
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券