一 简介
bitmap中文名为位图算法，简单的说 就是通过下标来代替数据的唯一key，然后这个位通过0或1来代表这个数据是否存在。这么说可能还是不是很好理解，下面我举个例子说明:
给定长度是10的bitmap，每一个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。注意下面的数字是下标
把整型数2、6、7存入bitmap，就是把下标为2、6、7的位置的bit位 置为1
此时的bitmap存了哪些元素? 显然是 2、6、7,很容易看出来
此时大家会感觉这个很简单，但是有什么用呢?
如果bitmap代表一个标签，比如爱好、性别之类
下标为用户的id，假如有10个人,用户的id范围是0~9，下面对于男，女，爱好游戏，爱好打球的bitmap
男：
女：
游戏:
打球:
先把上面四个bitmap处理成一个10位的二进制数
男: 1110001100
女: 0001110011
游戏: 0010100110
打球: 1010011000
此时有个需求，需要找到男生并且爱打游戏也爱打球的用户，该怎么求解？
其实大家很明显就能看出来，只需要通过求并集就可以，也就是:
男&游戏&打球
同理假如求 女生中 爱打游戏或者爱打球的就可以:
女&(游戏|打球)
所以利用bitmap特别适合求解这种标签人群的筛选。
可能有些人注意到了，似乎有一种情况，bitmap求解不了，那就是非，例如:求解不爱打游戏的，其实变化一下，也是可以求解的，需要先初始化一个全量的bitmap,也就是每一位都是1的:
全量: 1111111111
求不爱打游戏的，可以用全量和打游戏的做异或即可:
全量^游戏(可能会有人疑问，游戏不是直接能取非吗？要知道全量也不一定每一位都是1的，万一中间有空的，就不完全是1)
至此，简单介绍完了，下一节，讲一下实现。
二 怎么实现bitmap
(1) 先看下原生的bitmap
利用byte数组实现，一个byte占8个比特，算是一个长度为8的bitmap，如果我们需要扩大，就可以利用byte数组，以下是简单实现:
public class BitMap {
//保存数据的
private byte[]bits;
//能够存储多少数据
private int capacity;
public BitMap(int capacity){
this.capacity = capacity;
//1bit能存储8个数据，那么capacity数据需要多少个bit呢，capacity/8+1,右移3位相当于除以8
bits =new byte[(capacity >>3 )+1];
}
public void add(int num){
// num/8得到byte[]的index
int arrayIndex = num >>3;
// num%8得到在byte[index]的位置
int position = num &0x07;
//将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。
bits[arrayIndex] |=1 <
}
public boolean contain(int num){
// num/8得到byte[]的index
int arrayIndex = num >>3;
// num%8得到在byte[index]的位置
int position = num &0x07;
//将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可
return (bits[arrayIndex] & (1 <
}
public void clear(int num){
// num/8得到byte[]的index
int arrayIndex = num >>3;
// num%8得到在byte[index]的位置
int position = num &0x07;
//将1左移position后，那个位置自然就是1，然后对取反，再与当前值做&，即可清除当前的位置了.
bits[arrayIndex] &= ~(1 <
}
public static void main(String[] args) {
BitMap bitmap =new BitMap(100);
bitmap.add(7);
System.out.println("插入7成功");
boolean isexsit =bitmap.contain(7);
System.out.println("7是否存在:"+isexsit);
bitmap.clear(7);
isexsit =bitmap.contain(7);
System.out.println("7是否存在:"+isexsit);
}
(2) java提供的BitSet,使用起来非常简单，实例如下:
public static void main(String[] args) {
BitSet bitSet1 =new BitSet();
bitSet1.set(1);
bitSet1.set(10000);
BitSet bitSet2 =new BitSet();
bitSet2.set(1);
bitSet2.set(5);
System.out.println(bitSet1.get(1));
bitSet1.or(bitSet2);
System.out.println(bitSet1);
}
虽然简单，但是也有着显著的缺点，比如一个极端情况，一个bitmap只有两个位有数据，0和10000000，BitSet会把中间空的地方也初始化10000-1)/64 + 1个数组，这样浪费了很大的空间，其实按中间的这些空数组，完全可以通过offset的概念给压缩掉，能省下很大的空间
(3) redis的bitmap
bitmap是在redis中是大家都忽略的一个操作，说操作是因为 bitmap并不是redis中的一个数据结构，而是在已有的数据结构的扩展，从2.2.0版本就开始支持setbit,getbit,bitcount等几个bitmap相关命令。
关系redis的bitmap也有一个缺陷，跟Java原生的缺点一样，底层也没有做压缩处理，会浪费很大的空间，所以这里就不赘述了。
(4) google的JavaEWAH
个人认为JavaEWAH
算是非常好的bitmap实现了，主要因为JavaEWAH底层进行了压缩处理，所以在bitmap不是完全连续的情况下，占用空间会小，而且提供的api也比较丰富，目前JavaEWAH算是bitmap应用比较广泛的一个方案，以下是简单实例:
public static void main(String[] args) {
int[]arry1={0,1,2};
int[]arry2={0,4,5};
EWAHCompressedBitmap m1 =EWAHCompressedBitmap.bitmapOf(arry1);
EWAHCompressedBitmap m2 =EWAHCompressedBitmap.bitmapOf(arry2);
EWAHCompressedBitmap and =m1.and(m2);
EWAHCompressedBitmap or =m1.or(m2);
int[]andArray=and.toArray();
int[]orArray=or.toArray();
}
可以看出，在集合上的运算，JavaEWAH是非常简单易用的。
三 应用场景
(1) 问题引出
在运营推广的场景，一般会有一些，对于固定客群标签的app消息、短信消息等等的广告推送场景，如果按一般系统的思路，该怎么匹配这些客群呢？如果用户的标签都在一张表里，会简单些，一条sql就查出客群，但是事实上，对于一个优雅的设计，可能不会把所有标签并到一张大宽表，而且每一个标签，或者类似一组标签管理到一张表里，这时候，如果对于跨表的标签该怎么查询呢？大家可能都会想到关联查询呗。但如果N多标签，这时候关联查询几乎是不可能的了，所以这个时候就可以利用bitmap了。
(2) 如何利用?
问题来了，bitmap要有一个数字索引，而且最好是连续的，但是好多用户系统的唯一id是uuid，这个该怎么办呢？
关于这个问题其实我的方案是，给用户生成一个递增的数字流水id，把流水id和用户的唯一id映射维护到一张表里，这个流水id对于其它系统可以是不透明的，只是针对于标签系统使用的，在跑批用户标签的时候，通过用户id去流水id，并跑入相关标签表。
文字描述可能不太清晰，下面我大概表结构说明一下：
比如下面是一个性别的标签表:
流水Id标签
带有流水id的标签表已经有了，下一步就是生成Bitmap了，由于Bitmap本质上是用一个bit位来标记某个元素，所以对于性别这个标签，是延伸出两个Bitmap的，分别是男、女
生成男、女这两个Bitmap也很简单，从数据库查询，然后代码中利用相关Bitmap数据结构即可，这里还是推荐JavaEWAH。
如果一个场景需要算出男性，并且爱好是跑步，并且职业是程序员或者销售的人群，就可以这么算：
男性bitmap & 跑步bitmap &(程序员bitmap | 销售bitmap)
是不是很简单，比传统的一大段sql优雅而且效率高很多？
这时候我估计很多人提问了，单表查出集合构建bitmap不是也需要时间吗？而且也不快。。。
关于这个问题也是我做项目时候遇到的一个问题，后来的解决方案是，提前把标签的bitmap跑批生成到缓存里，这时候需要哪个bitmap时，直接从缓存里拿，速度提升巨大。
这时候还有个问题，这种跑批的Bitmap貌似失去了实时性，拿不到最新的标签？
其实一般的标签系统都不是实时的，也没必要实时，用户标签变动不会频繁，所以也是当天跑批昨天的标签，所以这么做，在业务上也是没有问题的。
作为一个优化，可以把每天的跑批在数据库和缓存里建议都存一份，这样提高数据的可靠性。
(3) 避坑
在生成bitmap时候，如果集合的流水id是乱序的，必须重新升序排序，如果是乱序，JavaEWAH在计算集合的时候会非常慢，这个也是我在实际开发中遇到的问题。
以上是我对于bitmap的介绍和应用场景，以及我在开发中的一些经验，希望对大家有帮助。
