模拟实现位图
目录
位图
概念
编辑
BitSet部分源码
模拟实现
set方法
get方法
reset方法
完整代码
位图的应用场景
位图
概念
所谓位图，就是用一位来存放某种状态，适用于海量数据，整数，数据无重复的场景。通常是用来判断某个数据存不存在的。
概念图：
例如：对于判断一个数是否在数十亿个无符号整数中，如果我们将这数十亿的无符号整数全都加载到内存中，内存是存不下的，那么，如果我们使用每一个比特位来标记一个数是否存在，可以大大的节省空间，内存就存放得下了，因此，遍历这数十亿的数，对这些数使用一个比特位来标记是否存在，就很容易判断出一个数是否在大量的数中是否存在。
BitSet部分源码
BitSet常用的方法有get，set，clear方法。
模拟实现
基本结构
public class MyBitSet {
public byte[] elem;
//记录当前位图当中 存在了多少个有效的数据
public int usedSize;
public MyBitSet() {
this.elem = new byte[1];
}
public MyBitSet(int n) {
this.elem = new byte[n/8+1];
}
}set方法
如何将值存入到位图中？
步骤：
1.判断值是否小于0，如果小于0，则抛异常IndexOutOfBoundsException;
2.计算出值对应的大下标arrayIndex;
3.如果arrayIndex的值大于当前数组的大小，则进行扩容；
4.计算出值对应的小下标bitIndex;
5.让1向左移bitIndex之后的值和数组对应大下标的值进行“或”运算；
6.usedSize进行++。
代码
public void set(int val) {
if(val < 0) {
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8 ;
//扩容
if(arrayIndex > elem.length-1) {
elem = Arrays.copyOf(elem,arrayIndex+1);
}
int bitIndex = val % 8;
elem[arrayIndex] |= (1 << bitIndex);
usedSize++;
}get方法
如何判断值是否在位图中？
步骤：
1.判断值是否小于0，如果小于0，则抛异常IndexOutOfBoundsException;
2.计算出值对应的大下标arrayIndex;
3.计算出值对应的小下标bitIndex;
4.让1向左移bitIndex之后的值和数组对应大下标的值进行“与”运算；
5.判断运算结果是否等于0，如果等于0说明不存在，返回false.
否则说明该值存在于位图中，返回true。
代码
public boolean get(int val) {
if(val < 0) {
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8 ;
int bitIndex = val % 8;
if((elem[arrayIndex] & (1 << bitIndex)) != 0) {
return true;
}
return false;
}reset方法
如何清除掉某个值？
步骤：
1.判断值是否小于0，如果小于0，则抛异常IndexOutOfBoundsException;
2.计算出值对应的大下标arrayIndex;
3.计算出值对应的小下标bitIndex;
4.让1向左移bitIndex之后的值按位取反，得到的结果和数组对应大下标的值进行“与”运算；
5.这样得到的结果就能够清除掉某个值，并且不影响其他值。
代码
public void reSet(int val) {
if(val < 0) {
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8 ;
int bitIndex = val % 8;
elem[arrayIndex] &= ~(1 << bitIndex);
usedSize--;
}完整代码
public class MyBitSet {
public byte[] elem;
//记录当前位图当中 存在了多少个有效的数据
public int usedSize;
public MyBitSet() {
this.elem = new byte[1];
}
public MyBitSet(int n) {
this.elem = new byte[n/8+1];
}
public void set(int val) {
if(val < 0) {
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8 ;
//扩容
if(arrayIndex > elem.length-1) {
elem = Arrays.copyOf(elem,arrayIndex+1);
}
int bitIndex = val % 8;
elem[arrayIndex] |= (1 << bitIndex);
usedSize++;
}
public boolean get(int val) {
if(val < 0) {
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8 ;
int bitIndex = val % 8;
if((elem[arrayIndex] & (1 << bitIndex)) != 0) {
return true;
}
return false;
}
public void reSet(int val) {
if(val < 0) {
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8 ;
int bitIndex = val % 8;
elem[arrayIndex] &= ~(1 << bitIndex);
usedSize--;
}
//当前位图中记录的元素的个数
public int getUsedSize() {
return usedSize;
}
}位图的应用场景
1.集合操作：位图常被用于处理整数值或布尔值的集合，实现高效的集合操作（如并集、交集、差集）以及快速检查元素是否存在于集合中。它通过使用位数组来表示集合中的元素状态，每个元素对应一个位（bit），从而实现高效的空间和时间性能。
2.数据筛选和计数：在数据分析和处理中，位图可以用来快速筛选和计数数据。例如，在处理大量用户行为数据时，可以使用位图来记录用户是否完成了某项操作，或者统计某项操作的发生次数。
3.内存管理：在文件系统和数据库管理中，位图常被用于管理内存或磁盘空间的使用情况。例如，Ext3文件系统中使用位图来管理磁盘空闲块和inode节点的分配状态。
4.高效排序：对于大规模且范围确定的整数排序问题，位图可以提供一种高效的解决方案。通过为每个可能的整数分配一个位来表示其是否出现，可以快速收集出现过的整数并进行排序。5.布隆过滤器（Bloom Filter）：布隆过滤器是一种基于位图的概率型数据结构，用于快速判断一个元素是否属于某个集合。虽然它存在误判率，但因其空间效率和查询速度而广受欢迎。
6.路由表存储：在大型分布式系统中，如腾讯的QQ号路由服务器，可以使用位图来存储路由表。通过为每个可能的QQ号分配固定数量的位来表示其对应的服务器号，可以实现高效的路由查询。
