BitMap原理

BitMap原理是借助bit数组，通过把一个元素映射到bit数组上的相应位置，设置bit的值来表示有无。

比如：java中开辟一个byte大小空间的值，相当于8位大小的空间，那么现在有1到8 之间的几个数字，就可以按数值大小映射到这个bit数组上。通过bit位上的值，我们就可以判断某个数是否出现过；

BitMap尤其在判断某个元素是否存在，或者统计出现的元素都很高效并且节省空间； 通常我们申请一块空间，然后把我们的目标元素映射到这块空间的bit位上，JDK为我们提供了一个便捷的工具类BitSet;

JDK BitSet

原理：BitSet内部申请的空间没有直接通过byte数组，而是通过long数组来存储，一个long相当于8个byte,代表64位空间，可以存储64个元素的有无； JDK解释用long数组来做存粹存粹是为了性能考虑；可能是考虑到缓存行的原因，防止伪共享；

BitSets are packed into arrays of "words." Currently a word is a long, which consists of 64 bits, requiring 6 address bits. The choice of word size is determined purely by performance concerns.

初始化逻辑

初始化大小 默认就一个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];}private static int wordIndex(int bitIndex) {    return bitIndex >> ADDRESS_BITS_PER_WORD;}

Set逻辑

BitSet.set(int bitIndex) 设置index标识位；原理如下： public void set(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

//bitIndex除去64(bitIndex >> 6 )得到会落到long数组的index；    int wordIndex = wordIndex(bitIndex);    //如果当然数组大小不够，进行二倍扩容；    expandTo(wordIndex);    // 对1移动bitIndex 效果是除位，只保留64位的有效值，如 1<<65 ,    // 1<<129 效果是一样的；落到同一word的bitIndex除位的个数是相同的，余下的位求和，放到word里；    words[wordIndex] |= (1L << bitIndex); // Restores invariants    checkInvariants();}

扩容

//long数组不够，进行二倍扩容； 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;    }}

Get逻辑

BitSet.get(int bitIndex) 判断该index是否已加入，原理和get相似，只不过最后一步是取并；

public boolean get(int bitIndex) {    if (bitIndex < 0)        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);    checkInvariants();    int wordIndex = wordIndex(bitIndex);    //set的区别是 这里是取并；    return (wordIndex < wordsInUse)        && ((words[wordIndex] & (1L << bitIndex)) != 0);}

Cardinality逻辑

BitSet.cardinality()判断当前BitSet设置了多少标识位；

public int cardinality() {    int sum = 0;    for (int i = 0; i < wordsInUse; i++)    	//计算一个Long中用了几个bit;        sum += Long.bitCount(words[i]);    return sum;}

BitSet间的运算

and(BitSet set) or(BitSet set) 比如and 可以用在统计几天用户是否连续登陆等，or可用在最近这几天登陆过的用户运算；