漫画：Bitmap算法 进阶篇

上一期漫画分享了Bitmap算法的基本概念，小伙伴们的互动十分积极，在此很感谢大家的热情。

没看过上一期漫画的朋友们可以点击下面的链接：

漫画：什么是Bitmap算法？

针对上一期小伙伴们提出的各种问题，这一次咱们来集中解答。

1.解析Word0，得知当前RLW横跨的空Word数量为0，后面有连续3个普通Word。

2.计算出当前RLW后方连续普通Word的最大ID是  64 X  (0 + 3) -1 = 191。

3. 由于 191 < 400003，所以新ID必然在下一个RLW（Word4）之后。

4.解析Word4，得知当前RLW横跨的空Word数量为6247，后面有连续1个普通Word。

5.计算出当前RLW（Word4）后方连续普通Word的最大ID是191 + （6247 + 1）X64  = 400063。

6.由于400003 < 400063，因此新ID 400003的正确位置就在当前RLW（Word4）的后方普通Word，也就是Word5当中。

最终插入结果如下：

官方说明如下：

* Though you can set the bits in any order (e.g., set(100), set(10), set(1),
* you will typically get better performance if you set the bits in increasing order (e.g., set(1), set(10), set(100)).
* 
* Setting a bit that is larger than any of the current set bit
* is a constant time operation. Setting a bit that is smaller than an 
* already set bit can require time proportional to the compressed
* size of the bitmap, as the bitmap may need to be rewritten.

几点说明：

1.为了便于理解，文中介绍的Bitmap优化方法在一定程度上做了简化，源码中的逻辑要复杂得多。比如对于插入数据400003的定位，和实际步骤是有出入的。

2.如果同学们有兴趣，可以亲自去阅读源码，甚至是尝试实现自己的Bitmap算法。虽然要花不少时间，但这确实是一种很好的学习方法。

EWAHCompressedBitmap对应的maven依赖如下：

  com.googlecode.javaewah
  JavaEWAH
  1.1.0

—————END—————

喜欢本文的朋友们，欢迎长按下图关注订阅号梦见，收看更多精彩内容

转载声明：本文转载自公众号【程序员小灰】

原文链接：https://mp.weixin.qq.com/s/743mJir0AGOvilzebTuNkw