前言
希望读者在阅读本文后能对BitMap有所了解，同时如果本文有不对的地方希望指出我会尽快修改。😅
结构了解
BitMap 多用于大数据量的场景。
举个🌰: 假设我们有10亿的int数据，那么我们需要 4*10亿=40亿字节≈4G空间
BitMap🤣正如直译“位图”一样，非常的形象。下面看一张图
上面的图表示我们存储了数字 3、5
🎈我们用一个bit来表示每一个数字
即：我们声明一个长度为 n 的比特数组，利用下标来表示数字
当数组的第 i 位元素为1时则代表 i 存在
这样是不是就不用每一个数字都占用4字节空间了。
🍟下面对比一下存储的空间
int 类型，存储1个数字需要 4字节=32比特
bit 数组，存储1个数字只需 1比特
相当于节省空间 32 倍
🎃现在如果用 BitMap 来存储10亿数字只需要：4G/32≈125Mb
4G与128M，何等的卧槽
算法了解
🤔那么我们如何存储呢？
上面说到了我们的每一个数字只占1个bit，我们这里用int[]来举🌰
👓假设我们要存储最大数为 n 的一堆数字，那么我们的数组大小为：n / 32 +1
int[] bits = new int[n/32+1];
下面我们如何在一个int中存储32个数字，我们知道int占4字节也就是32bit。一个数字也就对应1bit，列举一下数字存储情况
bits[0] => [0, 31]
bits[1] => [32, 63]
bits[2] => [64, 95]
…
对于数字 k
对应 bits 的下标 i = k / 32
在下标 i 中的对应位置 j = k % 32
即数字 k 在 bits[k / 32][k % 32] 位置，🤔为什么上面是一维数组这里又是二维数组了。为了方便读者理解，实际上还是一维数组，我们将数组中的每个数字都看成一个二进制，此时就相当于一个二维数组了
// int[] bits = new int[n/32+1];
public void add(int k) {
bits[k >> 5] |= 1 << (k & 0x1f);
}
k >> 5 相当于 k / 32
k & 0x1f 相当于 k % 32
1 << (k & 0x1f) 相当于 2k & 0x1f，即将 k & 0x1f 位数字标记
整个式子就是：将 bits 中下标为 k/32 的数字从右往左数第 k & 0x1f 位二进制数标记为1
且重复标记答案一样
上面讲解了如何存储，那么我们如何取出来呢🤔
🌰我们现在要判断是否存储了数字 k
// int[] bits = new int[n/32+1];
public boolean has(int k) {
return (bits[k >> 5] >> (k & 0x1f) & 1) == 1;
}
整个式子意思是判断 bits 中下标为 k/32 的数字从右往左数第 k & 0x1f 位二进制数是否为1
结语
🎉到此我们了解了 BitMap，若要用long做数组也行只是确定位置的地方略有区别而已。
我们发现，假设最大数是十亿，那么我们至少要十亿个 bit 位才行，那么在数据比较稀疏的情况下表现并没有那么的优秀。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/195214.html
