位图算法简介及Java代码解读

terry 2年前 (2023-09-27) 阅读数 65 #数据结构与算法

假设给你20亿个非负int型整数，然后给你一个非负int型整数t，然后让你决定是否这里存在 20 亿人中你会做什么。

有人可以使用 int 数组，在其中存储 20 亿个数字，然后循环遍历它。

想一下，这种情况下时间复杂度是O(n)，需要的内存空间是

4字节*20亿，总共需要80亿字节，

大约。需要8GB内存空间。显然，某些计算机的内存无法一次加载那么多数据。

初步优化

根据上述方法，时间复杂度为O(n)，内存为8GB。事实上，我们可以将时间复杂度降低到O(1)。

例如，我们可以通过使用 int 非负整数 n 作为数组签名来存储数据。如果n存在则对应值为1，如果不存在则对应值为0。例如数组arr[n] = 1表示n存在，arr[n] = 0表示n不存在不存在。

那么我们可以存储20亿个号码作为订阅者，然后直接确定arr[t]的值。如果arr[t] = 1，则表示存在。如果arr[t] = 0，表示不存在。这样我们就可以将时间复杂度降低到O(1)。然而，我们并没有降低空间复杂度。它有点大。

由于一共有2^31个int非负整数，所以数组的大小必须有2^32那么大。

这里可能有人会说，也可以用HashSet来存储，时间复杂度也是O(1)左右。不过，这里需要说明的是，HashSet中存储的对象必须是对象，也就是说int必须用Integer包装。当然对象会消耗更多内存，需要对象头等等...

再次优化

让我们考虑一个问题。对于一个数我们其实只需要两种状态，就是这个数存在和不存在的两种可能。上面我们用1代表存在，0代表不存在。

也就是说，我们可以不用int类型数组来存储。 int类型占用4个字节，即32个二进制位，总共可以表示超过40亿种状态。用int类型来存储两个状态是一种浪费。

所以我们可以考虑使用boolean类型来存储。 boolean 似乎占用一个字节（java 中的 boolean 似乎占用一个字节）。布尔值有两种状态：true 和 false，因此它也是 true。本例中记录的内存为2GB内存。

这样一来，内存就可以减少到之前的四分之一。

最终优化：位图

我们再考虑另一个问题。虽然boolean代表两种状态，但boolean实际上占用8位。逻辑上，8位可以代表128种状态。而我们用它来代表两个国家是不是有点浪费呢？

我们都知道二进制位有两种状态：0和1。所以实际上我们可以用二进制位来表示int类型的数字是否存在。例如，如果存在 1、3、5、7 这四个数字，则可以表示为：

1 表示该数字存在，0 表示该数字不存在。例如表中01010101表示1、3、5、7存在，0、2、4、6不存在。

那么如果8、10、14也存在的话，如何才能拯救它们呢？如图所示，第二个字节

可以存储8、10、14等。这样我们就可以将内存减少到之前的八分之一。

这种使用二进制位来存储数据的方法也称为位图算法。

有人可能会问，如果我要加一个数字n，我知道它一定存在于第n位，并将第n个二进制变为1，但是我该怎么做呢？

我会在后面的文章中讲到如何保存位图算法以及如何进行添加和删除操作。本文将简单介绍一下位图算法。

Java 有自己的位图实现。今天我们就利用Java自带的位图来练习题。让我们换一个类似的问题。我想知道您是否可以想出位图算法来快速完成此操作。

问题描述：

现在有五十亿个int类型的正整数，我们需要找到其中重复的数字并返回它们。

判断这50亿个数字中哪些是重复的，其实和上面的判断是一样的。我们使用位图算法来做到这一点。但是这里的50亿这个数字肯定是以文件流的形式给你的。这样，为了，我们假设这些数字是以int数组的形式给我们的。

代码如下：

public class Test {
    //为了方便，假设数据是以数组的形式给我们的
    public static Set<Integer> test(int[] arr) {
        int j = 0;
        //用来把重复的数返回，存在Set里，这样避免返回重复的数。
        Set<Integer> output = new HashSet<>();
        BitSet bitSet = new BitSet(Integer.MAX_VALUE);
        int i = 0;
        while (i < arr.length) {
            int value = arr[i];
            //判断该数是否存在bitSet里
            if (bitSet.get(value)) {
                output.add(value);
            } else {
                bitSet.set(value, true);
            }
            i++;
        }
        return output;
    }
    //测试
    public static void main(String[] args) {
        int[] t = {1,2,3,4,5,6,7,8,3,4};
        Set<Integer> t2 = test(t);
        System.out.println(t2);
    }
}

复制代码

打印结果：