BitMap JS实现以及重复数检查

DongYuanxin

2021-08-08

位图（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 排序算法：

/*
 * @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 位是：

那么思路大体就是：

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

位图（bitmap）介绍

应用 1: 位图实现 BitSort

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

参考