原理
BitSet是位操作的对象，值只有0或1即false和true，内部维护了一个long数组，初始只有一个long，所以BitSet最小的size是64，当随着存储的元素越来越多，BitSet内部会动态扩充，最终内部是由N个long来存储，这些针对操作都是透明的。
用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用用的时候既可根据某一个是否为0表示，此数是否出现过。 一个1G的空间，有 8102410241024=8.5810^9bit，也就是可以表示85亿个不同的数。 注意：在没有外部同步的情况下，多个线程操作一个BitSet是不安全的。例子
比如有一堆数字，需要存储，source=[3,5,6,9]
用int就需要4*4个字节。 java.util.BitSet可以存true/false。 如果用java.util.BitSet，则会少很多，其原理是： 1，先找出数据中最大值maxvalue=9 2，声明一个BitSet bs,它的size是maxvalue+1=10 3，遍历数据source，bs[source[i]]设置成true. 最后的值是： (0为false;1为true) bs [0,0,0,1,0,1,1,0,0,1] 3, 5,6, 9 这样一个本来要int型需要占4字节共32位的数字现在只用了1位！ 比例32:1 这样就省下了很大空间 通常用在数据统计、分析的领域。初始化逻辑
初始化大小 默认就一个long元素，逻辑如下：
private final static int ADDRESS_BITS_PER_WORD = 6;private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; //用来开辟bit位空间private long[] words;//当前long数组的大小private transient int wordsInUse = 0;public BitSet() { initWords(BITS_PER_WORD); sizeIsSticky = false;}private void initWords(int nbits) { words = new long[wordIndex(nbits-1) + 1];}//bitIndex除去64(bitIndex >> 6 )得到会落到long数组的index；private static int wordIndex(int bitIndex) { return bitIndex >> ADDRESS_BITS_PER_WORD;} BitSet的基本运算
public class BitUtils { /** * 获取运算数指定位置的值 * 例如： 0000 1011 获取其第 0 位的值为 1, 第 2 位 的值为 0 * * @param source * 需要运算的数 * @param pos * 指定位置 (0<=pos<=7) * @return 指定位置的值(0 or 1) */ public static byte getBitValue(byte source, int pos) { return (byte) ((source >> pos) & 1); } /** * 将运算数指定位置的值置为指定值 * 例: 0000 1011 需要更新为 0000 1111, 即第 2 位的值需要置为 1 * * @param source * 需要运算的数 * @param pos * 指定位置 (0<=pos<=7) * @param value * 只能取值为 0, 或 1, 所有大于0的值作为1处理, 所有小于0的值作为0处理 * * @return 运算后的结果数 */ public static byte setBitValue(byte source, int pos, byte value) { byte mask = (byte) (1 << pos); if (value > 0) { source |= mask; } else { source &= (~mask); } return source; } /** * 将运算数指定位置取反值 * 例： 0000 1011 指定第 3 位取反, 结果为 0000 0011; 指定第2位取反, 结果为 0000 1111 * * @param source * * @param pos * 指定位置 (0<=pos<=7) * * @return 运算后的结果数 */ public static byte reverseBitValue(byte source, int pos) { byte mask = (byte) (1 << pos); return (byte) (source ^ mask); } /** * 检查运算数的指定位置是否为1 * * @param source * 需要运算的数 * @param pos * 指定位置 (0<=pos<=7) * @return true 表示指定位置值为1, false 表示指定位置值为 0 */ public static boolean checkBitValue(byte source, int pos) { source = (byte) (source >>> pos); return (source & 1) == 1; } /** * 入口函数做测试 * * @param args */ public static void main(String[] args) { // 取十进制 11 (二级制 0000 1011) 为例子 byte source = 11; // 取第2位值并输出, 结果应为 0000 1011 for (byte i = 7; i >= 0; i--) { System.out.printf("%d ", getBitValue(source, i)); } // 将第6位置为1并输出 , 结果为 75 (0100 1011) System.out.println("\n" + setBitValue(source, 6, (byte) 1)); // 将第6位取反并输出, 结果应为75(0100 1011) System.out.println(reverseBitValue(source, 6)); // 检查第6位是否为1，结果应为false System.out.println(checkBitValue(source, 6)); // 输出为1的位, 结果应为 0 1 3 for (byte i = 0; i < 8; i++) { if (checkBitValue(source, i)) { System.out.printf("%d ", i); } } }} BitSet的应用一——排序
/** * 问题重述：一个最多包含n个正整数的文件，每个数都小于n，其中n=107，并且没有重复。 * 最多有1MB内存可用。要求用最快方式将它们排序并按升序输出。 */import java.util.BitSet;import java.util.Scanner;/** * 解决思路 * 将文件中的数读入，把数字对应的bit位设置为1，最后，将bit位为1的按序输出。 */public class SortByBit { public static void main(String args[]) { //输入数字 int n; Scanner sc = new Scanner(System.in); n = sc.nextInt(); BitSet bitSet = new BitSet(); for (int i = n; i>0;i--) { bitSet.set(sc.nextInt()); } //输出 for (int i = bitSet.size(); i>0; i--) { if (bitSet.get(i)) System.out.print(i + " "); } }}//输出31 20 220 2 1 应用二——字符串判重
BitSet bitSet = new BitSet(Integer.MAX_VALUE);//hashcode的值域 //0x7FFFFFFF (int类型的最大值，第一位是符号位，可用Integer.MAX_VALUE代替)String url = "http://baidu.com/a"; int hashcode = url.hashCode() & 0x7FFFFFFF; bitSet.set(hashcode); System.out.println(bitSet.cardinality()); //状态为true的个数System.out.println(bitSet.get(hashcode)); //检测存在性 bitSet.clear(hashcode); //清除状态
为什么使用long，不用int？
JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑，因为BitSet提供and和or这种操作，需要对两个BitSet中的所有bit位做and或者or，实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低，所以Java选择使用long数组作为BitSet的内部存储结构。
从数据在栈上的存储来说，使用long和byte基本是没有什么差别的，除了编译器强制地址对齐的时候，使用byte最多会浪费7个字节(强制按照8的倍数做地址对其)，另外从内存读数组元素的时候，也是没有什么区别的，因为汇编指令有对不同长度数据的mov指令。所以说，JDK选择使用long数组作为BitSet的内部存储结构的根本原因就是在and和or的时候减少循环次数，提高性能。
Java1.8-BitSet源码分析
https://www.jianshu.com/p/91d75bf588b8