【JAVA进化论】LV4-4：位图

发表于 分类于 阅读次数： 本文字数： 650 阅读时长 ≈ 2 分钟

一、用法

先来看看java里对位图数据结构的实现类：BitSet

用法如下：

代码块1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
    BitSet bitSet = new BitSet();
    bitSet.set(78); //只传一个参数代表将该位置上的数值置为1（true）
    bitSet.set(79, 82); //79、80、81位为true，即[79, 82)
    bitSet.set(83, true); //83位置为1（true）
    System.out.println(bitSet.get(78)); //true
    System.out.println(bitSet.get(79)); //true
    System.out.println(bitSet.get(80)); //true
    System.out.println(bitSet.get(81)); //true
    System.out.println(bitSet.get(82)); //82位为false
    System.out.println(bitSet.get(83)); //true
 
    bitSet.set(83, false); //再次将第83位上的值置为0（即false）
    System.out.println(bitSet.get(83)); //第83位上的值为0（false）
}

打印结果如下：

代码块2
1
2
3
4
5
6
7
true
true
true
true
false
true
false

很懵逼吧？位图到底是什么？这些”位“代表什么意思？记录true或false有什么用？继续往下看。

二、位图

图1

其实位图就是个数组，所谓的”位“就是指数组里每个数值元素的二进制位，像不像我们对开关字段的处理方式？标记只有存在或者不存在（对应二进制的0和1），这样就可以做到用一个long型的数字就可以产生出64个标记信息，非常适合数据量庞大而判断状态少的应用场景，比如判断一个词语是否是屏蔽词，首先屏蔽词状态只有两种：命中or不命中，但是屏蔽词可能是个非常庞大的集合，如果一个个拿来比较，效率完全保证不了，那么就可以利用这个数据结构来解决这类问题，可以首先把所有的屏蔽词放到一个位图结构里，如果有相同的词语，只需要简单的两部运算就可以拿到是否命中结果，构建这个位图结构的过程如下：

图2

通过上图，屏蔽词位图结构就构建好了，如果有个词语需要判定是否命中屏蔽词，只需要让这个词语通过上面的哈希算法计算出哈希值，然后找到对应的数组下标，通过位运算算出其所在位置，将该位置的值取出，如果是0，则认为没有命中，1则认为命中。

抽象到代码块1的例子，其实就是将传入的index，与long型的64位做除法，计算出自己属于数组的哪个下标值，这样就找到了自己在数组中的位置，然后再将下标值跟64取模，计算出将该十进制的值的第几位标记为1或0.