SakuraTears的博客

越努力越幸运

Java BitSet类简介及应用

发表于 分类于 阅读次数： Valine：
本文字数： 10k 阅读时长 ≈ 9 分钟

前言

面试过程中我们或许被问过如下问题：如何快速判断某个数字在1亿数据中有没有出现过？

这都要用到我们今天要说的BitSet，我们下面一起来看下吧。

正文

BitSet简介

BitSet类实现了一个根据需要增长的位向量。BitSet的每个组成部分都有一个布尔值。BitSet的位由非负整数索引。可以检查、设置或清除单个索引位。

一个BitSet对象可以通过逻辑与、逻辑或、逻辑异或操作来修改另一个BitSet对象的内容。

默认情况下，集合中的所有位初始值为false。

每个BitSet都有一个当前大小，即该BitSet当前使用的空间位数。

需要注意其大小与BitSet的实现有关，因此它可能随实现而改变。BitSet的长度与BitSet的逻辑长度有关，并且与实现无关。

除非另有说明，否则将null传递给BitSet中的任何方法都会导致NullPointerException。

如果没有外部同步，BitSet是线程不安全的。

基本原理

BitSet是位操作的对象，值只有 0 或 1 （false和true），其内部维护了一个long数组，初始只有一个long，所以BitSet最小的长度是64，当随着存储的元素越来越多，BitSet内部会动态扩充，最终内部是由N个long来存储。

如下图：

upload successful

我们每个数字对应一个bit位，其值0 或 1表示该位置数字存不存在，这样一个long（8bit）可以表示64个数据，1G空间（1024 x 1024 x 1024 x 8 = 8589934592 bit）可以表示 85亿数据的相关信息。

同时位操作也是较快的，这也就是为什么BitSet在处理特定海量数据高效且节省空间的原因。

相关方法

Java中的BitSet为我们提供了一些实用的操作方法，我们来看下。

构造方法部分

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
public class BitSet implements Cloneable, java.io.Serializable {
    //部分代码略
    private static final int ADDRESS_BITS_PER_WORD = 6;
    private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
    private long[] words;
    private transient int wordsInUse = 0;

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

    public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;
    }

    public BitSet(int nbits) {
        // nbits can't be negative; size 0 is OK
        if (nbits < 0)
            throw new NegativeArraySizeException("nbits < 0: " + nbits);

        initWords(nbits);
        sizeIsSticky = true;
    }

    private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
    }

//部分代码略
}

上述代码可以看到BitSet底层为long数组，wordIndex方法用来计算数据在数组的位置。

initWords方法，初始化long数组，最少为1个long数组。

wordsInUse 是检查当前的long数组中，实际使用的long的个数，即long[wordsInUse-1]是当前最后一个存储有有效bit的long。这个值是用于保存BitSet有效大小的。

内部方法部分

下面再来看下四个比较重要的内部方法：ensureCapacity、expandTo、checkInvariants、recalculateWordsInUse

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
private void ensureCapacity(int wordsRequired) {
    if (words.length < wordsRequired) {
        // Allocate larger of doubled size or required size
        int request = Math.max(2 * words.length, wordsRequired);
        words = Arrays.copyOf(words, request);
        sizeIsSticky = false;
    }
}
private void expandTo(int wordIndex) {
    int wordsRequired = wordIndex+1;
    if (wordsInUse < wordsRequired) {
        ensureCapacity(wordsRequired);
        wordsInUse = wordsRequired;
    }
}
private void checkInvariants() {
    assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
    assert(wordsInUse >= 0 && wordsInUse <= words.length);
    assert(wordsInUse == words.length || words[wordsInUse] == 0);
}
private void recalculateWordsInUse() {
    // Traverse the bitset until a used word is found
    int i;
    for (i = wordsInUse-1; i >= 0; i--)
        if (words[i] != 0)
            break;

    wordsInUse = i+1; // The new logical size
}

checkInvariants函数检查内部状态，校验wordsInUse等参数是否合法。在每一个public方法最后都会被调用。

recalculateWordsInUse会计算wordsInUse的位置。

expandTo和ensureCapacity为扩容方法，扩容条件是wordsInUse < wordIndex+1，扩容大小为 2 * words.length和wordIndex+1中的最大值。

主要方法部分

再来看下BitSet常用的几个主要方法:set，clear，get，flip。

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

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);

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

    checkInvariants();
}

可以看到set方法设置某一指定位，操作主要有两步，找到对应的long，获取mask并与指定的位进行 按位或（OR） 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
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();
}

clear方法清除某一指定位，操作也基本分两步，找到对应的long，获取mask并与指定的位进行 按位与（AND） 操作。

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

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);

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

    recalculateWordsInUse();
    checkInvariants();
}

flip方法翻转某一指定位，操作也基本分两步，找到对应的long，获取mask并与指定的位进行 异或（XOR） 操作。

1
2
3
4
5
6
7
8
9
10
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);
}

get方法获取某一指定位值，同样的两步走，这里的位操作是按位与（AND）。可以看到，如果指定的bit不存在的话，返回的是false，即没有设置。

主要方法处理上述部分外，还有重载的一些方法。

如对某个位置设置具体的布尔值，设置某一区间的值等。

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

这儿就不过多介绍了。

两个BitSet相关操作方法

主要有以下四个方法

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
62
63
64
65
66
67
68
69
70
public void and(BitSet set) {
    if (this == set)
        return;

    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();
}

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();
}

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();
}

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];

    recalculateWordsInUse();
    checkInvariants();
}

and(BitSet set)方法相当于对当前BitSet和参数BitSet执行按位与（AND）操作。

or(BitSet set)方法相当于对当前BitSet和参数BitSet执行按位或（OR）操作。

xor(BitSet set)方法相当于对当前BitSet和参数BitSet执行异或（XOR）操作。

andNot(BitSet set)方法相当于对参数BitSet取反，然后和当前BitSet执行按位与（AND）操作。

相关应用

了解了BitSet相关方法和原理后，我们来看下BitSet的一些应用场景。

布隆过滤器

BitSet一个典型的应用就是布隆过滤器，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如1%, 这个散列表就只能容纳 m / 100 个元素。显然这就不叫空间效率了（Space-efficient）。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

相关代码如下：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
public class BloomFilter {

    /**
     * 一个长度为10 亿的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;

    /**
     * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};

    /**
     * 相当于构建 8 个不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];

    /**
     * 初始化布隆过滤器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);

    /**
     * 添加数据
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //计算 hash 值并修改 bitmap 中相应位置为 true
                bitset.set(f.hash(value), true);
            }
        }
    }

    /**
     * 判断相应元素是否存在
     * @param value 需要判断的元素
     * @return 结果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一个 hash 函数返回 false 则跳出循环
            if (!ret) {
                break;
            }
        }
        return ret;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }

        // 添加1亿数据
        for (int i = 0; i < 100000000; i++) {
            add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);

        System.out.println(contains(id));   // true
        System.out.println("" + contains("234567890"));  //false
    }
}

class HashFunction {

    private int size;
    private int seed;

    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        return (size - 1) & result;
    }
}

可以看到布隆过滤器可以解决我们上面所说的问题：如何快速判断某个数字在1亿数据中有没有出现过？

除了这个问题，布隆过滤器也可以解决邮箱黑名单等一系列问题。

使用BitSet，还可以对有限范围的大量正整数进行快速排序，我们来看一下。

使用BitSet排序

需要注意的是，使用BitSet进行排序时，需要数据为正整数，且需要知道数据范围（最大值范围），并且在排序时，如果有相同元素，BitSet需要变种，进行额外处理。

其实也是比较好理解的，BitSet可以表示1 ~ +∞ 范围的数据，知道数据范围，我们将数组数据放到BitSet对应的位置上，然后遍历拿到true的数据即可。

相同元素会被覆盖，因此普通的BitSet是无法统计数据数量的，也就是如果数组存在相同元素，BitSet需要变化一下才能适应对此的排序。

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
62
63
64
65
66
67
68
69
70
public class BitSetSort {
    /**
     * 初始化数组
     *
     * @param size
     * @param max
     * @return
     */
    private static int[] generateNumber(int size, int max) {
        int[] nums = new int[size];
        for (int i = 0; i < size; i++) {
            //[0,max)
            nums[i] = RandomUtils.nextInt(max);
        }
        return nums;
    }

    /**
     * 使用BitSet进行排序
     *
     * @param nums 待排序数组
     * @param max  最大值范围，不需要知道最大值，这个值不小于最大值即可
     * @return
     */
    public static void bitSetSort(int[] nums, int max) {
        int len = nums.length;

        //辅助map，用于记录相同元素次数
        Map<Integer, Integer> map = new HashMap<>();

        BitSet bitSet = new BitSet(max);
        bitSet.set(0, max, false);
        //更改数据位为true
        for (int i = 0; i < len; i++) {
            int pos = nums[i];
            if (bitSet.get(pos)) {
                Integer value = map.get(pos);
                value = value == null ? 0 : value;
                value++;
                map.put(pos, value);
            } else {
                bitSet.set(pos, true);
            }

        }
        //遍历bitSet
        int k = 0;
        for (int i = 0; i < max; i++) {
            if (bitSet.get(i)) {
                nums[k] = i;
                k++;
                Integer value = map.get(i);
                if (value != null) {
                    for (int s = 0; s < value; s++) {
                        nums[k] = i;
                        k++;
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] nums = generateNumber(100000000, 10000000);
        long start1 = System.currentTimeMillis();
        bitSetSort(nums, 10);
        long end1 = System.currentTimeMillis();
        System.out.println("BitSet排序耗时--> " + (end1-start1) +"ms");
    }
}

可以看到我们这儿借助HashMap来存储相同元素个数，如果待排序的数据不重复，则不引入HashMap即可，同时可以达到很高的效率。

我们也可以使用1bit来记录该位置是否有多个相同元素，有的话再去Map里获取，这样也能提高不少效率，其也属于BitSet的变种。

总结

通过本篇文章我们了解了BitSet的原理及一些使用场景，在特定的情况下，使用BitSet或许是个不错的选择。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

您的支持就是我创作的动力！

欢迎关注我的其它发布渠道