基于位图法的高效存储结构
位图法，适用连续范围区间。预先分配空间，用每一个bit来表达数字存在与否。
普通的方式既要保存数字本身，还要关联一个boolean变量，而位图法则将bit位置作为数字，bit值作为状态，极大的缩减了内存。
典型问题
- N个未排序的整数，在线性时间内，求这N个整数在数轴上相邻两个数之间的最大差值
底层实现
底层存储由一个long数组组成
BitSet.java
一个long提供64位，即能表达64个位置，那么实际上一个数字除以64就能找到word的索引
BitSet.java1
2
3
| private static int wordIndex(int bitIndex) {
return bitIndex >> ADDRESS_BITS_PER_WORD;
}
|
初始化能容纳n个bit位的数组,bit索引0~n-1,可以复用上面方法算出需要多少word
BitSet.java@1651
2
3
| private void initWords(int nbits) {
words = new long[wordIndex(nbits-1) + 1];
}
|
操作
向set中加入一个元素相当于把相应位置1
java中的左移会自动取模，因此直接左移即可
BitSet.java1
2
3
4
5
6
7
8
9
10
| public void set(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
int wordIndex = wordIndex(bitIndex);
expandTo(wordIndex);
words[wordIndex] |= (1L << bitIndex);
checkInvariants();
}
|
同理从set中删除一个元素相当于把相应位置0
BitSet.java1
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();
}
|
寻找下一个元素
关键是造出111…000这样的mask。可以用全1值左移获得
BitSet.java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int nextSetBit(int fromIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
checkInvariants();
int u = wordIndex(fromIndex);
if (u >= wordsInUse)
return -1;
long word = words[u] & (WORD_MASK << fromIndex);
while (true) {
if (word != 0)
return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
if (++u == wordsInUse)
return -1;
word = words[u];
}
}
|
同理可以寻找前一个元素
关键是造出000…111这样的mask。用全1值无符号右移。
右移一个负数值-n相当于右移(64-n)%64
BitSet.java@7841
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public int previousSetBit(int fromIndex) {
if (fromIndex < 0) {
if (fromIndex == -1)
return -1;
throw new IndexOutOfBoundsException(
"fromIndex < -1: " + fromIndex);
}
checkInvariants();
int u = wordIndex(fromIndex);
if (u >= wordsInUse)
return length() - 1;
long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
while (true) {
if (word != 0)
return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
if (u-- == 0)
return -1;
word = words[u];
}
}
|
容量
size方法返回BitSet的物理大小
BitSet.java1
2
3
| public int size() {
return words.length * BITS_PER_WORD;
}
|
length方法返回BitSet的逻辑大小,即当前的最大值
BitSet.java1
2
3
4
5
6
7
| public int length() {
if (wordsInUse == 0)
return 0;
return BITS_PER_WORD * (wordsInUse - 1) +
(BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
}
|
扩容
当前数组大小的2倍和目标大小的最大值，即如果2倍不够就直接扩展到目标大小
BitSet.java1
2
3
4
5
6
7
8
| private void ensureCapacity(int wordsRequired) {
if (words.length < wordsRequired) {
int request = Math.max(2 * words.length, wordsRequired);
words = Arrays.copyOf(words, request);
sizeIsSticky = false;
}
}
|
