【位图（Bitmap）】数据结构：高效存储与处理大量数据

���录

一、位图概念

1.面试题

2.位图的概念

二、位图的实现

三、位图的应用

使用位图进行排序

---

一、位图概念

1.面试题

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】

 对于这个问题，在前面学习到的知识中，我们有两种方案进行解决：

1. 遍历，时间复杂度O(N)
2. 排序 + 二分查找，时间复杂度O(NlogN) + O(logN)

而对于40亿的无符号整数来说，我们计算一下将这些数组放在内存中需要多大的空间：

10亿个字节换算后需要0.93GB的内存(近似看作1GB) -->

10亿个整型则需要4GB的内存 -->

40亿个整型就需要16GB的内存！！！

我们16GB的电脑内存刚开机就已经占用了20%以上的内存，因此对于这种场景，上述两种方案明显不可取。此时就需要用到位图解决。

2.位图的概念

        位图是一种数据结构，是用每一位来存放某种状态，适用于海量数据，整数，数据无重复的场景。通常是用来判断某个数据存不存在的。         数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比 特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

 如上例子，10个整数本应该存放需要40个字节，此时用位图只需要3个字节。而此时处理40亿个整型数据的问题也就迎刃而解了。

---

二、位图的实现

注意：模拟实现的位图只处理0和正整数数据

思路：一个字节有8个比特位，每个比特位只表示0和1。位图的关键就在于，对于每个字节，将其所有比特位用来表示对应的某些数存不存在。例如：一个byte类型占一个字节，也就是8个比特位，则第一个byte用来表示0-7，第一个表示8-15，以此类推。

下面，我用byte数组的方式模拟实现了一个位图（Java中BitSet集合类中用的是long数组，为什么？）

import java.util.Arrays;public class MyBitSet {    byte[] elem;    int usedSize;    public MyBitSet() {        elem = new byte[4];    }    //bits：elem数组需要存入的最大位数    public MyBitSet(int bits) {        elem = new byte[bits / 8 + 1];    }    //存入集合 -> 等价于将数据的对应位置为1    public void set(int val) {        if (val = elem.length * 8) {            elem = Arrays.copyOf(elem, val / 8 + 1);        }        int arrayIndex = val / 8; //该数字在数组中应存入的位置        int bitIndex = val % 8; //该数字在数组位置中应存入的比特位位置        elem[arrayIndex] |= (byte) (1  等价于检查数据的对应位置是否为1    public boolean get(int val) {        if (val = elem.length) {            return false;        }        int bitIndex = val % 8;        //逻辑& 如果结果不为0，说明当前bitIndex位置为1，否则为0        return (elem[arrayIndex] & (1 = elem.length) {            return;        }        int bitIndex = val % 8;        // 1