BitMap
面试题海量数据处理经常出现BitMap，所以记一下笔记
1. BitMap
BitMap也称为位图，其原理和布隆过滤器类似，其基本原理都是使用位数组及其下标来表示某些元素是否存在，其在处理大量数据的排序、查询、去重，以及在用户群做交集和并集运算的时候也有极大的便利
假如我们要将 {5,6,1,10} 进行排序，利用位图思想的话：（这里并不是真实原理，是个假设）
- 遍历找出或预计最大元素值
- 然后创建最大元素值大小的位数组（比如上例就创建大小为10的位数组）
- 最后遍历数据，每遇到一个元素则在对应的位数组置1
其时间复杂度为O(N)，比一般的排序算法都快
且空间利用率高，在普通情况下10亿个整数占用空间3.8G，而位图占用120MB左右
2. 实际操作
我们使用 byte[] arr = new byte[max]数组来模拟位数组：
- 一个 byte占用8bit，那么可以表示 0~7 的数
- byte[10] 占用80bit，那么可以表示 0~79的数
- 根据上两条，那么 8这个数是在 byte[1] 里面存放的
那么我们可以总结出：若最大数为N，那么需要创建数组大小为 byte[ N / 8+ 1]
找出某数 n对应的整型数组下标：n / 8 == n >> 3
在具体整型下标中，找出的位下标：n % 8 == n & 0x07
综合起来的Java实现就是
public class BitMap {
private byte[] data;
private int capacity;
public BitMap(int cacapacity){ // 还可以做个扩容机制？
this.capacity = cacapacity;
data = new byte[ (cacapacity >> 3) + 1];
}
public void add(int num){
int arrayIndex = num >> 3; // /8
int position = num & 0x07; // %8
// 左移表示将1向左移动几位，加上小端存储，即可占用对应位了
data[arrayIndex] |= 1 << position;
}
public boolean contain(int num){
int arrayIndex = num >> 3;
int position = num & 0x07;
return ( data[arrayIndex] & (1 << position) ) != 0;
}
public void clear(int num){
int arrayIndex = num >> 3;
int position = num & 0x07;
data[arrayIndex] &= ~(1 << position);
}
public static void main(String[] args) {
BitMap bitmap = new BitMap(100);
bitmap.add(10);
System.out.println("是否存在10:"+ bitmap.contain(10));
bitmap.clear(10);
System.out.println("是否存在10:" + bitmap.contain(10));
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录