BitMap原理与实现

比较经典的问题是： 在只能够使用2G的内存中，如何完成以下 *** 作：

①：对10亿个不重复的整数进行排序。

②：找出10亿个数字中重复的数字。

无论是排序还是找重复的数字都需要将这10亿个数字加入到内存中在去进行 *** 作，很明显，题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的

1000000000* 4/（1024* 1024* 1024） = 3.725G

那么这时候就需要用到 BitMap结构了

bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,而map的key值正是这个数字本身。

相比于一般的数据结构需要用4个byte去存储数值本身，相当于是节省了 4*8：1 = 32倍的内存空间

bitMap不一定要用bit数组,可以使用 int,long等等的基本数据类型实现，因为其实质都是在bit位上存数据，用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少

    例如：java中的BitSet使用Long数组

BitMap的实现当然少不了位运算，先来明确几个常见位运算，这是实现BitMap的基础：

set(bitIndex): 添加 *** 作

    1 .确定该数处于数组中的哪个元素的位上

     int wordIndex = bitIndex >>5

因为我用的是int[]实现，所以这里右移 5 位（2^5 = 32）

    2 .确定相对于该元素中的位置偏移

     int bitPosition = bitIndex &((1 <<5) - 1)

这里相当于是 bitIndex % （1<<5）的取模运算，因为当取模运算的除数是2的次幂，所以可以使用以下的位运算来计算，提升效率（对比HashMap的容量为什么总是2的幂次方的问题，HashMap求下标时也是使用 hash&(n-1)）

tips: 位运算的优先级是低于+,-等等的，所以要加上括号,防止发生不可描述的错误

    3 .将该位置1

     bits[wordIndex] |= 1 <<bitPosition

相当于是将指定位置处的bit值置1，其他位置保持不变，也就是将以这个bitIndex为key的位置为1

tips: 这里是参考了网上的各位大佬的文章,取余 + 按位或，又对比了下BitSet的源码：

     words[wordIndex] |= (1L <<bitIndex)

没有取余 *** 作，直接|，这两个一样吗？答案当然是一样的

举个栗子：

     1 <<148 == 1<<20     

     1L <<125 ==1L<<61

即对于int和long型数据，直接左移其位数相当于是附带了对其的取模 *** 作

总结 ：使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的 *** 作。

Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构

当一个元素加入布隆过滤器中的时候，会进行哪些 *** 作：

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行哪些 *** 作：

然后，一定会出现这样一种情况： 不同的字符串可能哈希出来的位置相同 （可以适当增加位数组大小或者调整我们的哈希函数来降低概率）,因此： 布隆过滤器可能会存在误判的情况

总结来说就是： 布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在 。

Bloom Filter的应用: 常用于解决缓存穿透等场景。

在网上有一道面试题大概意思就是: 存在十亿个数字,现在需要知道哪些数字没有出现在里面. 这个问题你可能觉得一个for循环就能解决,但是实际上你可能忽略了一个问题,那就是10亿个数字需要占据的内存空间.例如在java中要存下10亿个数字需要多大空间呢?假设使用int存储,一个int占32个位也就是4个字节.存放10亿个数字则需要: 10亿*4/1024/1024/1024 = 4G左右 .面对上面的问题我们肯定不能使用这种方式存储.而使用我们的Bitmap就能很好的解决上面的问题.

Bitmapi简单的说就是使用bit(位)来存储状态,适合用来存储大规模的数据,但是状态又不是很多的情况.举例来说,如果我现在有 1,3,4,2,7 这五个数字,如果我们使用5个int来存储则需要20个字节的空间.但是我现在使用1字节就能存储上面的五个数字.如下图所示,1个字节可以用8位表示,1位有0和1两种值分别用来表示该位上是否有值,而位的索引用来表示数字(图中以从左到右的顺序计算).

而它的缺点同样也比较明显.它的一个位只能存储一个数据,对于重复的数据无法记录.如果数据分布很稀疏,会造成空间的浪费.例如,如果现在只有{1,3,1000000000}这个三个数据,它有很多空间会被浪费掉.

BitMap在java中提供了BitSet的实现,同时在我们平常使用的Redis中也有实现.它很适合用来做大量的用户统计.例如统计登录人数,签到,在线等等.这些需求都可以通过redis的bit相关指令很简单的就能实现.

例如,统计网站的在线人数:

上面的方式不仅简单,而且就算用户数量很大也能又快又好的完成.

---