一、结构思想
以 bit 作为存储单位进行 0、1存取的数据结构。 可用作布尔值存取,比如给定第i位,该bit为1则表示true,为0则表示false。
二、使用场景及优点
适用于对布尔或0、1值进行(大量)存取的场景。
如:记录一个用户365天的签到记录,签了为true,没签为false。若是以普通key/value数据结构,每个用户都需要记录365条,当用户量很大时会造成巨大的空间开销。 因此运用位图的话,每天签到记录只占1个位(bit),一共就365位,则只需48个字节就能容纳一个用户一年的签到记录。
优点: 低空间开销且高效的0、1存取方案
三、具体实现
实现源码:https://github.com/SimpleIto/data_structure/blob/master/src/bitmap/Bitmap.java
主要考虑以下问题:
- 用什么物理结构存储一系列bit?
- 如何通过位操作高效的实现对指定bit的获取、修改操作?(而不是通过字符串转去转来臃肿的实现)
解决思路:
Java中,使用 byte[] 字节数组来存储bit。 1 byte = 8 bit
对于获取操作 思路:拿到目标bit所在的byte后,将其向右位移(并将高位置0),使目标bit在第一位,这样结果值就是目标bit值。
通过 byte[index >> 3] (等价于byte[index/8])取到目标bit所在的byte。
令 i = index&7(等价于index%8)得到目标bit在该byte中所在的位置。
为了将目标bit前面的高位置0(这样位移后的值才等于目标bit本身):需要构建到目标bit为止的低位掩码,即 0b11111111 >>>(7 - i),再与原byte做&运算。
最后将结果向右位移 i 位,使目标bit处在第一位,结果值即为所求。
对于修改操作 思路:根据设定值true或false的不同,分为两种操作逻辑
如果value为true,则目标位应与1做“或”运算。需构建“目标位为1,其他为0”的操作数(因为实际操作的是byte,为了只修改目标bit,而不影响其他位)
如果value为false,则目标位应与0做“与”运算。则需构建“目标位为0,其他为1”的操作数。
构建目标位为1其他位为0的操作数:1 << (index & 7)