BitMap算法和Java的实现类BigSet

考虑下面几个应用场景：

1. 统计每天的日活（访问量、用户数等）
2. 统计某个部门的联系客户量
3. 对大量数据进行排序

针对第一种应用场景，通常的做法就是采用明细表来记录每一个访问量，然后统计每天的用户数（用一个用户，多次访问，只算一个）。

这里有个问题，就是假设用户量比较大，假设一天有1000万的请求量，一个月就有3亿的数据量，对数据库的压力比较大。

这是我们就可以考虑采用BigMap来实现，它之间用位置代替数字，用0和1来表示这个数字是否存在，可以加大的压缩存储空间。比如说，1亿个用户一天的数据量也就 1 0000 0000bit = 11.92m，也就是说用户一天的登录信息也就产生11.92m的数据量。一个月也就357.63m的数据量。

Java的实现就是BigSet，下面是一段实现代码：

BitSet bm = new BitSet();

System.out.println(bm.isEmpty()+"--"+bm.size());

bm.set(0);

System.out.println(bm.isEmpty()+"--"+bm.size());

bm.set(1);

System.out.println(bm.isEmpty()+"--"+bm.size());

System.out.println(bm.get(65));

System.out.println(bm.isEmpty()+"--"+bm.size());

bm.set(65);

System.out.println(bm.isEmpty()+"--"+bm.size());

上面的逻辑很好理解，存储的数据越大，BitSet就会自动扩展64位来存储，所以当数据量不多的时候，占用的存储也不多。

正常影响，一个int数据是32位，而BitSet则可以存储32个数字和0/1标志位。所以正常情况下，存储空间只需要原先1/32甚至更小。

但这种实现也有一个缺点，就是数据过于稀疏的情况下，会产生大量无效遍历，导致低效。

另外，BitSet只能存储int数据，当数据量超过int范围的时候，BitSet就不够存放了，这个时候该怎么办呢？

一种思路就是拆分多个BitSet来存放数据，比如说，现在最大的用户编号已经达到int的1.5倍，那么我们用2个BitSet来存放。

针对第二种场景，通常的做法是直接从明细表统计，当时当数据量比较大的时候，压力就上来了。如果是要求实时统计，则压力更大。

采用BigSet可以解决这个问题，把没有员工的访问数据保存到BigSet中，然后一个部门，则通过部门内的员工的BigSet进行与或操作，通过实行多个员工的统计。

针对第三个产品，往往使用sql语句，采用order by对数据进行排序，但这种方法在遇到大量数据的时候性能很差。

采用BigSet存储数据，那么数据天生就是排序的，可以顺序获取。