算法：BitMap的常用代码。

妖狐艹你老母 2021-11-05 06:26 339阅读 0赞

# 偷懒的方法 #

--------------------

其实java.util包中已经有了一个实现，可以用这个数据结构偷懒，写了一个Demo如下：

package org.du.offerproblem.bitmap;
    
    import java.util.BitSet;
    
    /**
     * Created by 燃烧杯 on 2018/2/24.
     */
    public class BitSetTest {
    
        public static void main(String[] args) {
            int [] array = new int [] {1,2,3,22,0,3,63};
            BitSet bitSet  = new BitSet(1);
            System.out.println(bitSet.size());   //64
            bitSet  = new BitSet(65);
            System.out.println(bitSet.size());   //128
            bitSet  = new BitSet(23);
            System.out.println(bitSet.size());   //64
    
            //将数组内容组bitmap
            for(int i=0;i<array.length;i++)
            {
                bitSet.set(array[i], true);
            }
    
            System.out.println(bitSet.get(22));
            System.out.println(bitSet.get(60));
    
            System.out.println("下面开始遍历BitSet：");
            for ( int i = 0; i < bitSet.size(); i++ ){
                System.out.println(bitSet.get(i));
            }
        }
    
    }

java.util.BitSet的底层是long数组，.size()方法返回的是BitSet当前位数，因为long是64位的，所以size返回的值也是64的整数倍，所以在上面的代码中发现，我在构造函数中传入初始化长度1~64中的任意一个值，size的大小都是64位，因为此时long数组的长度只有1，而我一旦将其设置成65，size的大小就变成128了。  
用这个类是个偷懒的好办法，但是一旦面试官一定要让你自己实现一个就不行了。

# 自己实现BitMap #

--------------------

可以用int数组来实现一个BitMap，这种方法最关键的是求出index在int数组中的位置以及在该位置上的偏移量，有如下公式：

int数组中的位置(belowIndex) = (index - 1) >> 5
    偏移量(offset) = (index - 1) & 31

我们这里假设index是从1开始的，所以先将index减去1，如果你要统计的数据范围是从0开始的，则不需要减去这个1。右移5位（相当于除以32）的原因是，一个int型数据是32位的（2的5次方等于32）。偏移量中&31相当于模32，其原因也因为int型数据是32位的。如果你不准备基于int，而是准备基于其他的，如byte，long的话，（以byte为例）则将>>5改成>>3，&31改成&7即可。

setBit的流程如下：

1.  求出belowIndex并且得到int值；
2.  求出offset并且利用“或运算”将刚才得到的int值的offset位置置为1；

getBit的流程如下：

1.  求出belowIndex并且得到int值；
2.  求出offset，之后利用“与运算”取出offset位置的值将其变为01后返回；

代码如下：

package org.du.offerproblem.bitmap;
    /**
     * 实现BitMap
     *注：这个bitMap的index是从1开始的
     */
    public class BitMap {
        private long length;
        private static int[] bitsMap;
    
        //构造函数中传入数据中的最大值
        public BitMap(long length) {
            this.length = length;
            // 根据长度算出，所需数组大小
            bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
        }
    
        public int getBit(long index) {
            int intData = bitsMap[(int) ((index - 1) >> 5)];
            int offset = (int) ((index - 1) & 31);
            return intData >> offset & 0x01;
        }
    
    
        public void setBit(long index) {
            // 求出该index - 1所在bitMap的下标
            int belowIndex = (int) ((index - 1) >> 5);
            // 求出该值的偏移量(求余)
            int offset = (int) ((index - 1) & 31);
            int inData = bitsMap[belowIndex];
            bitsMap[belowIndex] = inData | (0x01 << offset);
        }
        public static void main(String[] args) {
            BitMap bitMap = new BitMap(32);
            bitMap.setBit(32);
            System.out.println(bitMap.getBit(1));
            System.out.println(bitMap.getBit(32));
        }
    }

# 使用BitMap进行数据去重 #

--------------------

下面给出数组去重的代码：

package org.du.offerproblem.bitmap;
    
    import java.util.Arrays;
    
    /**
     * Created by 燃烧杯 on 2018/2/24.
     * 这个BitMap的去重是从0开始
     */
    public class BitMapRepRemove {
        //public static final int _1MB = 1024 * 1024;
    
        //public static byte[] flags = new byte[ 512 * _1MB ];
    
        public static byte[] flags;
    
    
        public static void main(String[] args) {
    
            int[] array = {255, 1024, 1024, 0, 65536, 0, 1024, 8888, 9999, 1111, 8888};
    
            int length = 65536 + 1;
            flags = new byte[(int) (length >> 3) + ((length & 7) > 0 ? 1 : 0)];
    
            int index = 0;
            for(int num : array) {
                if( getFlags(num) != 1) {
                    //未出现的元素
                    array[index] = num;
                    index = index + 1;
                    //设置标志位
                    setFlags(num);
                }
            }
            array = Arrays.copyOf(array, index);
            System.out.println(Arrays.toString(array));
            System.out.println(array.length);
        }
    
        public static void setFlags(int num) {
            int offset = num & (0x07);
            flags[num >> 3] |= 0x01 << offset;
        }
    
        public static int getFlags(int num) {
            int offset = num & (0x07);
            return flags[num >> 3] >> offset & 0x01;
        }
    }