场景

最近碰到有一个功能，需要在程序中缓存几十万个节点更新状态，一个节点要么已经更新，要么等待更新，这就是一种二进制状态，在巨量的节点数量下，除了存取状态，「当中也需要批量地对某一批节点置为已更新或者未更新」，那么我们可以怎么在 Javascript 语言设计这个存储的数据结构以及提供相应的 api 呢？

一般性存储方案

我知道有同学马上就能想到数组、字符串等等方案。在数组中直接存入所有的二进制数据自然能够实现此类功能，又或者将他们都转成字符串。

window.A_arr = Array.from({ length: 500000 }).fill(0)
// or
window.A_string = Array.from({ length: 500000 }).fill(0).join('')

但你也能看出来，直接用数组或者字符串可以存储，但过于灵活，不会利用到二进制有关的特性，无法提高存取的效率，对于他们俩产生的数据表现，我们可以用 chrome 控制台 memory 中打一个 Heap snapshot 并找到他们占用的内存。

位数组存储方案

而如何利用二进制的特性来存储呢，很容易想到的是二进制的位运算在硬件底层上直接执行的，所以效率极高，利用这一特性，我们可以结合位运算，将大量的二进制数字压缩为其他高进制，通过位运算进行取值和改值。

这里我们选择使用 Uint8Array，直白点来讲它就是一个只能存 0 到 0xFF 的整数数组，同时在内存空间上它的每个值也刚好可以填满 1 个 bit，使得内存空间存储效率拉满，所以它又称之为 「Bit Array」 —— 位数组，也因此在存储二进制数值上，它的存储效率和执行效率也高于其他同等的 TypedArray，如 Uint16Array、Uint32Array。

位数组的存取

我们可以这样存储我们的 500000 个二进制值——

window.A_bitArray = new Uint8Array(Math.ceil(500000 / 8))

如果在浏览器执行上述的声明代码，我们可以看到他的内存占用在十万级别的数据上要「远低于」一般数组和字符串。

在取某个位的值时，则需要将值取出来后做位运算

// 在普通数组中
function getValueFromArray (arr: number[], index:number) {
    return arr[index]
}

// 在位数组中
function getValueFromBitArray(arr: Uint8Array, index:number) {
    const byteIndex = ~~(index / 8)
    const bitIndex = index % 8
    return arr[byteIndex] >> bitIndex & 1
}

位数组的修改

对于单个值的修改，位数组同样通过位运算进行存储——

function setValueOfBitArray(arr:Uint8Array, index: number, value: 0 | 1) {
    const byteIndex = ~~(index / 8);
    const bitIndex = index % 8;
    if (value === 1) {
        arr[byteIndex] |= 1 << bitIndex
    } else {
        arr[byteIndex] &= 1 ~(1 << bitIndex)
    }
}

❝这里解释一下位运算的过程，

byteIndex 表示这个索引的值存储于数组的第几个值；

bitIndex 则表示这个值是 bit 当中的第几位；

要将这一位置为 1 ，那就是让原数与这个位为 1 其他位为 0 的数进行「或运算」即可，这样不会影响其他位的值。

同理，要置为 0 则是与原数与这个位为 0 其他位为 1 的数进行「与运算」即可（当然首位不能为0，需要补1）。

❞

「单个」二进制值的修改看起来比直接修改数组值和字符串值要麻烦上许多，同时性能上相比也不上不下。

但在「批量范围性」的修改中，位数组的执行效率跟它的存储效率一样高，对于普通数组或者类数组，我们需要遍历需要修改的数组项然后一个个地修改，而位数组可以一次性修改一整个 bit 存储的二进制值，也就说明位数组在这个场景下的执行效率要比一般类数组的执行效率要高 8 倍左右。

function setValueOfArrayByArea (arr: number[], start: number, end:number, value:number) {
    for (let i = start; i < end; i ++) {
        arr[i] = value
    }
}

function setValueOfBitArrayByArea (arr: Uint8Array, start: number, end:number, value:0 | 1) {
    const startByte = ~~(start / 8);
    const endByte = ~~(end / 8);
    const startBit = start % 8;
    const endBit = end % 8;
    const startMask = 0xff >> startBit;
    const endMask = 0xff << (7 - endBit);
    
    if (startByte === endByte) {
            const mask = startMask & endMask;
            if (value === 0) {
                    arr[startByte] &= ~mask;
            } else {
                    arr[startByte] |= mask;
            }
            return this;
    }

    if (value === 0) {
            arr[startByte] &= ~startMask;
            arr[endByte] &= ~endMask;
            for (let i = startByte + 1; i < endByte; i++) {
                    this.array[i] = 0;
            }
    } else {
            arr[startByte] |= startMask;
            arr[endByte] |= endMask;
            for (let i = startByte + 1; i < endByte; i++) {
                    this.array[i] = 0xff;
            }
    }
}

封装一下

为了便于使用位数组存取二进制数据，我们可以对其进行封装。

export class BitArray {
    protected array: Uint8Array;
    protected _size: number;
    get size() {
        return this._size;
    }
    set size(value: number) {
        this._size = value;
        const newArray = new Uint8Array(Math.ceil(value / 8));
        newArray.set(this.array);
        this.array = newArray;
    }
    
    constructor(size: number) {
        this._size = size;
        this.array = new Uint8Array(Math.ceil(size / 8)); 
    }
    
    setValue(index: number, value: 0 | 1) {
        const { array } = this
        const byteIndex = ~~(index / 8);
        const bitIndex = index % 8;
        if (value === 1) {
            array[byteIndex] |= 1 << bitIndex;
        } else {
            array[byteIndex] &= ~(1 << bitIndex);
        }
        return this;
    }
    setValueByArea(start: number, end: number, value: 0 | 1) {
        const { array } = this
        const startByte = ~~(start / 8);
        const endByte = ~~(end / 8);
        const startBit = start % 8;
        const endBit = end % 8;
        const startMask = 0xff >> startBit;
        const endMask = 0xff << (7 - endBit);

        if (startByte === endByte) {
                const mask = startMask & endMask;
                if (value === 0) {
                        array[startByte] &= ~mask;
                } else {
                        array[startByte] |= mask;
                }
                return this;
        }
        if (value === 0) {
                array[startByte] &= ~startMask;
                for (let i = startByte + 1; i < endByte; i++) {
                        array[i] = 0;
                }
                array[endByte] &= ~endMask;
        } else {
                array[startByte] |= startMask;
                for (let i = startByte + 1; i < endByte; i++) {
                        array[i] = 0xff;
                }
                array[endByte] |= endMask;
        }
        return this;
    }
    getValue(index: number) {
            const byteIndex = Math.floor(index / 8);
            const bitIndex = index % 8;
            return (this.array[byteIndex] >> bitIndex) & 1; 
    }
}

位数组的业务场景

在常规的前端业务数据处理当中，我们几乎不需要位数组这样的功能存在，但在图像处理领域包括 3D 渲染，二进制数组可以很高效率的存储每个节点甚至是像素点的某种开关状态，例如透明通道、光照计算、模型面的可见性等等。

这些数据基本都能达到百万级别，倘若用一般性数组来存储这类数据将会使整个程序的内存占用