BitMap是啥?脑袋一下空白? bitmap文件头

面试过程中我们会被问到了解BitMap吗？在项目开发中如何使用BitMap?那么到底什么是BitMap，在开发中BitMap的优势在哪？我们又如何实现它呢？今天我们带着这些问题一起走进BitMap。

一、什么是BitMap

BitMap本质可以理解成bit数组，其中的每一个bit用来表示某个元素的value值。其中bit即比特，是计算机系统里边数据的最小单位，8个bit即为一个Byte。一个bit的值，要么是0，要么是1。

二、BitMap简单案例

在Java中，一个整数int类型占4个字节，1个字节占8位(1 byte = 8 bit)。如果每个数字都用int类型来存储，那么20亿个int整数所占用的空间为(2000000000*4/1024/1024/1024)≈7.45G ，是不是空间占用很大呀！！那么有没有一种方式可以压缩一下空间呢？答案是有的，使用BitMap就可以实现。

先举个示例：

我们存一个整数10，那么在BitMap中存储的时候key就是10，BitMap的value就是用来存储key对应的value值，即如下图将标识为10的那个bit位标记成1。如下图的bit数组：

详解一下：这是一个10bit的数组，从左往右数分别是0，1，2，...10代表11个数字。对于数据10来讲，存储在内存中就是在第10个标记上设置成1，代表数字 10存在这了，前面的都是0 代表没有数字。

这么一举例，20亿个整数是不是也可以使用同样的方式来存储数据了，使用20亿个bit空间来存储了呢！即按位存储，20亿个数就是20亿位，占用空间约为(2000000000/8/1024/1024/1024)≈0.233G。这样一对比是不是就看出BitMap的优势了。

三、BitMap优缺点

BitMap在数据稠密的时候，非常节省空间，但是在数据稀疏的时候，会有极大的浪费。

详解：我们知道一个int型的整型数字存储在内存中是占4个字节，一个字节是8bit，还是拿上面的例子，存储一个数字10，用一个int型数组 int[1] 表示的话 就是 1*4*8=32 bit，在内存中占 32bit位，如果是使用 BitMap存呢？32bit 可以存 32个数字，每一个bit位可以代表一个数字（即可以存储从1到32，共32个数字），理解了吗？这就是BitMap在存储空间上的优势。

同理这样也会有个劣势，假如BitMap就只是存一个很大的数字 10000， 那怎么表示呢，那就在第10000个bit位上设置1，其它的bit位还是默认的0，那么BitMap此时是占了 10000bit的，而10000这个数字用一个int类型的数组存的话，内存中还是只占32bit，在数据稀疏的时候，会有极大的浪费。

四、BitMap之Redis案例

在Redis中，使用"位图（Bitmap）"数据结构来表示一个可能非常大的布尔向量，其中每个位(bit)代表某个对象是否存在或某个事件是否发生过。在Redis中，我们可以通过SETBIT、GETBIT等命令来设置或获取这些位的值。

以下是一个简单的Redis Bitmap实现示例，假设我们要记录用户在每天登录的情况：

// 假设我们要记录从2022年1月1日至2022年12月31日期间，某个用户每天是否登录

String userKey = "user:1000:login";

for (int i = 0; i < 365; i++) {

// 这里使用当前日期作为位图中的下标，例如1号的下标为0，2号的下标为1，以此类推

int dayIndex = i;

// 假设用户在2022年的前半年登录过，后半年没有登录

boolean isLogin = i < 182; // 前半年有183天，0~182是登录，183~364是未登录

// 设置位图中对应的位的值

jedis.setbit(userKey, dayIndex, isLogin ? "1" : "0");

}

该示例使用setbit命令来设置位图中某个位置的值，其第一个参数为键名，第二个参数为位图中的下标，第三个参数为要设置的值。在本例中，我们使用一个字符串类型的键user:1234:login来表示某个用户在每天是否登录，并使用当前日期作为位图中的下标。具体而言，下标为0代表2022年1月1日，下标为364代表2022年12月31日。我们使用一个循环来遍历每天，将该用户在当日是否登录的信息设置到位图对应的位置上。

之后，我们可以使用getbit命令来获取某个日期的登录情况。其第一个参数为键名，第二个参数为位图中的下标，返回值是一个布尔类型的对象，代表该位置上的值（即用户在该日期是否登录）。在本例中，我们获取2月29日的登录情况，其对应的下标为58。

// 获取用户在某个日期是否登录

int dayIndex = 59; // 2月29日的下标为58

Boolean isLogin = jedis.getbit(userKey, dayIndex) == 1;

System.out.println("用户在2月29日是否登录：" + isLogin);

Redis的Bitmap是一种纯粹的位图，它仅仅用于存储和检索单个二进制位的值。在Redis中，Bitmap通常用于实现类似于计数器、日志记录、用户状态跟踪等简单的功能。

五、布隆过滤器之BitMap案例升级

布隆过滤器是一种快速判断一个元素是否在一个集合中的数据结构，它使用哈希函数将元素映射成位数组中的多个位置，并将这些位置标记为已经被占用。当查询一个元素时，如果对应的位置都已经被占用，那么这个元素可能存在于这个集合中；否则，这个元素一定不存在于集合中。

布隆过滤器可以应用于很多场景，比如在处理类似于网页缓存、垃圾邮件过滤、爬虫去重等应用场景时非常有用。

以下是一个简单的基于Java语言实现的布隆过滤器示例代码：

public class BloomFilter {

private BitSet bitSet; //存储每个元素的哈希值

private int size; //BitSet的大小

private int hashCount; //要使用的哈希函数数量

public BloomFilter(int size, int hashCount) {

this.size = size;

this.hashCount = hashCount;

this.bitSet = new BitSet(size);

}

//将一个元素添加到布隆过滤器中

public void add(String element) {

for (int i = 0; i < hashCount; i++) {

int hash = hash(element, i);

bitSet.set(hash);

}

}

//检查布隆过滤器是否包含给定的元素

public boolean contains(String element) {

for (int i = 0; i < hashCount; i++) {

int hash = hash(element, i);

if (!bitSet.get(hash)) {

return false;

}

}

return true;

}

//用于计算元素的哈希值

private int hash(String element, int index) {

int hash = 17;

hash = 31 * hash + element.hashCode();

hash = 31 * hash + index;

return Math.abs(hash % size);

}

}

在这个示例中，布隆过滤器使用一个BitSet来存储每个元素的哈希值。构造函数接受两个参数：size是BitSet的大小，hashCount是要使用的哈希函数数量。add()方法用于将一个元素添加到布隆过滤器中，contains()方法用于检查布隆过滤器是否包含给定的元素。hash()方法用于计算元素的哈希值。

六、总结

看到这里是不是对BitMap有一个清楚的认识了。不过我还想再补充一点，BitMap中的value能表达的状态有限(只能是0或1)，且所有的数据不能重复。即不可对重复的数据进行排序和查找。