By IceMimosa

更新日期:

文章目录
  1. Java BitSet源码分析
    1. 1. 构造方法
    2. 2. set方式
    3. 3. clear方法
    4. 4. get方法
    5. 5. size和length方法
    6. 6. and/or/xor方法
    7. 7. andNot方法

[TOC]

Java BitSet源码分析

1. 构造方法

1
2
public BitSet() 
// 或者 public BitSet(int nbits)

两者的代码基本相似，主要调用了 initWords方法：

1
2
3
4
5
6
7
8
9
10
11
12
// nbits默认传进来的是 1 << 6，即64
private void initWords(int nbits) {
    words = new long[wordIndex(nbits-1) + 1];
}

// words是long类型的数组，所以每个元素64位，即一个元素可以存放64个数字
// 这里相当于确定存放数字的位置。
// 比如我要放200个数字（即nbits=200），最后初始化的long数组为 `new long[4]`，即需要4个long元素才能放下200个数字。
private static int wordIndex(int bitIndex) {
	// bitIndex >> 6 即 bitIndex/64
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

下面说下几个重要的方法。

2. set方式

1
2
3
4
5
6
7
8
// 设置一个数字
public void set(int bitIndex)
// 设置或清除一个数字
public void set(int bitIndex, boolean value) 
// 设置一个数字范围
public void set(int fromIndex, int toIndex) 
// 设置或清除一个数字范围
public void set(int fromIndex, int toIndex, boolean value)
  • 基本的set方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    // 确定存放的下标
    int wordIndex = wordIndex(bitIndex);
    // 是否需要扩容，这里跟ArrayList类似，就不多说了
    expandTo(wordIndex);

    // 分析见下面
    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    // 检查一些不变量，可以不用管
    checkInvariants();
}

words[wordIndex] |= (1L << bitIndex); 这里不是很好理解，首先得清楚一个基本知识点：

1
2
int类型左移n位，如果n大于等于32，需要用(n%32)作为移动的位数。
int类型左移n位，如果n大于等于64，需要用(n%64)作为移动的位数。

即上述代码变成如下：

1
2
3
4
int transderBits = bitIndex % 64;
words[wordIndex] |= (1L << transderBits);

// 这样就很清晰了，然后做或运算，将对应的位数置为1。

3. clear方法

1
2
3
4
5
6
// 清除一个数字
public void clear(int bitIndex) 
// 清除一个数字范围
public void clear(int fromIndex, int toIndex)
// 清除所有
public void clear()

主要代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void clear(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    // 确定元素下标
    int wordIndex = wordIndex(bitIndex);
    if (wordIndex >= wordsInUse)
        return;

    // 同理，自行意淫一把。。
    words[wordIndex] &= ~(1L << bitIndex);

    // 重新计算使用的元素，可以不管
    recalculateWordsInUse();
    checkInvariants();
}

4. get方法

1
2
3
4
// 查看数组是否存在
public boolean get(int bitIndex)
// 查询一个数字范围
public BitSet get(int fromIndex, int toIndex)
1
2
3
4
5
6
7
8
9
10
11
// 看着不难，还行
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);
}

5. size和length方法

  • size()
1
2
3
4
5
public int size() {
    return words.length * BITS_PER_WORD; // 常数是64
}

// 返回存放数字的数量，64的倍数
  • length()
1
2
3
4
5
6
7
8
9
public int length() {
    if (wordsInUse == 0)
        return 0;

    return BITS_PER_WORD * (wordsInUse - 1) +
        (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
}

// 返回存放数字的逻辑大小

6. and/or/xor方法

  • and() 交集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void and(BitSet set) {
    if (this == set)
        return;

    // 将多余的元素置为0
    while (wordsInUse > set.wordsInUse)
        words[--wordsInUse] = 0;

    // Perform logical AND on words in common
    for (int i = 0; i < wordsInUse; i++)
        words[i] &= set.words[i]; // 与运算，取出交集

    recalculateWordsInUse();
    checkInvariants();
}
  • or() 并集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void or(BitSet set) {
    if (this == set)
        return;

    int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

    if (wordsInUse < set.wordsInUse) {
        ensureCapacity(set.wordsInUse);
        wordsInUse = set.wordsInUse;
    }

    // Perform logical OR on words in common
    for (int i = 0; i < wordsInCommon; i++)
        words[i] |= set.words[i];

    // Copy any remaining words
    if (wordsInCommon < set.wordsInUse)
        System.arraycopy(set.words, wordsInCommon,
                         words, wordsInCommon,
                         wordsInUse - wordsInCommon);

    // recalculateWordsInUse() is unnecessary
    checkInvariants();
}
  • xor() 异或
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void xor(BitSet set) {
    int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

    if (wordsInUse < set.wordsInUse) {
        ensureCapacity(set.wordsInUse);
        wordsInUse = set.wordsInUse;
    }

    // Perform logical XOR on words in common
    for (int i = 0; i < wordsInCommon; i++)
        words[i] ^= set.words[i];

    // Copy any remaining words
    if (wordsInCommon < set.wordsInUse)
        System.arraycopy(set.words, wordsInCommon,
                         words, wordsInCommon,
                         set.wordsInUse - wordsInCommon);

    recalculateWordsInUse();
    checkInvariants();
}

7. andNot方法

1
2
3
4
5
6
7
8
public void andNot(BitSet set) {
    // Perform logical (a & !b) on words in common
    for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
        words[i] &= ~set.words[i]; // 把相同的置为0

    recalculateWordsInUse();
    checkInvariants();
}

其他方法可以自行查看下源码，也基本大同小异。由于普通BitSet含有自身的缺陷，后面会介绍下RoaringBitmap

参考：

文章目录
  1. Java BitSet源码分析
    1. 1. 构造方法
    2. 2. set方式
    3. 3. clear方法
    4. 4. get方法
    5. 5. size和length方法
    6. 6. and/or/xor方法
    7. 7. andNot方法