L
L
LearnJava
Search…
Bitmap

简介

bitmap的核心思想是利用元素本身的值来保存其位置,一般要求元素不能重复。Bitmap算法利用这种思想处理大量数据的排序、查询以及去重。

实例

例如我们有list [0, 2, 3, 4, 8, 10, 13, 14, 15, 16, 17, 19, 20, 22, 23],那么我们只需要24个bit就可以存储这些元素,策略如下:
  1. 1.
    构建一个长度为24个bit的数组
  2. 2.
    对所有数字做遍历,把bit 1插入到bit数组中下标与该数字值相等的位置;例如,数字5就应该向bit数组的第5个位置中插入1,插入后结果是 100000
  3. 3.
    重复上面的操作,直到把所有的数字都插入到bit数组中,此时数字保存完毕、并且此时数组中的数字都是有序的,操作完成。
代码实现:
1
package com.wangjun.test;
2
3
import java.util.ArrayList;
4
import java.util.HashSet;
5
import java.util.List;
6
import java.util.Random;
7
import java.util.Set;
8
9
public class Bitmap {
10
11
public static void main(String[] args) {
12
List<Integer> list = getList();
13
System.out.println(list);
14
int s = 0;
15
for (int i : list) {
16
// 把1左移i位的值等于2的i次方
17
// 之后把该值与s并上等于把该值上所有的1都插入s的对应位置上
18
s = s | 1 << i;
19
}
20
21
StringBuilder sb = new StringBuilder(Integer.toBinaryString(s));
22
System.out.println(sb.reverse()); // 对二进制做反转操作以方便观察
23
}
24
25
/**
26
* 生成随机的list
27
*/
28
private static List<Integer> getList() {
29
Set<Integer> set = new HashSet<>();
30
while (set.size() < 15) {
31
int i = new Random().nextInt();
32
if (i < 0)
33
i = -i;
34
i = i % 30;
35
set.add(i);
36
}
37
List<Integer> list = new ArrayList<>();
38
list.addAll(set);
39
return list;
40
}
41
}
Copied!
运行结果:
1
[0, 3, 5, 9, 11, 12, 13, 14, 18, 19, 21, 24, 25, 26, 28]
2
10010100010111100011010011101
Copied!
第一行是原始的值,第二行是用位图保存的值。我们发现位图的第0位、第3位、第5位 … 第26位、第28位上的值都为1,对应了这些下标所对应的值的存在,可见我们已经成功的把数字保存到了位图之中。
通过仔细的观察我们发现,在上面的例子中我们用一个int类型的值就可以保存15位大小在0~30之间的数字了,事实上一个int类型的值最多可以保存 4 * 8 = 32 个连续而不重复的数字,按照这样来算即使是1亿个连续而不重复的int类型数字也只需要
1
100000000 / 1024 / 1024 = 95.36M
Copied!
即只需要不到96M的内存我们就可以存下这些数字。如果我们不使用位图来保存则需要
1
100000000 * 32 / 1024 / 1024 = 3052M
Copied!
差不多是3个G左右的内存,可见Bitmap对内存的节省还是相当夸张的。
Last modified 1yr ago
Copy link
Contents
简介
实例