位图算法：什么是BitMap
BitMap算法的核⼼思想是⽤bit数组来记录0-1两种状态，然后再将具体数据映射到这个⽐特数组的具体位置，这个⽐特位设置成0表⽰数据不存在，设置成1表⽰数据存在。
BitMap算在在⼤量数据查询、去重等应⽤场景中使⽤的⽐较多，这个算法具有⽐较⾼的空间利⽤率。
本⽂参考：
1. 位图算法的简单原理
给定长度是10的bitmap，每⼀个bit位分别对应着从0到9的10个整型数。此时bitmap的所有位都是0。
把整型数4存⼊bitmap，对应存储的位置就是下标为4的位置，将此bit置为1。
把整型数2存⼊bitmap，对应存储的位置就是下标为2的位置，将此bit置为1。
要问此时bitmap⾥存储了哪些元素？就⼀⽬了然。
Bitmap不仅⽅便查询，还可以去除掉重复的整型数。
2. BitMap的开源实现
BitMap算法的开源实现由JDK的BitSet和⾕歌的EWAHCompressedBitmap。
BitSet是对BitMap算法的简单实现，⽽EWAHCompressedBitmap对BitMap的存储空间做了优化。
我们还是接着上⾯列⼦往下讲。上⾯我们已经在BitMap中插⼊了2和4两个数，现在数据中的数存储如下：
加⼊现在要插⼊⼀个⾮常⼤的数，⽐如10000000，那么BitMap必须要开启⼀⼤块空间来存储10000000，但是这篇空间中的很多Bit位是⽤不到的。在这种数据分布极度不均匀的情况下BitMap的空间利⽤率是很低的。EWAHCompressedBitmap实现就对这种情况作了优化。具体的优化算法这边就不做详细解释了。可以参考这篇
3. 使⽤案列
给定10亿个不重复的正int的整数，没排过序的，然后再给⼀个数，如何快速判断这个数是否在那10亿个数当中。
解法：遍历40个亿数字，映射到BitMap中，然后对于给出的数，直接判断指定的位上存在不存在即可。
使⽤位图法判断正整形数组是否存在重复
位字符串是什么解法：遍历⼀遍，存在之后设置成1，每次放之前先判断是否存在，如果存在，就代表该元素重复。
使⽤位图法进⾏元素不重复的正整形数组排序
解法：遍历⼀遍，设置状态1，然后再次遍历，对状态等于1的进⾏输出，参考计数排序的原理。
在2.5亿个整数中出不重复的正整数，注，内存不⾜以容纳这2.5亿个整数
解法1：采⽤2-Bitmap（每个数分配2bit，00表⽰不存在，01表⽰出现⼀次，10表⽰多次，11⽆意义）。
解法2：采⽤两个BitMap，即第⼀个Bitmap存储的是整数是否出现，接着，在之后的遍历先判断第⼀个BitMap⾥⾯是否出现过，如果出现就设置第⼆个BitMap 对应的位置也为1，最后遍历BitMap，仅仅在⼀个BitMap中出现过的元素，就是不重复的整数。
解法3：分治+Hash取模，拆分成多个⼩⽂件，然后⼀个个⽂件读取，直到内存装的下，然后采⽤Hash+Count的⽅式判断即可。
该类问题的变形问题，如已知某个⽂件内包含⼀些电话号码，每个号码为8位数字，统计不同号码的个数。8位最多99 999 999，⼤概需要99m个bit，⼤概10⼏m字节的内存即可。（可以理解为从0-99 999 999的数字，每个数字对应⼀个Bit位，所以只需要99M个Bit==12MBytes，这样，就⽤了⼩⼩的12M左右的内存表⽰了所有的8位数的电话）
BitMap的⼀些缺点：
（1）数据碰撞。⽐如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑⽤ Bloom Filter 来解决，Bloom Filter 使⽤多个 Hash 函数来减少冲突的概率。
（2）数据稀疏。⼜⽐如要存⼊(10,8887983,93452134)这三个数据，我们需要建⽴⼀个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很⼤的空间浪费，碰到这种问题的话，可以通过引⼊ Roaring BitMap 来解决。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。