Fork me on GitHub

Java BitSet类简介及应用

前言

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

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

正文

BitSet简介

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

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

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

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

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

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

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

基本原理

BitSet是位操作的对象,值只有 01falsetrue),其内部维护了一个long数组,初始只有一个long,所以BitSet最小的长度是64,当随着存储的元素越来越多,BitSet内部会动态扩充,最终内部是由Nlong来存储。

如下图:

upload successful

我们每个数字对应一个bit位,其值01表示该位置数字存不存在,这样一个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有效大小的。

内部方法部分

下面再来看下四个比较重要的内部方法:ensureCapacityexpandTocheckInvariantsrecalculateWordsInUse

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的位置。

expandToensureCapacity为扩容方法,扩容条件是wordsInUse < wordIndex+1,扩容大小为 2 * words.lengthwordIndex+1中的最大值。

主要方法部分

再来看下BitSet常用的几个主要方法:setcleargetflip

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或许是个不错的选择。




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

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%