bitmap数据结构

32位机器上的自然数一共有2的32次方约42亿个，如果用一个bit来存放一个整数，1代表存在，0代表不存在，那么把全部自然数存储在内存只要4294967296 / (8 * 1024 * 1024) = 512MB(8bit = 一个字节)，而这些自然数存放在文件中，一行一个数字，1个整数4个字节，4*8*512MB需要16G的容量。可见，bitmap算法节约了非常多的空间。

ps：占内存 10bit

应用：

Bitmap不仅方便查询，还可以去除掉重复的整型数。

使用场景：

开发一个用户画像系统，实现用户信息的标签化。用户标签包含用户的社会属性，生活习惯，消费行为。

通过用户标签，实现多样的用户群体统计，统计用户的男女比例，统计喜欢旅游的用户数量等。

1. 建立用户名和用户ID的映射：  1->me   2->you  3->he

2.让每一个标签存储包含此标签的所有用户ID，每一个标签都是一个独立的Bitmap。

男[1,2]   女[3] 爱旅游[2]  程序员[1,2]

3. 这样，实现用户的去重和查询统计，就变得一目了然：

Bitmap在做交集和并集运算的时候也有极大的便利。位运算的高性能。

男性的程序员  110&110=110

不能做非运算，并不是除了1,2的其他都是女性，其实只有3是女性。除非提供一个全量的Bitmap，做异或即可。

一个很长的Bitmap里使用率低的话很浪费空间。

谷歌所实现的EWAHCompressedBitmap中，对存储空间做了优化：

com.googlecode.javaewah

JavaEWAH

1.1.0

redis 用setbit(bitmap)统计活跃用户

Redis支持对String类型的value进行基于二进制位的置位操作。通过将一个用户的id对应value上的一位，通过对活跃用户对应的位进行置位，就能够用一个value记录所有活跃用户的信息。如下图所未，下图中的bitmap有9个位被置为1，表示这9个位上对应的用户是今天的活跃用户。其中第15位表示uid为15的用户，第一位表示uid为0的用户。(如果你的uid不是从1开始的，比如从100000开始，实际上你也可以相应的用uid减去初始值来表示其位数，比如1000000用户对应到bitmap的第一位)

具体的代码类似下面这样：

redis.setbit(play:yyyy-mm-dd, user_id, 1)

这样一次记录的复杂度是O(1)，在Redis中速度非常快。