日常工作中我们使用到bitmap的场景并不是很多，前几年在面试中倒是经常会被问到，

比如，一亿用户id的去重、排序、布隆过滤器等等，分析型数据库中bitmap也是利器。

Java中常用的bitmap实现有BitSet，还有开源的、功能强大的Roaringbitmap。

近年比较火的OLAP领域，大量的采用Roaringbitmap作为bitmap的基础实现库。

在读写速度还有内存控制上Roaringbitmap都非常优秀，但是有一个比较大的限制，

就是只支持int类型的数据写入，而实际工作中，我们想要存入Bitmap的是long型。

如果你去搜索bitmap三方库的issue就会发现，有此类需求的人非常多。

众多开源项目在使用Roaringbitmap的时候，也碰到了这问题，有的是扩展实现了对

long型的支持，有的是做了预处理，将数据控制在int类型范围内。

之前在meepo项目中引入bitmap，为了解决在两张表中，查找差异的主键ID，

一般来说一个表的主键ID都是自增的long型(bigint)，所以要扩展long型的支持。

思考

刚才提到bitmap经常被用来存储ID，那么在业务中ID为什么经常被定义为long型呢？

我们平时使用的大多数表数据量可能只有几百或者几千，这些数据也很少更新和增加。

这种数据可以称为常量数据，比如定义浏览器、操作系统、运营商等等，这种场景完全

可以使用int、甚至更短的整数形式，有利于减低索引的开销，还有运行时的内存占用。

还有一种ID是流水号，比如订单ID、用户ID、商品ID等等。考虑业务未来的增长，

有必要把他们定义为long型。当然实际上，绝大多数公司都会在流水号上做一些手脚，

比如在订单流水号的末尾添加用户ID的后四位，用来作为分库分表的依据。

为了防止ID被穷举，设置适当的跳跃和偏移也是必要的。总之，ID涉及到拼接，

就极有可能超过int类型的范围了。

如何实现

如果你真有海量数据需要需要填充到bitmap中，你需要考虑一下内存是不是够用了，

就算支持到long型，内存不够也处理不了。既然一个bitmap可以支持int，那么

我们使用多个bitmap，依次表达 N × int。这样可以使用现有的Roaringbitmap，

作为基础实现。这里有实现代码：【BitMap】。

细节

在处理N × int的时候，很多人会使用整除和取模的方式，当然这样可以实现功能，

但是运行效率一般，参考Ringbuffer在处理Sequence时的技巧，实现如下：

long seq = data >> 31;
int val = (int) (data & Integer.MAX_VALUE);

测试下来，整体运行效率可以提高一倍。

因为这些Roaringbitmap是有序的，使用Treemap当然是最理想的。

但是在搜索性能上，Treemap不及Hashmap，所以只在局部使用。

Roaringbitmap的接口非常多，这里只实现了一部分，后面根据需要再补充。