BitMap的原理和实现方法
这篇文章主要介绍"BitMap的原理和实现方法"，在日常操作中，相信很多人在BitMap的原理和实现方法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"BitMap的原理和实现方法"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
在java中：
byte -> 8 bits -->1字节char -> 16 bit -->2字节short -> 16 bits -->2字节int -> 32 bits -->4字节float -> 32 bits -->4字节long -> 64 bits -->8字节
BitMap实现原理
在java中，一个int类型占32个比特，我们用一个int数组来表示new int[32]，总计占用内存32*32bit，现假如我们用int字节码的每一位表示一个数字的话，那么32个数字只需要一个int类型所占内存空间大小就够了，这样在大数据量的情况下会节省很多内存。
具体思路：
1个int占4字节即4*8=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:
tmp[0]:可表示0~31 tmp[1]:可表示32~63 tmp[2]可表示64~95 .......
那么接下来就看看十进制数如何转换为对应的bit位：假设这40亿int数据为：6,3,8,32,35,......，那么具体的BitMap表示为：
如何判断int数字在tmp数组的哪个下标，这个其实可以通过直接除以32取整数部分，例如：整数8除以32取整等于0，那么8就在tmp[0]上。另外，我们如何知道了8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8 mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）。
/** * @author sowhat * @create 2020-08-20 19:30 */public class BitMap{ private long length; private static int[] bitsMap; private static final int[] BIT_VALUE = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000}; public BitMap(long length) { this.length = length; /** * 根据长度算出，所需数组大小 * 当 length%32=0 时大小等于 = length/32 * 当 length%32>0 时大小等于 = length/32+l */ bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)]; } /** * @param n 要被设置的值为n */ public void setN(long n) { if (n < 0 || n > length) { throw new IllegalArgumentException("length value ">BitMap应用
1：看个小场景 > 在3亿个整数中找出重复>=2次的整数，限制内存不足以容纳3亿个整数。
对于这种场景我可以采用2-BitMap来解决，即为每个整数分配2bit，用不同的0、1组合来标识特殊意思，如00表示此整数没有出现过，01表示出现一次，11表示出现过多次，就可以找出重复的整数了，其需要的内存空间是正常BitMap的2倍，为：3亿*2/8/1024/1024=71.5MB。
具体的过程如下：
扫描着3亿个整数，组BitMap，先查看BitMap中的对应位置，如果00则变成01，是01则变成11，是11则保持不变，当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为11的整数输出即可。
2：已知某个文件内包含一些电话号码，每个电话号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99百万个bit，大小= 99 999 999/8/1024/1024 =12M。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99百万个Bit==1.2MBytes，这样，就用了小小的12M左右的内存表示了所有的8位数的电话）。
另一种方式分析BitMap
一、问题引入
bitMap是位图，其实准确的来说，翻译成基于位的映射，举一个例子，有一个无序有界int数组{1,2,5,7},初步估计占用内存4*4=16字节，这倒是没什么奇怪的，但是假如有10亿个这样的数呢，10亿*4字节/(1024*1024*1024)=3.72G左右（1GB=1024MB 、1MB=1024KB 、1KB=1024B 、1B=8b）。如果这样的一个大的数据做查找和排序，那估计内存也崩溃了，有人说，这些数据可以不用一次性加载，那就是要存盘了，存盘必然消耗IO。我们提倡的是高性能，这个方案直接不考虑。
二、问题分析
如果用BitMap思想来解决的话，就好很多，解决方案如下：
一个byte是占8个bit，如果每一个bit的值就是有或者没有，也就是二进制的0或者1，如果用bit的位置代表数组值有还是没有， 那么0代表该数值没有出现过，1代表该数组值出现过。不也能描述数据了吗？具体如下图：
是不是很神奇，那么现在假如10亿的数据所需的空间就是3.72G/32了吧，一个占用32bit的数据现在只占用了1bit，节省了不少的空间，排序就更不用说了，一切显得那么顺利。这样的数据之间没有关联性，要是读取的，你可以用多线程的方式去读取。时间复杂度方面也是O(Max/n)，其中Max为byte[]数组的大小，n为线程大小。
三、应用与代码
如果BitMap仅仅是这个特点，还不是它的优雅的地方，接下来继续欣赏它的魅力所在。下面的计算思想其实就是针对bit的逻辑运算得到，类似这种逻辑运算的应用场景可以用于权限计算之中。
再看代码之前，我们先搞清楚一个问题，一个数怎么快速定位它的索引号，也就是说搞清楚byte[index]的index是多少，position是哪一位。举个例子吧，例如add(14)。14已经超出byte[0]的映射范围，在byte[1]范围之类。那么怎么快速定位它的索引呢。如果找到它的索引号，又怎么定位它的位置呢。Index(N)代表N的索引号，Position(N)代表N的所在的位置号。
Index(N) = N/8 = N >> 3; Position(N) = N%8 = N & 0x07;
(1) add(int num)
你要向bitmap里add数据该怎么办呢，不用担心，很简单，也很神奇。
上面已经分析了，add的目的是为了将所在的位置从0变成1.其他位置不变.
public void add(int num){ // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。 bits[arrayIndex] |= 1 << position; }(2) clear(int num)
对1进行左移，然后取反，最后与byte[index]作与操作。
public void clear(int num){ // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后，那个位置自然就是1，然后对取反，再与当前值做&，即可清除当前的位置了. bits[arrayIndex] &= ~(1 << position); }(3) contain(int num)
public boolean contain(int num){ // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可 return (bits[arrayIndex] & (1 << position)) !=0; }全部代码：
public class BitMap { //保存数据的 private byte[] bits; //能够存储多少数据 private int capacity; public BitMap(int capacity){ this.capacity = capacity; //1bit能存储8个数据，那么capacity数据需要多少个bit呢，capacity/8+1,右移3位相当于除以8 bits = new byte[(capacity >>3 )+1]; } public void add(int num){ // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。 bits[arrayIndex] |= 1 << position; } public boolean contain(int num){ // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可 return (bits[arrayIndex] & (1 << position)) !=0; } public void clear(int num){ // num/8得到byte[]的index int arrayIndex = num >> 3; // num%8得到在byte[index]的位置 int position = num & 0x07; //将1左移position后，那个位置自然就是1，然后对取反，再与当前值做&，即可清除当前的位置了. bits[arrayIndex] &= ~(1 << position); } public static void main(String[] args) { BitMap bitmap = new BitMap(100); bitmap.add(7); System.out.println("插入7成功"); boolean isexsit = bitmap.contain(7); System.out.println("7是否存在:"+isexsit); bitmap.clear(7); isexsit = bitmap.contain(7); System.out.println("7是否存在:"+isexsit); }}到此，关于"BitMap的原理和实现方法"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！
