BitMap JS实现以及重复数检查

位图(bitmap)介绍

什么是位图?

用 1 个(或多个)bit 位,来表示某个值。

位图的好处?

1、使用 bit 位,相较于使用原生数据结构,占用内存更少。

例如,对于 0、6 这 2 个数字,一个 int 类型的数字,是 4 个字节,也就是 2*8=16 个 bit 位。如果用 bitmap 表示呢?只需要申请一个字节,一个字节有 8 个 bit 位,初始全部置 0,从最低位到最高位分别对应数字 0-7,如果数字存在,那么 bit 位置 1,所以 0、6 对应的字节是:0100 0001

2、更容易进行集合运算。例如要求 2 个集合的交集,一个是{0, 6, 7},一个是{2, 4, 6}。那么只需要将他们用 bitmap 表示,然后将 bit 位进行&运算,并且将得到的 bitmap 转换为对应数字即可。

位图的缺点?

一般来说,假设要表示的数据集合的容量是n,那么申请的 bit 位是10*n。对于范围过大的数字,单纯用 bitmap 反而需要申请更多空间,可以使用“布隆过滤器”。

应用 1: 位图实现 BitSort

使用 js 实现了 bitmap,并且实现 bitsort 排序算法:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
* @Author: dongyuanxin
* @Date: 2020-12-27 16:26:18
* @Github: https://github.com/dongyuanxin/blog
* @Blog: https://0x98k.com/
* @Description: js位图
*/

const BYTE_SIZE = 8; // 1byte = 8bit

/**
* 位图的实现
*/
class BitMap {
constructor(bytes = 0) {
this.buf = Buffer.alloc(bytes); // 申请bytes个字节大小
}

/**
* 作用:将第position个数对应的字节位,设置为1
* 思路:最简单的8个bit可以表示[0, 7]共8个数字,分别是:
* 0000 0001(表示0)
* 0000 0010(表示1)
* ......
*/
set(position) {
let index = Math.floor(position / BYTE_SIZE);
let offset = position % BYTE_SIZE;
// 对应的字节的bit位置位0
this.buf[index] = this.buf[index] | (0x01 << offset);
}
}

function bitSort(nums = []) {
// step1: 计算需要的字节数
const byteLengh = Math.ceil(nums.length / BYTE_SIZE);
// step2: 生成对应字节数的位图,并将出现的数字的bit位标识为1
const bitmap = new BitMap(byteLength);
nums.forEach((num) => bitmap.set(num));
// step3: 遍历所有的字节,找到为1的所有bit位对应的所有数字
for (let i = 0; i < byteLength; ++i) {
let mask = 0x01; // 掩码
let j = 0; // 标识当前字节的bit位
do {
// step3.1: 找到为1的bit位,将其转换为对应的数字
if ((bitmap.buf[i] & mask) === mask) {
const num = i * BYTE_SIZE + j;
process.stdout.write(num.toString() + " ");
}
// step3.2: 移动掩码,继续查找下一个bit位
mask = mask << 1;
++j;
} while (j < BYTE_SIZE);
}

process.stdout.write("\r\n");
}

// 测试代码:bitsort排序
// 输出:2 3 5 6 8 9 10 12 14
bitSort([3, 5, 2, 10, 6, 12, 8, 14, 9]);

应用 2: 找到 2.5 亿个整数中不重复的数

假设:内存不足以容纳这 2.5 亿个整数。直接申请数组或者使用哈希表肯定不可行。

借助 bitmap 的思路,可以用 bit 位来表示数组的出现情况。根据要求,有 3 种情况:

  • 没出现过
  • 出现过 1 次
  • 出现过多次

由于是 3 种情况,所以需要 2 个 bit 位,3 种情况对应 bit 位是:

  • 00
  • 01
  • 11

那么思路大体就是:

  1. 依次扫描整数
  2. 扭转整数对应的 2 个 bit 位的状态,00 变成 01,01 变成 11,11 不需要变
  3. 重新遍历所有的 bit 位,找到 bit 位为 01 对应的数字即可

参考