from:https://my.oschina.net/mengyuankan/blog/1932425
前言
在开发中，可能会遇到这种情况：需要统计用户的某些信息，如活跃或不活跃，登录或者不登录；又如需要记录用户一年的打卡情况，打卡了是1， 没有打卡是0，如果使用普通的 key/value存储，则要记录365条记录，如果用户量很大，需要的空间也会很大，所以 Redis 提供了 Bitmap 位图这中数据结构，Bitmap 就是通过操作二进制位来进行记录，即为 0 和 1；如果要记录 365 天的打卡情况，使用 Bitmap 表示的形式大概如下：0101000111000111...........................，这样有什么好处呢？当然就是节约内存了，365 天相当于 365 bit，又 1 字节 = 8 bit , 所以相当于使用 46 个字节即可。当然，由于公司业务关系，我还没有遇到这种需求 ^ ^。
Redis 操作 Bitmap
setbit 设置操作
set key offset value : 设置 key 的第 offset 位为value
比如 key = 010101101
现在想把 4 这个位置的值设置为 0 ，即上述红色的位置，可以进行如下操作：
set key 4 0getbit 获取操作
get key offset 获取某个位上的值
如获取上述 5 这个位置上的值，可以进行如下操作：
get key 5bitcount 统计操作
bitcount key [start, end] 统计 key 上位为1的个数
如果想获取 上述 key 中1的个数，可以进行如下操作
bitcount key使用 bitmap 来记录上述事例中一周的打卡记录如下所示：
周一：1，周二：0，周三：0，周四：1，周五：1，周六：0，周天：0 （1 为打卡，0 为不打卡）
统计这周打卡的记录，可以看到只有3天是打卡的状态：
Redis 的 Bitmap 还有其他的操作，可以参考Redis 命令
Bitmap 原理
接下来看下 Bitmap 的原理，下面以 Java 中 int 类型举例；
Java 中 int 类型占用 4 个字节，即 4 byte，又 1 byte = 8 bit，所以 一个 int 数字的表示大概如下，
试想以下，如果有一个很大的 int 数组，如 10000000，数组中每一个数值都要占用 4 个字节，则一共需要占用 10000000 * 4 = 40000000 个字节，即 40000000 / 1024.0 / 1024.0 = 38 M，下面用程序验证下：
final Runtime runTime = Runtime.getRuntime();
public static int[] normalArray(int size)
{
// 获取剩余内存容量
long t1 = runTime.freeMemory();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i;
}
long t2 = runTime.freeMemory();
System.out.println(String.format("共占用内存 %s M", (t1-t2) / 1024.0 / 1024.0));
return arr;
}
public static void main(String[] args) {
int size = 10000000;
normalArray(size);
}结果如下：
共占用内存 38.14698791503906 M
可以看到和上面手动计算的一样。
此时，如果使用 bit 来存放上述 10000000 个元素，只需要 10000000 个 bit 即可， 10000000 / 8.0 / 1024.0 / 1024.0 = 1.19 M 左右，可以看到 bitmap 可以大大的节约内存。
使用 bit 来表示数组 [1, 2, 5] 如下所示，可以看到只用 1 字节即可表示：
接下来看下 Java 是如何表示用 Bitmap 来表示上述的大数组的；
首先定义一个 byte 数组，根据初始容量来分配数组的大小 capacity = ( size >> 3 ) + 1：
public byte[] bitemapArray(int size){
byte[] arr = new byte[(size >> 3) + 1];
return arr;
}byte 数组的容量为什么是 ( size >> 3 ) + 1？ 还是因为 1 个字节 = 8 bit ，比如传入的大小 size = 7 ，则 capacity = ( 7 >> 3) + 1 = 1
之后，向数组中添加值，即把对应的位设置为 1，步骤如下：
1. 首先找到 byte 中的索引 index，计算公式 index = n / 8 = n >> 3
2. 找到 byte[index] 中对应的位置 position ，计算公式 position = n % 8 = n & 0x07 （因为下标从 0 开始）
3. 将 byte[inex] 和 1 << positon 做或（|）运算
代码如下：
public void add(byte[] arr, int val)
{
// num/8得到byte[]的index
int index = val >> 3; // val / 8
// num%8得到在byte[index]的位置
int position = val & 0x07;
arr[index] |= 1 << position;
}如果现在 Bitmap 如下：
之后，将 5 添加到 Bitmap 中，index = 5 / 8 = 0, position = 5 & 0x07 = 5，所以需要将上图中的第 5 位设置为 1：
1 << position 即 1 << 5 如下：
arr[index] |= 1 << position 如下：
可以看到 Bitmap 中的第 5 位已经成功设置为 1 。
判断 Bitmap 中是否包含某个值，如上述的 Bitmap 中是否包含 5 ，也就是 5 对应的位是否为 1 即可，步骤如下：
Bitmap 为：
1. position = 5 & 0x07 = 5
1 << position 即 1 << 5 如下：
2. 使用 byte[index] =& (1 << position)
3. 查看第 2 步的值是否为 1 ，如果为 1 则包含，否则不包含
public boolean contain(byte[] arr, int val){
int index = val >> 3;
int position = val & 0x07;
int a = arr[index] & (1 << position);
return a != 0;
}删除 Bitmap 中的某个值，即把对应位设置为 0 ，如果把上述的 Bitmap 中 5 删除，则步骤如下：
Bitmap 为：
1. position = 5 & 0x07 = 5
~（1 << position）即 ~（1 << 5） 如下：
2. byte[index] =& ~（1 << position）
可以看到 position 位置的值被设置为 0，代码如下：
public void remove(byte[] arr, int val){
int index = val >> 3;
int position = val & 0x07;
arr[index] &= ~(1 << position);
}现在使用 Bitmap 来测试以下刚开始的那个大数组例子，看下占用的内存是多大：
首先看下 bitemapArray 方法：
public byte[] bitemapArray(int size){
long t1 = runTime.freeMemory();
byte[] arr = new byte[(size >> 3) + 1];
for (int i = 1; i <= size; i++) {
add(arr, i);
}
long t2 = runTime.freeMemory();
System.out.println(String.format("共占用内存 %s M", (t1-t2) / 1024.0 / 1024.0));
return arr;
}
public static void main(String[] args) {
int size = 10000000;
byte[] ret = test.bitemapArray(size);
boolean isContain = test.contain(ret, 5555);
System.out.println(isContain); // true
test.remove(ret, 5555);
boolean isContain2 = test.contain(ret, 5555);
System.out.println(isContain2); // false
boolean isContain3 = test.contain(ret, 9999999);
System.out.println(isContain3); // true
}结果：共占用内存 1.1921157836914062 M
可以看到 10000000 个数字只用 1.2 M的内存，和上面手动计算的一致，此外，还测试了 remove 方法和 contain 方法，都是可以工作的。
以上就是 Bitmap 的一个实现原理