什么是位向量/位图?
位向量/位图是一个数据结构,可以利用小空间存储大量数据。
通俗概括一下:位向量是一个二进制数,我们要存储的数字是几,就让位向量的第几位为 1。这样就能使用一个数,存储大量的数了。
位向量有什么用?
看了上面的概括,大家可能不太明白这种数据结构到底有什么用。这里我举一个非常常见的场景:进程 pid 的分配。
如果不使用位向量,你想一想要怎么保存那么多进程的 pid?需要用一个 int 数组来保存吗?这样势必会造成大量的空间浪费,我们平时使用的电脑、手机等设备可能不在乎这点空间,但是在一些嵌入式设备中,这点空间就弥足珍贵了。
接下来让我们一起看看用位向量怎么实现 pid 分配的逻辑。
pid 分配
代码实现
直接上代码:
需要注意的是,这个程序只是模拟了 pid 的分配逻辑,并没有兼顾实际的业务逻辑(比如 0~299 的 pid 保留给 daemon 进程)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| static int last = -1;
static int pids;
static int usedPid = 0;
static int MAX_PID = 10;
static int allocPid() { if (usedPid == MAX_PID) { throw new RuntimeException("No pid resources!"); } int pid = last; do { pid += 1; if (pid >= MAX_PID) { pid = 0; } } while ((1 << pid) == ((1 << pid) & pids)); pids = pids | (1 << pid); last = pid; usedPid++; return pid; }
|
从代码中可以看到,我们使用了三个变量来存储,分别是 last
、pids
和 usedPid
。
pids
就是我们用来保存使用中的 pid 的位向量
last
用来保存上一次分配的 pid,主要为了保持 pid 的递增状态
usedPid
是用来记录已经使用了多少 pid 了,用来判断是否还有剩余 pid 可供使用。
整个代码的流程就是:
- 先判断还有没有剩余的 pid 资源
- pid 在上次分配的基础上进行自增,如果到了最大值就从头开始重新递增
- 检查自增后的 pid 是否已经被使用了
- 直到寻找到一个可用的 pid
- 返回此 pid
测试验证
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| public static void main(String[] args) { System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); pids = pids & ~(1 << 3); usedPid -= 1; System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); pids = pids & ~(1 << 6); usedPid -= 1; System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); System.out.println(allocPid()); }
|
在测试代码中我们一直在调用 allocPid
分配 pid,因为我们没有写释放的函数,所以就手动释放掉了 pid 3
和 6
。
输出:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| 0 1 2 3 4 5 6 7 8 9 3 6 Exception in thread "main" java.lang.RuntimeException: No pid resources! at com.android.signapk.Main.allocPid(Main.java:33) at com.android.signapk.Main.main(Main.java:25)
Process finished with exit code 1
|
从输出可以看出:pid 一直在递增,回收了 3
和 6
后 pid 也没有中断递增。递增了一圈后开始第二轮,重新使用了 3
和 6
。最后实在没有 pid 资源了,抛出了 No pid resources
异常。
最后
这次的代码可以在 Gist 上找到:https://gist.github.com/T-Oner/2f6d634b111dc2d50c528d34f0e8b7a5