🔎概念
用某一位表示存储的状态
位图的适用场景
- 海量数据
- 数据为自然数(≥ 0)
- 数据不重复
举个栗子🌰
以 byte[] 数组为例
byte[] 数组中元素的大小是 1 Byte(字节), 8 bit(比特位)
存在数组 int[] arr = {1, 4, 12, 20}
满足数据为自然数(≥ 0), 数据不重复
存入 byte[] 数组
- 对于 byte[] bytes
- bytes[0] 用于存储 0 ~ 7 之间的数字
- bytes[1] 用于存储 8 ~ 15 之间的数字
- bytes[2] 用于存储 16 ~ 23 之间的数字
- …
- 用某一位表示存储的状态
- 用 bytes[0] 的第 0 ~ 7 位(比特位)表示是否存储 0 ~ 7 之间的数字
- 用 bytes[1] 的第 0 ~ 7 位(比特位)表示是否存储 8 ~ 15 之间的数字
- 用 bytes[2] 的第 0 ~ 7 位(比特位)表示是否存储 16 ~ 23 之间的数字
- …
🔎位图的模拟实现
此处利用 byte[] 数组模拟实现位图
定义两个变量
public byte[] bytes表示位图
public int usedSize表示位图中的元素个数
无参的构造方法🍭
public ExBitSet() { this.bytes = new byte[1]; }
带参的构造方法🍭
n 表示位数
8 表示byte[] 数组的大小为1 Byte(字节), 8 bit(比特位)
n / 8 +1
(0 ~ 7 之间的数字 / 8 = 0, 但所需的大小为 1 字节 → 存储 0 ~ 7 之间的数字)
public ExBitSet(int n) { this.bytes = new byte[n / 8 + 1]; }
set()
set(int val)
将某一位设置为 1
(将 val 存储至位图中)
- val 表示传入的数字, 在 byte[] 数组中根据该数字的值修改其对应下标的位
- arrayIndex 表示 bytes 数组的下标
- bitIndex 表示对应的位
public void set(int val) { if(val < 0) { throw new ValException("val 值小于0"); } int arrayIndex = val / 8; if(arrayIndex > bytes.length) { bytes = Arrays.copyOf(bytes, arrayIndex + 1); } int bitIndex = val % 8; bytes[arrayIndex] |= 1 << bitIndex; usedSize++; }
举个栗子🌰
val = 12
arrayIndex = 12 / 8 = 1(对应 byte[] 数组的下标为1 → bytes[1])
bitIndex = 12 % 8 = 4(对应的位数为4 → 下标为1, 第 4 位表示 1 * 8 + 4 = 12)
bytes[arrayIndex] |= 1 << bitIndex
将 bytes[1] 的第 4 位设置为 1, 表示存储了数字 12
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
get()
get(int val)
判断当前位是否为 1
(判断 val 在位图中是否存在)
- val 表示传入的数字, 在 byte[] 数组中根据该数字的值修改其对应下标的位
- arrayIndex 表示 bytes 数字的下标
- bitIndex 表示对应的位
public boolean get(int val) { if(val < 0) { throw new ValException("val 值小于0"); } int arrayIndex = val / 8; if(arrayIndex > bytes.length) { bytes = Arrays.copyOf(bytes, arrayIndex + 1); } int bitIndex = val % 8; return (bytes[arrayIndex] & 1 << bitIndex) != 0; }
举个栗子🌰
val = 12
arrayIndex = 12 / 8 = 1(对应 byte[] 数组的下标为1 → bytes[1])
bitIndex = 12 % 8 = 4(对应的位数为4 → 下标为1, 第 4 位表示 1 * 8 + 4 = 12)
bytes[arrayIndex] &= 1 << bitIndex
若存储了数字12, 则 bytes[1] 的第 4 位为 1
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
reSet()
reSet(int val)
将某一位设置为 0
(将 val 从位图中删除)
- val 表示传入的数字, 在 byte[] 数组中根据该数字的值修改其对应下标的位
- arrayIndex 表示 bytes 数字的下标
- bitIndex 表示对应的位
public void reSet(int val) { if(val < 0) { throw new ValException("val 值小于0"); } int arrayIndex = val / 8; if(arrayIndex > bytes.length) { bytes = Arrays.copyOf(bytes, arrayIndex + 1); } int bitIndex = val % 8; bytes[arrayIndex] &= ~(1 << bitIndex); usedSize--; }
举个栗子🌰
val = 12
arrayIndex = 12 / 8 = 1(对应 byte[] 数组的下标为1 → bytes[1])
bitIndex = 12 % 8 = 4(对应的位数为4 → 下标为1, 第 4 位表示 1 * 8 + 4 = 12)
bytes[arrayIndex] &= ~(1 << bitIndex)
将 bytes[1] 的第 4 位设置为 0, 表示删除了数字 12
~0 = 1
~1 = 0
getUsedSize()
getUsedSize()
获取位图中的元素个数
public int getUsedSize() { return usedSize; }
完整代码
这里的异常是自定义的
也可以根据自己的需要进行相关的修改
import java.util.Arrays; public class ExBitSet { public byte[] bytes; // 记录当前位图中存在多少个有效数据 public int usedSize; public ExBitSet() { this.bytes = new byte[1]; } /** * n → 需要多少位 */ public ExBitSet(int n) { this.bytes = new byte[n / 8 + 1]; } /** * 设置某一位为 1 */ public void set(int val) { if(val < 0) { throw new ValException("val 值小于0"); } int arrayIndex = val / 8; if(arrayIndex > bytes.length) { bytes = Arrays.copyOf(bytes, arrayIndex + 1); } int bitIndex = val % 8; bytes[arrayIndex] |= 1 << bitIndex; usedSize++; } /** * 判断当前位是否为 1 */ public boolean get(int val) { if(val < 0) { throw new ValException("val 值小于0"); } if(arrayIndex > bytes.length) { bytes = Arrays.copyOf(bytes, arrayIndex + 1); } int arrayIndex = val / 8; int bitIndex = val % 8; return (bytes[arrayIndex] & 1 << bitIndex) != 0; } /** * 将对应位置变为0 */ public void reSet(int val) { if(val < 0) { throw new ValException("val 值小于0"); } if(arrayIndex > bytes.length) { bytes = Arrays.copyOf(bytes, arrayIndex + 1); } int arrayIndex = val / 8; int bitIndex = val % 8; bytes[arrayIndex] &= ~(1 << bitIndex); usedSize--; } // 当前位图中的元素个数 public int getUsedSize() { return usedSize; } }
🔎利用位图进行排序
根据 byte[] 数组的下标计算数据所在的范围区间
根据当前位是否为 1 判断是否存储了该数字
- bytes[0] 表示 0 ~ 7 之间的数字(0 * 8 + 对应的位)
- bytes[1] 表示 8 ~ 15 之间的数字(1 * 8 + 对应的位)
- bytes[2] 表示 16 ~ 23 之间的数字(2 * 8 + 对应的位)
public static void main(String[] args) { ExBitSet bitSet = new ExBitSet(); int n = bitSet.bytes.length; for(int i = 0; i < n; i++) { int x = bitSet.bytes[i]; for(int j = 0; x != 0 && j < 8; j++) { if((x & 1 << j) != 0) { System.out.println(i * 8 + j); } } } }
举个栗子🌰
假设当前位图中存储的元素为 1, 12, 4, 0, 23, 5
- int n = 3
- bytes[0] != 0, bytes[1] != 0, bytes[2] != 0
- i 表示对应的下标, i * 8 表示对应的取值范围
- j 表示对应的位数, i * 8 + j 表示具体的数值
🔎结尾
创作不易,如果对您有帮助,希望您能点个免费的赞👍
大家有什么不太理解的，可以私信或者评论区留言，一起加油
