Bit-Map实现查找数组中的重复数字

约定不等于承诺〃 2022-05-10 12:58 218阅读 0赞

Bit-Map中文翻译为位图，其实和本文所谓的Bit-Map是有出入的。

> 所谓的Bit-Map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

查找一个数组中的重复数字，假设数组时从0开始的，且数组是乱序的，不用Bit-Map的方法就是申请一个boolean数组，数组的长度等于要去重数组的长度 。然后遍历要去重的数组，得到每个数字，在boolean数组的相应索引位置判断，如果为false，则更新为true，如果为true，则这个索引位置所对应的数组是重复数字。

例如：要去重的数组为 \{2, 3, 2, 1, 5, 4\}，初始化boolean数组 \{false, false, false, false, false, false\}

对数组进行遍历，第一个元素为 2 ，则boolean索引为 2 的位置进行更新操作。

更新后的beelean数组为 \{false, false, true, false, false, false\}

下一个元素为 3 ，索引为 3 的元素为 false，说明 3 还没有出现过，则更新为true。

更新后的boolean数组为 \{false, false, true, true, false, false\}

下一个元素为 2 ，索引为 2 的元素为 true，说明 2 已经出现过，则元素 2 为第一个重复的元素。

代码实现：

public boolean duplicate(int[] numbers) {
        if(numbers == null && numbers.length == 0) return false;
        boolean[] b = new boolean[numbers.length];
        for(int i = 0; i < numbers.length; i++) {
            if(b[numbers[i] == false) {
                b[numbers[i]] = true;
            } else {
                return false         //说明数组有重复元素
            }    
        }
        return true                //数组无重复元素
    }

代码实现非常简单，但是有一个问题，boolean类型在java中所占的字节，可以参考： [https://blog.csdn.net/YuanMxy/article/details/74170745][https_blog.csdn.net_YuanMxy_article_details_74170745]

从网上查阅资料了解到，**boolean的大小JVM规范并没有指定。**那boolean的大小就取决于JVM是如何实现的了。但是大多数实践发现，一个boolean所占大小为 1byte 。 [http://blog.51cto.com/mb1069/1077652][http_blog.51cto.com_mb1069_1077652]

1byte = 8bit，虚拟机的实现可能是用 0000 0001 表示 true，用 0000 0000 表示false，有 8 个位，但是只用到了 1 个位，在如今大数据的时代下，这是非常严重的内存浪费。在内存相同的情况下，如果 8个位 全部利用起来，可能使一次处理数据的数量提升 8倍。所以我们就要考虑把另外的七个位利用起来。

**Bit-Map用byte简单实现方法:**

用byte数组，一个byte所占内存空间为 1字节 ，也就是 8bit，但是却可以表示8种状态。还拿上面的去重数组举例

去重数组 \{2, 3, 0, 1, 3, 4\}，初始化一个byte，值为 0， 二进制位 0000 0000。

![70][]

一个byte可以表示 0 ~ 7。对数组进行遍历，第一个元素为 2，则把第三位也就是 2 的位置置为 1。

![70 1][]

现在byte表示有一个元素 2 。

下一个元素为 3，则把第三位置为 1。

![70 2][]

下一个为 0 。

![70 3][]

下一个为1 。

![70 4][]

再下一个为 3 ，但是此时 3 的位置已经被置为 1 了，所以 3 是第一个重复的元素。

Bit-Map大致原理就是这样，本来用 6 byte 才能搞定的事情，现在用 1 byte就能搞定。

实现代码如下：

private static byte[] bitmap;
    
    public static void initBitMap(int capacity) {
        int length = numbers.length % 8 == 0 ? numbers.length / 8 : numbers.length / 8 + 1;
        bitmap = new byte[length];    //如果numbers.length % 8 == 0，就不用 + 1
    
    }
        
    public static boolean setBit(int index) {
        int bIndex = index % 8;
        index = index / 8;
        byte b = (byte) (bitmap[index] >> bIndex);
        //以下代码有很大的改进空间，留给小伙伴们了
        if((b & 0x01) == 1) return false;
        byte temp = (byte) (0x01 << bIndex);
        bitmap[index] = (byte) (bitmap[index] | temp);
        return true;
    }
    
    public static boolean duplicate(int[] numbers) {
        if(numbers == null || numbers.length == 0) return false;
        initBitMap(numbers.length);
        for(int i = 0; i < numbers.length; ++i) {
            if(!setBit(numbers[i]) return false;
        }
        return true;
    }

以上

[https_blog.csdn.net_YuanMxy_article_details_74170745]: https://blog.csdn.net/YuanMxy/article/details/74170745
[http_blog.51cto.com_mb1069_1077652]: http://blog.51cto.com/mb1069/1077652
[70]: /images/20220505/c5bdc9f8b31e45a5ba89989522ce9a06.png
[70 1]: /images/20220505/fa15a016d8a146ddb375b5c59fd94727.png
[70 2]: /images/20220505/b1e01375762f4b1e91458963dbc26e7c.png
[70 3]: /images/20220505/b5729295bf9f45ef8b65de24f9bb4321.png
[70 4]: /images/20220505/0ed87936db414a4285c6a860c230dfcd.png