Bitmap原理--Bitmap是什么?

对于有开发语言经验的人来说,可以将Bitmap简单理解为数组,但特别的是:数组内只能存放0、1两种值,例如:[1,0,1,0,1,1,0,0]。
计算机专业术语中,Bit表示信息量单位,同时也指二进制(只有0、1两种值)数据中的“位”。所以,Bitmap也可以简单理解为:Bit类型的数组。

Wikipedia 对Bitmap的解释是:“In computing, a bitmap is a mapping from some domain (for example, a range of integers) to bits.”,翻译来是:“在计算机技术中,Bitmap是把某些域(比如一个整数范围)向位的映射”。“整数范围”比较好理解,比如“0~7” 、“8~100” 等就是2个整数范围,那“整数范围向位的映射”,怎么理解呢?前面说到,Bitmap可以简单理解为bit类型的数组,“整数范围”可以理解为数组的下标。比如存储“0~7”范围内的0 2 3 4 5 6 7这几个数字,用只有0、1值的数组可以这样存储:

“0~7”是该数组的下标,存在的话对位下标位置的值为1,不存在的话值为0,因为0 2 3 4 5 6 7中只缺少1,所以index为1的值是0,其他的值都是1。

在计算机中,8个Bit称为一个“字节”(Byte),1个Byte也可以理解为包含8个Bit的集合。比如“10111111”就是一个包含8个Bit的的Byte,所以上边的数组也可以记为:10111111或者11111101的字节,一般会记做11111101。所以,在Bitmap的具体实现上,可以使用Byte来存储。

下边举个Bitmap的应用案例:一个公司的考勤记录。某员工如果当天到了,考勤状态记为1,没到的话记为0。我们首先给每个员工“发”一个数字类型的ID,假如该公司只有8名员工的话,他们对应的员工ID分别是0、1、2、3、4、5、6、7。如果8位员工全到了,他们员工ID对应下标位置的值全为1,即可记为:11111111,全没到记为:00000000,只有1号员工未到记为:11111101。

公司只有8名员工时只需要1个Byte存储即可,那如果该公司有800名员工怎么办呢?可以使用Byte数组。因为一个Byte能存储8名员工的状态,那么800名员工就需要800/8=100个Byte存储:

Byte数组中的第一个值表示0~7 号员工的状态,第二个值表示8~15号员工的状态,依次类推。对于具体某个员工的状态,比如66号员工的考勤状态,存储位置的计算过程如下:

第一步,找到66所在byte在数组中的位置下标:i = n/8 = 66/8 = 8,第二步,找到66在byte中对应bit的位置下标:j = n%8 = 66%8 = 2。即66号员工的状态,存在Byte数组下标为8的Byte中,具体到Byte值中是下标为2的位置。

如上述例子所述,Bitmap可以使用Byte数组实现,其实也可以使用位数更长的Int(包含32个Bit)、Long(包含64个Bit)类型的数组实现。如果使用Int类型的数组实现的话,因为一个Int包含32个Bit,所以66员工状态的存储位置计算过程是:



第一步,找到66所在int在数组中的位置下标:i = n/32 = 66/32 = 2,第二步,找到66在int中对应bit的位置下标:j = n%32 = 66%32 = 2。即66号员工的状态,存在Int数组下标为2的int值中,具体到int值中是下标为2的位置。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. 问题引入: 比较经典的问题是: 在只能够使用2G的内存中,如何完成以下操作:①:对10亿个不重复的整数进行排...
    一个歌手阅读 1,069评论 0 2
  • BitMap是一种很常用的数据结构,它的思想的和原理是很多算法的基础,当然,并且在索引,数据压缩,海量数据处理等方...
    goldenJetty阅读 1,660评论 0 2
  • 1 .问题引入 在给定的一台4G的PC机器上实现,一个包含40亿个不重复并且没有排过序的无符号的int整数,给...
    等一夏_81f7阅读 2,397评论 0 0
  • 一、问题引入bitMap是位图,其实准确的来说,翻译成基于位的映射,举一个例子,有一个无序有界int数组{1,2,...
    bbe9e62bc5ba阅读 1,654评论 0 0
  • 经常能够看到有些大厂的面试题里有一些这样的题目:一个10G的文件,里面全部是自然数,一行一个,乱序排列,对其排序。...
    菜six岁阅读 1,178评论 0 1