bitmap算法

所谓bitmap算法就是，用一个bit来标记，当前元素是否或者存在这个标签。是标签和另外一个维度的映射关系。比如1亿个人，5千万是程序员。那就是标签程序员和整个10亿人的一个映射 f(x)=(flag==programmer?1,0) x<- 0 untl 1亿。所以本质，还是一个signal函数的变形。
算法是signal函数，数据结构是bit 。
好处是 效率高
占用内存少，比如N=10000000;只需占用内存为N/8 = 1250000Bytes = 1.2M，如果采用int数组存储，则需要38M多
所以一般以大的集合作为定义域。然后标签是值域。只是保存存在或者不存在。
也有可能，多个标签，代表一个维度。比如80后，90后，00后，年龄的一个维度。

image.png

这里转化后是9个位图。
但是现实生活中，比如电商行业，买家各种标签，成千上万。每一个都用全量位图来的话，假如用户10个亿。也需要32M的内存，再乘以1万个标签，320G内存。而且32M内存里面，有些标签只是个别人，比如说特殊人群，浪费空间。崩盘了

所以要引入一种新的bitmap算法，EWAHCompressedBitMap .
通过引入特殊字，直接存储数据的叫Literal word，还有另外一个存储跨度信息的叫Runnng-length-word
。 先后插入1，4，64，129
第一个word存1和4 ，第2个word存64 ，第3个word存129 。假设输入x,那么他的word值是 （x+1）%64
比如说插入400000.
高32位说有几个有数据的Lw ,低32位是Rlw.高位代表后面的LW,低位代表前面的跨度几个空白。
11==00-00000-00000-00000-00000-00000-00000B

具体请看这篇文章
在EWAH算法中插入400000的时候，25769803776L = 11000000000000000000000000000000000B应该是错的。具体的自己算吧。

最后jdk自带bitmap算法，java.util.BitSet。。get ,set方法