官方微信：动力节点Java学院 关注官方微信免费领取java视频教程

官方微博：动力节点

Java位向量的实现原理与巧妙应用

1、博文介绍

本篇博文将会介绍几本的位运算含义、位向量介绍、BitSet实现原理、Java位向量的应用、拓展介绍Bloom Filter等。

2、位运算介绍

1) 位运算符

java中位运算操作符主要包括：

2）位运算简单应用

// 1. 获得int型最大值；2147483647的十六进制为0x7FFFFFFF,其中最高位为符号位System.out.println((1 << 31) - 1);// 2147483647， 由于优先级关系，括号不可省略System.out.println(~(1 << 31));// 2147483647// 2. 获得int型最小值System.out.println(1 << 31);

3）应用 - 小游戏中状态的判断，如斗地主判断四人是否处于准备状态

充分利用一个位有两种状态，可以代表开闭、是否准备好等二状态场景中，即便是多状态也可以用多位来实现，比如在迷宫问题中，可以用00 01 10 11 来代表四个方向。如果正常的判断四人是否处于准备状态，可定义四个变量，但是如果用位运算，则一个byte类型变量的低4位就足够了。

在提高运行速度的同时，也对程序的可读性造成了影响，上面只是举例位运算可以应用在类似的场景中，具体适不适合根据项目背景而定。可以使用设计模式来解决，底层用位实现，封装到上层之后只公开方法。

实现代码：

/**

3、Java位向量介绍-BitSet

位向量，也叫位图，是一个我们经常可以用到的数据结构，在使用小空间来处理大量数据方面有着得天独厚的优势；位向量的定义就是一串由0.1组成的序列。

Java中对位向量的实现类时Java.util.BitSet;C++标准库中也有相应的实现，原理都是一样的； BitSet源码也很简单，很容易看懂 ，如果读者在对位向量有一定的了解后，可以通过读源码来了解BitSet的具体实现。

一个bit上有两个值，正好可以用来判断某些是非状态的场景，在针对大数据场景下判断存在性，BitSet是相比其他数据结构比如HashMap更好的选择，在Java中，位向量是用一个叫words的long型数组实现的，一个long型变量有64位，可以保存64个数字；比如我们有[2,8,6,10,15]这5个数要保存，一般存储需要 5*4 = 20字节的存储空间。但是如果我们使用Java.util.BitSet进行存储则可以节省很多的空间只需要一个long型数字就够了。BitSet只面向数字只面向数字使用，对于string类型的数据，可以通过hashcode值来使用BitSet。

由于，1 << 64, 1<<128, 1<<192 这些数字的结果都为1，BitSet内部，long[]数组的大小由BitSet接收的最大数字决定，这个数组将数字分段表示[0,63],[64,127],[128,191]...。即long[0]用来存储[0,63]这个范围的数字的“存在性”，long[1]用来存储[64,127]，依次轮推，这样就避免了位运算导致的冲突。原理如下：

|------------|----------|----------|----------|----------| |

Java的BitSet每次申请空间，申请64位，即一个long型变量所占的位数；

BitSet源码实现-缩小版：

package java.util;import java.io.*;import java.nio.ByteBuffer;import java.nio.ByteOrder;import java.nio.LongBuffer;public class BitSet implements Cloneable, java.io.Serializable {

4、BitSet的应用

1）《编程珠玑》中的排序问题

问题重述：一个最多包含n个正整数的文件，每个数都小于n，其中n=107，并且没有重复。最多有1MB内存可用。要求用最快方式将它们排序并按升序输出。

解决方案就是：把文件一次读入，出现的数字在位向量对应索引处中标注为1，读取完文件之后，将位向量从低位向高位依次将为1的索引输出即可。

相关代码：

package cn.liuning.test;import java.util.BitSet;public class MainTest {

2）使用BitSet做String类型数据的存在性校验

一种方案：

BitSet bitSet = new BitSet(Integer.MAX_VALUE);//hashcode的值域 //0x7FFFFFFF (int类型的最大值，第一位是符号位，可用Integer.MAX_VALUE代替)String url = "http://baidu.com/a";

使用上述算法需要解决Java中hashcode存在冲突的问题。即不同的String可能得到的hashcode是一样的（即使不重写hashcode方法）。如何解决？调整hashcode生成算法：我们可以对一个String使用多个hashcode算法，生成多个hashcode，然后在同一个BitSet进行多次“着色”，在判断存在性时，只有所有的着色位为true时，才判定成功。

String url = "http://baidu.com/a";

其实我们能够看出，这种方式降低了误判的概率。但是如果BitSet中存储了较多的数字，那么互相覆盖着色，最终数据冲突的可能性会逐渐增加，最终仍然有一定概率的判断失误。所以在hashcode算法的个数与实际String的个数之间有一个权衡，我们建议:

“hashcode算法个数 * String字符串的个数” < Integer.MAX_VALUE * 0.8；

另一种解决方案：多个BitSet并行保存

改良1)中的实现方式，我们仍然使用多个hashcode生成算法，但是每个算法生成的值在不同的BitSet中着色，这样可以保持每个BitSet的稀疏度(降低冲突的几率)。在实际结果上，比1)的误判率更低，但是它需要额外的占用更多的内存，毕竟每个BitSet都需要占用内存。这种方式，通常是缩小hashcode的值域，避免内存过度消耗。

BitSet bitSet1 = new BitSet(Integer.MAX_VALUE);//127MBitSet bitSet2 = new BitSet(Integer.MAX_VALUE);

最后：我们要考虑是否有必要完全避免误判，可能有时候这种误判也是我们需要的结果。如果做到100%的正确判断率，在原理上说BitSet是无法做的， BitSet能够保证“如果判定结果为false，那么数据一定是不存在；但是如果结果为true，可能数据存在 ，也可能不存在(冲突覆盖)”,即“false == YES，true == Maybe”。有人提出将冲突的数据保存在类似于BTree的额外数据结构中，事实上这种方式增加了设计的复杂度，而且最终仍然没有良好的解决内存占用较大的问题。

3） BloomFilter(布隆姆过滤器)

BloomFilter 的设计思想和BitSet有较大的相似性，目的也一致，它的核心思想也是使用多个Hash算法在一个“位图”结构上着色，最终提高“存在性”判断的效率。请参见Guava BloomFilter。如下为代码样例：

Charset charset = Charset.forName("utf-8");