BitSet

🔎概念
🔎位图的模拟实现
- set()
- get()
- reSet()
- getUsedSize()
- 完整代码
🔎利用位图进行排序
🔎结尾

🔎概念

位图
用某一位表示存储的状态

位图的适用场景

海量数据
数据为自然数(≥ 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);}}}
}