Bitmap是什么?
Bitmap是一种内存高效的、存储布尔值信息的数据结构。在Bitmap中,每个位(Bit)都被视为一个独立的开关,可以表示0或1。
由英文即可看出,Bitmap 是一个合成词,由 Bit 和 Map 组合而成 (Bitmap = Bit + Map),用于将一系列表示有/无(是/否)状态的二值组织起来的一种数据结构(Bit,表示计算机科学中的最小单位 (即: 0 或 1),在逻辑上可以表示为 “是/否” 或 “有/无”;Map,表示一种组织事物的特定方式。)
在《编程珠玑》中,对Bitmap的定义为:所谓的Bitmap就是用一个bit位来标记某个元素对应的VALUE,而KEY即是该元素。由于采用了Bit为单位来存储数据,因此可以大大节省存储空间。
一句话:Bitmap本质可以理解成bit数组,其中每一个bit用来表示某个元素的VALUE值,这个值,要么是0,要么是1。
使用场景
(1). 海量连续数字的排序、去重。
(2). 用于需要保存海量的是/否信息的场景,或者可以转换为保存是/否信息的场景。
如:用户是否点赞,用户是否签到,用户是否登录,日活用户,访问计数,在线用户数等等。
1. 判断用户登录:需要一个KEY(这个场景下KEY可以随意设计),VALUE是一个用户ID所对应的位上、由0/1表示的位数组。每个用户ID对应一个位,当用户登录时,将用户ID对应的位设为1,退出登录时将其对应的位设为0。
2. 判断用户打卡:用日期作为KEY,VALUE是一个在当前日期下用户ID所对应的位上、由0/1表示的位数组。如果在当前日期下,用户已打开,则将用户ID对应的位置为1,未打卡的用户ID所对应的位的值不变(初始化时所有的位都置为0)。
3. 判断用户是否领取优惠券:优惠券的唯一标识作为KEY,VALUE是一个用户ID所对应的位上、由0/1表示的位数组。如果用户已领取,则将用户ID对应的位置为1,未领取的用户ID所对应的位的值不变(初始化时所有的位都置为0)。
优缺点
Bitmap在数据稠密的时候,非常节省空间,但是在数据稀疏的时候,会有极大的浪费。
如:我们知道一个int型的整型数字,存储在内存中是占4个字节,一个字节是8bit,假设存储一个数字10,用一个int型数组 int[1] 表示的话,就是 148=32 bit,在内存中占 32个bit位。如果是使用 Bitmap存呢?32个bit 可以存 32个数字,每一个bit位可以代表一个数字(即可以存储从0到31,共32个数字),这就是Bitmap在存储空间上的优势。
同理,如果Bitmap就只是存一个很大的数字10000, 那么怎么用Bitmap表示呢?那就在第10000个bit位上设置1,其它的bit位还是默认的0,那么Bitmap此时是占了10000bit的,而10000这个数字用一个int类型的数组存的话,内存中还是只占32bit,所以,在存储数据稀疏时,会有极大的浪费。
如何使用Bitmap排序?
如何使用Bitmap对(4,7,2,5,3)这五个元素进行排序?
(1). 因为是0-7之间的这8个数,所以我们只需要8个Bit的数组即可(1字节<1Byte>);
(2). 首先我们开辟1字节的空间,将这个位数组的所有Bit位都设为0;
(3). 遍历这5个元素。第一个元素是4,那么就把4对应的位设为1,因为索引是从零开始的,所以要把第五位设为1;第二个元素7,将第八位设为1;然后依次处理其他元素,将相应的位设为1;
(4). 以上处理完以后,我们再遍历这个Bit数据,将值为1的、数组的索引输出:即为(2,3,4,5,7),这样就达到了排序的目的。