漫画算法：Bitmap算法（进阶篇）
之前分享了Bitmap算法的基本概念，小伙伴们的互动十分积极，在此很感谢大家的热情。
没看过上一期漫画的朋友们可以点击：《漫画：什么是Bitmap算法？》
针对上一期小伙伴们提出的各种问题，这一次咱们来集中解答。
image
image
image
image
我们以上一期的用户数据为例，用户基本信息如下。按照年龄标签，可以划分成90后、00后两个Bitmap：
image
用更加形象的表示，90后用户的Bitmap如下：
image
这时候可以直接求得非90后的用户吗？直接进行非运算？
image
显然，非90后用户实际上只有1个，而不是图中得到的8个结果，所以不能直接进行非运算。
image
image
同样是刚才的例子，我们给定90后用户的Bitmap，再给定一个全量用户的Bitmap。最终要求出的是存在于全量用户，但又不存在于90后用户的部分。
image
如何求出呢？我们可以使用异或操作，即相同位为1，不同位为0。
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
25769803776L = 11000000000000000000000000000000000B
8589947086L = 1000000000000000000011000011001110B
image
image
image
image
image
image
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当中。
最终插入结果如下：
image
image
image
image
image
官方说明如下：
<pre style="margin: 0px; padding: 0px; max-width: 100%; box-sizing: border-box !important; word-wrap: break-word !important; color: rgb(62, 62, 62); font-size: 12pt; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial; font-family: 宋体; background-color: rgb(255, 255, 255);">* 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. </pre>
image
几点说明：
1.为了便于理解，文中介绍的Bitmap优化方法在一定程度上做了简化，源码中的逻辑要复杂得多。比如对于插入数据400003的定位，和实际步骤是有出入的。
2.如果同学们有兴趣，可以亲自去阅读源码，甚至是尝试实现自己的Bitmap算法。虽然要花不少时间，但这确实是一种很好的学习方法。EWAHCompressedBitmap对应的maven依赖如下：
<dependency>
<groupId>com.googlecode.javaewah</groupId>
<artifactId>JavaEWAH</artifactId>
<version>1.1.0</version>
</dependency>
