位图—BitMap和BitSet，布隆过滤器，Roaring Bitmap

位图

简单来说就是为了压缩节省空间，才出现的。
           

举个例子：

你要是存储三个数字 2,5,10。这三个数字用java中的short类型来存储，也要6个Byte（short类型的内存空间是2Byte）。一个Byte是8bit，一共占用是64bit。我们知道bit的取值非0即1.

如果我用bit来表示这三个数字呢？

0010010000100000

从0开始，对应的位置上放1，这样16个bit就能表示这三个数字了，一共占用内存2byte。
           

比起上面的6Byte,用bit这样表示2byte可节省了不少空间。

BitMap

为什么叫BitMap呢？

我们知道Map类型的数据结构是key-value类型的，这里的BitMap也是这样的，比如我们在BitMap里面
	
	存储一个2，这个2就是key，value就是对应的bit位上的0或者1，这就是BitMap。	
           

BitSet

为什么叫BitSet呢？

我们知道Set在我们眼里是去重的类似于list的结构，没错这里也是这个意思，比如一组数字2，3，2，5，7
	
	存储第一个2的时候，对应的bit位已经置为1了，再去存储第二个2的时候对应的bit位已经是1了，
	
	这样就去重了。而且java中BitSet就是BitMap的实现。为什么不是两个类呢？我想了一下，因为一个BitSet
	
	就已经具备这两个的功能了。你想想是不是。
           

拓展

其实基于BitMap的变型有很多，比如布隆过滤器，

布隆过滤器

主要目的是去重。主要思想是根据多个Hash函数,根据Hash出来的结果(hash函数结果一般是Integer)将对应位置的bit置为1，举个例子：

比如重复过滤字符串“中国人牛逼”，几个Hash函数的结果分别是67829，23424，,575675，就将对应的
		
		位置bit置为1，然后再过滤到“中国人牛逼”的时候，发现67829，23424，,575675对应的位置的bit
		
		已经是1了，就认为已经存在了，这样就去重了，
           

从上面的原理我们可以知道，这个会存在误判重，布隆过滤器的效果好不好，

主要取决于选的Hash函数的散列效果，不然如果hash函数的散列效果比较差，主要集中在某一段取值上，这样很快就会把这一段位置的bit置为1，然后后面来的都会被认为重复，即是bit数组再大也没效果。

还有就是bit数组的大小，不然Hash函数散列效果再好，数组太小，也会出现上面的问题。

Roaring Bitmap

Roaring Bitmap算是对BitMap的优化，怎么优化呢？举个例子：

我现在只要存储两个数字0, 8388607这要是按照上面的BitMap去存储的话，这就需要一个

8388608个bit大的数组，也就是1M，我日，存储两个数字要用1M的内存，可见

BitMap有时候效率并不高，于是乎就出现了各种版本的优化，这里就出现了Roaring Bitmap。
           

Roaring Bitmap下文简称RBM，不是RMB

原理也很简单，RBM将一个Integer类型的数字分类高16位和低16位，我们知道16位的最大值是2^16，
	
	然后创建一个2^16的数组，数组的类型是Container，Container又分为不同的类型，
	
	先说为什么分为2^16个数组长度，一个Integer类型的数字，除以2^16得到的商和余数分别对应这个
	
	Integer高16位和低16位对应的值。所以当一个数存储到RMB的时候，就会那这个数除以2^16，
	
	然后根据商找到数组中对应下标的Container，然后在将余数放到Container中，这样就完成了

	一个Integer的存储。
           

上面大致介绍了RBM的原理，但是一直没有介绍他的Container，相比于BitMap，Container也是新增的概念，可见优化的点就在这个Container上，下面我们详细介绍一下这个Container。

Container 主要有两种：
	
	一种是ArrayContainer主要存放稀疏数据，它的数据结构是Short类型的数组，可以动态扩容，

	最大容量为4096，当超过4096则转换成BitContainer，而且数组是有序的可以通过二分法快速定位到。
	
	另一种是BitContainer主要存放稠密数据，数据结构是Long型的数组，切容量恒定为1024，存储方式

	像上面的BitMap一样，查找定位可以直接定位，如果对应的bit是1，就是存在。
           

为什么ArrayContainer的数据类型是Short？

因为Container里面存储的是余数，余数最大就是2^16,刚好在short范围内。

为什么BitContainer是恒定的Long型1024长度的数组？

因为是按照BitMap的形式操作的，Long型是64bit，1024长度的Long型数组，刚好有2^16个bit，

余数最大刚好是2^16。能容下所有的数。

为什么大于ArrayContainer容量大于4096转换成BitContainer？

因为BitContainer是Long型1024长度的恒容数组，也就是内存占用是8Byte*1024 = 8KB，ArrayContainer short类型4096容量时，占用的内存 2Byte * 4096 =8KB，所以当ArrayContainer 容量超过4096占用的内存就会大于8KB，就不划算了，所以就会转换成永远不会变的BitContainer的8KB