（自定义）BitMap在大数据下实现去重

末蓝、 2021-12-11 05:55 375阅读 0赞

> ### **（自定义）BitMap在大数据下实现去重** ###

**【BitMap】**：bitmap是很有用的结构。所谓的bitmap就是用一个bit位来标记某个元素，而数组下标是该元素。

**【方式一：用byte\[\]数组计数实现BitMap】： 参考 **[Java中Bitmap的实现][Java_Bitmap]

package com.caox.utils;
    
    import lombok.extern.slf4j.Slf4j;
    
    /**
     * @author : nazi
     * @version : 1.0
     * @date : 2019/7/9 15:14
     */
    @Slf4j
    public class BitMapUtils {
        /**
         * 创建bitmap数组
         */
        public static byte[] create(int n){
            byte[] bits = new byte[getIndex(n) + 1];
    
            for(int i = 0; i < n; i++){
                add(bits, i);
            }
    
            System.out.println(contains(bits, 11));
    
            int index = 1;
            for(byte bit : bits){
                System.out.println("-------" + index++ + "-------");
                showByte(bit);
    
            }
    
            return bits;
        }
    
        /**
         * 标记指定数字（num）在bitmap中的值，标记其已经出现过<br/>
         * 将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了
         * @param bits
         * @param num
         */
        public static void add(byte[] bits, int num){
            bits[getIndex(num)] |= 1 << getPosition(num);
        }
    
        /**
         * 判断指定数字num是否存在<br/>
         * 将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可
         * @param bits
         * @param num
         * @return
         */
        public static boolean contains(byte[] bits, int num){
            return (bits[getIndex(num)] & 1 << getPosition(num)) != 0;
        }
    
        /**
         * num/8得到byte[]的index
         * @param num
         * @return
         */
        public static int getIndex(int num){
            return num >> 3;
        }
    
        /**
         * num%8得到在byte[index]的位置
         * @param num
         * @return
         */
        public static int getPosition(int num){
            return num & 0x07;
        }
    
        /**
         * 重置某一数字对应在bitmap中的值<br/>
         * 对1进行左移，然后取反，最后与byte[index]作与操作。
         * @param bits
         * @param num
         */
        public static void clear(byte[] bits, int num){
            bits[getIndex(num)] &= ~(1 << getPosition(num));
        }
    
        /**
         * 打印byte类型的变量<br/>
         * 将byte转换为一个长度为8的byte数组，数组每个值代表bit
         */
    
        public static void showByte(byte b){
            byte[] array = new byte[8];
            for(int i = 7; i >= 0; i--){
                array[i] = (byte)(b & 1);
                b = (byte)(b >> 1);
            }
    
            for (byte b1 : array) {
                System.out.print(b1);
                System.out.print(" ");
            }
    
            System.out.println();
        }
    
        public static void main(String[] args) {
            int n = 101;
            byte[] bits =  BitMapUtils.create(n);
            log.info("call  检测是否包含其中 ：{}", BitMapUtils.contains(bits,100));
        }
    }

**【方式二：用int\[\]数组计数实现BitMap】** ：参考文献：[Java面试中常用的BitMap代码][Java_BitMap]

**setBit的流程如下：**

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

**getBit的流程如下：**

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

package com.caox.utils;
    
    /**
     * @author : nazi
     * @version : 1.0
     * @date : 2019/7/10 13:35
     */
    public class BitMap {
        private long length;
        private static int[] bitsMap;
    
        /**
         * 构造函数中传入数据中的最大值
         * @param length
         */
        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进行数据去重：采用byte\[\]实现】： **

package com.caox.utils;
    
    import java.util.Arrays;
    
    /**
     * @author : nazi
     * @version : 1.0
     * @date : 2019/7/10 14:53
     */
    public class BitMapRepRemove {
        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;
        }
    }

[Java_Bitmap]: https://www.jianshu.com/p/e530baada558
[Java_BitMap]: https://www.jianshu.com/p/9e7f8f33a61a?from=singlemessage