数据结构_BitMap
2025-01-22 08:19:30    3.3k 字    #数据结构
This post is also available in English and alternative languages.

BitMap 是一种数据结构, BitMap 用 bit 位来标记某个元素对应的 Value，而 Key 即是该元素; 由于采用了bit为单位来存储数据，因此可以大大节省存储空间(重点)。


1. 什么是BitMap？

计算机中，最小单位是bit，一个bit值只有两个：1、0

我们平时所使用的类型也都是bit构成的，例如 byte字节，一个字节等于8个bit

类型字节(byte)bit
int4 byte4 * 8
short2 byte2 * 8
long8 byte8 * 8
byte1 byte1 * 8
float4 byte4 * 8
double8 byte8 * 8
boolean1 byte1 * 8
char2 byte2 * 8

2. BitMap如何表示

在BitMap中如何表示一个数？

按照上面说的，一个bit位只有两个值：1(存在) 和 0(不存在)


表示{1,2,4,6}这四个数，如以下表示

bit值01010110
下标(位)76543210

下标的每一位，表示一位数，0不存在、1存在。（根据’下标’，取出bit值为1的，即为要表示的数字）


计算机内存分配的最小单位是字节，也就是8位，如果要表示{12,13,15}怎么办呢？

这就需要再另一个byte上表示,类似二维数组，第一组数组表示：0 ~ 7 ， 第二组数组表示：8 ~ 15

tmp[0]bit值01010110
tmp[0]下标(位)76543210
tmp[1]bit值10110000
tmp[1]下标(位)15141312111098

一个int值占32位(4*8)

那申请 int类型 tmp数组个数为：‘int tmp[1+N/32]’，N为int类型存储的最大值

1
2
3
4
5
6
7
8
9
比如要存储的最大值是50(0~50)，那就是 1+(50/32) = 2.56
考虑到会有小数，所以直接+1补偿，将小数去除，所以就是 两个tmp数组
tmp[0]:表示0~31
tmp[1]:表示32~63

如果存储最大值是80(0~80)，那就是 1+(80/32) = 3.5，去除小数就是3
tmp[0]:表示0~31
tmp[1]:表示32~63
tmp[2]:表示64~95

这样一来，如果给定一个M值，想知道在bit中的位置，可以这样算，M/32得到tmp数组下标，M%32得到数组中具体的下标位置。

1
2
3
4
5
6
7
比如，M值40，想知道这个M值，在bit中的位置，这样计算

40/32 = 1.25，那就在tmp[1]中

40 % 32 = 8.0

如下表格
tmp[0]0***00000000***0000
tmp[0]31***15141312111098***3210
tmp[1]0***000100000000
tmp[1]63***434241403938373635343332

2.1. BitMap 添加

如果想将数字5放入下面这个byte中，应该怎么做？

bit值01010110
下标(位)76543210

首先我们计算下5应该所属的位置

1
2
3
4
5
5 / 32 = 0.156，那就是在tmp[0]中

5 % 32 = 5.0

也就是说，在tmp[0]的第5个位置，将1向左移动5位，然后'按位或'

如下，两个表格’按位或’

one-byte tmp[0]bit值01010110
one-byte tmp[0]下标(位)76543210
two-byte tmp[0]bit值00100000
two-byte tmp[0]下标(位)76543210

得到下面表格

new tmp[0]bit值01110110
new tmp[0]下标(位)76543210

换算成二进制形式

one-byte | two-byte = new-byte

one-byte0101 0110
two-byte0010 0000
new-byte0111 0110

转换成十进制形式

one-byte2+4+16+64=86
two-byte32
new-byte2+4+16+32+64=118

相当于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
86 | 32 = 118

86 | (1<<5) = 118

tmp[0] = tmp[0] | (1<<5)

结合上面M公式，就是：

86 + (5/8) | (1<<(5%8))

86 代表现在的值

'(5/8) | (1<<(5%8))' 代表 新增的值

'(5/8)' 计算在哪个数组

'(1<<(5%8))' 计算在数组中下标的位置

再简化下，得出公式

1
2
3
p + (i/8)|(1<<(i%8))

p表示现在的值，i表示需要插入的值

也就是说，想要插入一个数，将1左移至代表该数字那一位的下标位置，然后与原数进行’按位或’操作。


2.2. BitMap 清除

假设我们要将6移除，该怎么操作？

下面两个表格，进行’按位与’操作。

one-byte tmp[0]bit值01010110
one-byte tmp[0]下标(位)76543210
two-byte tmp[0]bit值10111111
two-byte tmp[0]下标(位)76543210

得到以下

new tmp[0]bit值00010110
new tmp[0]下标(位)76543210

可以看到，只需将下标为6的bit值，至为0即可。

也就是，1左移6位，到达代表这个数字的位，然后’按位取反’，然后与原数’按位与’，即可清除。


3. BitMap Demo

jdk中对BitMap数据结构进行了实现：java.util.BitSet

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void testBitMap() {
    int[] array = new int[]{1, 3, 5, 7, 234, 2, 0};

    BitSet bitSet = new BitSet(array.length);

    for (int i = 0; i < array.length; i++) {
        bitSet.set(array[i], true);
    }
    System.out.println(bitSet);
    System.out.println(bitSet.size());
    System.out.println(bitSet.get(3));
    System.out.println(bitSet.get(9));
}

3.1. BitSet的实现

在jdk的java.util.BitSet中，封装了BitMap的实现

BitSet底层用一个long型数组来存储元素。

1
2
3
4
5
6
7
8
private final static int ADDRESS_BITS_PER_WORD = 6;

private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

/**
    * The internal field corresponding to the serialField "bits".
    */
private long[] words;

使用long型数组存储元素，说明BitSet容量最小是8*8(64)bit，可以存储64个bit元素；而且BitSet的大小是long型(64)的整数倍。


3.1.1. BitSet构造函数

BitSet有三个构造方法，都会创建一个’位集合’，所有位默认都是false

空构造方法，初始化长度为1的long型数组

1
2
3
4
public BitSet() {
    initWords(BITS_PER_WORD);
    sizeIsSticky = false;
}

看下有参构造函数的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private BitSet(long[] words) {
    this.words = words;
    this.wordsInUse = words.length;
    checkInvariants();
}

public BitSet(int nbits) {
    // nbits can't be negative; size 0 is OK（可以初始化长度为0的数组）
    if (nbits < 0)
        throw new NegativeArraySizeException("nbits < 0: " + nbits);

    initWords(nbits);
    sizeIsSticky = true;
}

long型参数的构造方法，入参即为words数组长度。

int型参数的构造方法，入参需要计算出words数组长度

举个栗子

1
2
3
传参为1，通过计算，构建的long型数组，words[]长度为1，因为只有一个long元素，size为64

传参为64，通过计算，构建的long型数组，words[]长度为2，这样就有了两个long元素，size为128

是否指定words数组的大小

1
2
3
4
5
/**
    * Whether the size of "words" is user-specified.  If so, we assume
    * the user knows what he's doing and try harder to preserve it.
    */
private transient boolean sizeIsSticky = false;

在有参构造方法中，使用initWords方法，初始化数组长度；

initWords方法，会把nbits这个数减1然后右移6位再加1（wordIndex(nbits-1) + 1），如此计算出long型数组初始长度。

1
2
3
4
5
6
7
8
9
10
private void initWords(int nbits) {
    words = new long[wordIndex(nbits-1) + 1];
}

/**
    * Given a bit index, return word index containing it.
    */
private static int wordIndex(int bitIndex) {
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

例如

1
2
3
4
5
6
7
8
initWords方法
如果是输入的28，那么words的长度是1;
如果是输入的2^6 = 64，那么words的长度是1;
如果是输入的2^6+1 = 65，那么words的长度是2;
如果是输入的(2^6)*2 = 128，那么words的长度是2;
如果是输入的(2^6)*2+1 = 129，那么words的长度是3;
如果是输入的(2^6)*3 = 192，那么words的长度是3;
如果是输入的(2^6)*3+1 = 193，那么words的长度是4;

BitSet用long类型，因为一个long占64bit，所以每个long表示64个元素。

也就是说，数组中words中的第一个long(words[0])表示0～63，第二个long(words[1])表示64～127，第三个long(words[2])表示128～191，依次类推…

wordIndex方法是很重要，它用来定位某个数在words数组中的位置。


3.1.2. ADDRESS_BITS_PER_WORD 为啥是6？

在 wordIndex() 方法中，计算value所属数组下标，为啥 ADDRESS_BITS_PER_WORD 是6呢？

1
2
3
private static int wordIndex(int bitIndex) {
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

上面提过，BitSet底层存储的容器是 long类型数组，一个long元素，占64bit；

还记得之前的公式吗？定位一个值，再哪个bit中时，需要先 M/32 得到数组下标，再 M%32 得到数组内下标；

因为是long型，所以，定位数组下标需要 M/64。

代码层面使用 >> ‘右移位’ 来代替除法（因为位运算效率比除法高）

long型占64bit，64刚好是2的6次幂，所以 ADDRESS_BITS_PER_WORD 是 6。


3.1.3. BitSet 添加

看下Demo

1
2
3
4
5
6
7
8
9
10
public static void testBitMap() {
    int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 8};

    BitSet bitSet = new BitSet(array.length);

    for (int i = 0; i < array.length; i++) {
        bitSet.set(array[i], true);
    }
    System.out.println(bitSet);
}

BitSet.set()方法，有两个入参

bitIndex 即要存储的值；

value 是一个boolean值，为true则存储；为false则删除

1
2
3
4
5
6
public void set(int bitIndex, boolean value) {
    if (value)
        set(bitIndex);
    else
        clear(bitIndex);
}

wordIndex 方法，定位 值 应该存储在words数组哪个下标的long中，即wordIndex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    
    //计算bitIndex在words数组中的下标
    int wordIndex = wordIndex(bitIndex);
    
    //检查是否需要扩容
    expandTo(wordIndex);
    
    //计算bitIndex在words[wordIndex]中的位置
    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    checkInvariants();
}

'words[wordIndex] |= (1L << bitIndex)'这一步，是计算值在数组内的位置。

1
2
3
4
5
这一步转换下，即

words[wordIndex] |= (1L << bitIndex);

words[wordIndex] = words[wordIndex] | (1L << bitIndex)

是不是和上面BitMap中的例子很像

运行上面的demo，在 words[wordIndex] |= (1L << bitIndex); 这一行，debug观察下

words下标十进制二进制
0210
06110
0141110
03011110
062111110
01261111110
025411111110
0510111111110

转换成二进制表格，即

bit值0000000111111110
下标(位)63…131211109876543210

很明显吧，下标 1 ~ 8 的bit值，都是1，即我们存储的值


3.1.4. BitSet 查询

demo

1
2
3
4
5
6
7
8
9
10
11
public static void testBitMap() {
    int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 8};

    BitSet bitSet = new BitSet(array.length);

    for (int i = 0; i < array.length; i++) {
        bitSet.set(array[i], true);
    }
    System.out.println(bitSet.get(3));
    System.out.println(bitSet.get(9));
}

看下源码

1
2
3
4
5
6
7
8
9
public boolean get(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    checkInvariants();

    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0);
}

wordIndex方法上面讲过了，即 定位 bitIndex 在words数组中的位置。

这里重点是：(words[wordIndex] & (1L << bitIndex))

结合demo，拆分开看下

1
2
3
4
5
6
7
8
9
10
bitIndex = 3;

第一步：
    计算出 wordIndex = 0;
    words[wordIndex] 代表bitIndex在words数组的下标位置。
    
第二步：
    计算3在bit中的位置
    1L << 3 = 8 ; 通过左移位，计算3在bit中的位置，
    8转换成二进制则是：1000

转换成表格，即

bit值0000000111111110
下标(位)63…131211109876543210
bit值0000000000001000
下标(位)63…131211109876543210

再看最后一步，将上面两步 ‘按位与’

1
(words[wordIndex] & (1L << bitIndex))

转换成表格即：

bit值0000000000001000
下标(位)63…131211109876543210

最后判断下标3的bit值，是否等于0，以此判断3，是否存在。


4. BitSet 实例

有1千万个随机数，随机数的范围在1到1亿之间；现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来？

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
/**
    * 有1千万个随机数，随机数的范围在1到1亿之间。
    * 现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来？
    * （数据量太大，换成一百万和一千万）
    */
public static void testBitSet() {

    Random random = new Random();

    //数据准备（一百万随机数，范围在一千万内）
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < 1000000; i++) {
        int randomResult = random.nextInt(10000000);
        list.add(randomResult);
    }
    System.out.println("list:" + list);

    //数据存入bitset
    BitSet bitSet = new BitSet(1000000);
    for (int i = 0; i < list.size(); i++) {
        bitSet.set(list.get(i), true);
    }
    System.out.println("bitSet:" + bitSet);

    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < 10000000; i++) {
        //循环一千万，从bitSet中取反即可
        if (!bitSet.get(i)) {
            result.add(i);
        }
    }
    System.out.println(result);
}

4.1. 缺点

BitMap的JDK实现，有一个缺点，数据稀疏问题。

当数据量少,且跨度极大也就是稀疏的时候,原生的位图不太适合

例如，我只存储两个数字，1 和 9999999，它们需要的空间会非常大。

这里记录下数据稀疏解决方案：EWAHCompressedBitmap、Roaring BitMap 算法

还有一个数据碰撞的问题

进度问题，暂不深究


5. Reference