踢树叶
0%

BitMap算法浅谈

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

BitMap 是使用 bit位来标记某个元素对应的value，而key 即是该元素，因此对于之前位数存储换成bit位存储数据能大大的节省存储空间。

我们先来看个简单的问题。
假如给你20亿个非负数的int型整数，然后再给你一个非负数的int型整数 t ，让你判断t是否存在于这20亿数中，你会怎么做呢？
有人可能会用一个int数组，然后把20亿个数给存进去，然后再循环遍历一下就可以了。
想一下，这样的话，时间复杂度是O(n)，所需要的内存空间
4byte * 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)。不过空间复杂度我们并没有降低。还稍微大了点。
由于int非负整数一共有 2^31 个，所以数组的大小需要 2^31 这么大。
这里可能有人说也可以用HashSet来存啊，时间复杂度也是近似O(1)。不过这里需要说明的是，HashSet里面存的必须是对象，也就是说需要把int包装成Integer，显然一个对象的话是更花销内存的，需要对象头啊什么的…..

再次优化

大家想一个问题，对于一个数，实际上我们只需要两种状态，就是这个数存在和不存在这两种可能。上面我们用1代表存在，用0代表不存在。
也就是说，我们是可以不用int型的数组来存储的，一个int型占用4个字节，即32个二进制位，一共可以表示40亿多个状态。用int型的来存两个状态，多浪费。
所以我们可以考虑用boolean型的来存的，boolean貌似就占用一个字节(java中的boolena貌似是占用一个字节)。而一个boolean有true和false两种状态，所以也是成立的。这样子的话占用的内存就是2GB的内存了。
这样，就可以降低到之前的四分之1内存了。

最终优化：BitMap

大家再想一个问题，虽然boolean是表示两种状态，但是boolean实际上占用了8bit啊，按道理8bit是可以表示128种状态的。而被我们拿来表示两个状态，是否也有点浪费了呢？
我们都知道，一个二进制位，有0和1两种状态，所以说，其实我们是可以用一个二进制位来代表一个int型的数是否存在的。例如对于1，3，5，7这四个数，如果存在的话，则可以这样表示：
【1，3，5，7】

数值 0 1 0 1 0 1 0 1
下标 0 1 2 3 4 5 5 7

1代表这个数存在，0代表不存在。例如上文01010101代表1，3，5，7存在，0，2，4，6不存在。
以此类推。这样子，我们又可以把内存降低到之前的8分之一了。
这种采用一个二进制位来存储数据的方法，我们也叫做BitMap算法。

BitMap算法实战

题目描述：

现在有五十亿个int类型的正整数，要从中找出重复的数并返回。

判断50亿个数有哪些是重复和刚才上面那个判断是否存在，其实是一样的。我们采用BitMap算法来做。不过这里50亿个数，别人肯定是以文件流的形式给你的。这样我们为了方便，我们就假设这些数是以存在int型数组的形式给我们的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
   }
}

打印结果

[3, 4]