分享自我的微信訂閱號“猿in”，可以搜索關(guān)注。

Bitset基礎(chǔ)

介紹

bitset(bitmap)也就是位圖，由于可以用非常緊湊的格式來表示給定范圍的連續(xù)數(shù)據(jù)而經(jīng)常出現(xiàn)在各種算法設(shè)計(jì)中。

類實(shí)現(xiàn)了一個按需增長的位向量。位 set的每個組件都有一個boolean值。用非負(fù)的整數(shù)將BitSet的位編入索引。可以對每個編入索引的位進(jìn)行測試、設(shè)置或者清除。通過邏輯與、邏輯或和邏輯異或操作，可以使用一個BitSet修改另一個BitSet的內(nèi)容。

默認(rèn)情況下，set 中所有位的初始值都是false。
每個位 set 都有一個當(dāng)前大小，也就是該位 set 當(dāng)前所用空間的位數(shù)。注意，這個大小與位 set 的實(shí)現(xiàn)有關(guān)，所以它可能隨實(shí)現(xiàn)的不同而更改。位 set 的長度與位 set 的邏輯長度有關(guān)，并且是與實(shí)現(xiàn)無關(guān)而定義的。

除非另行說明，否則將 null 參數(shù)傳遞給BitSet中的任何方法都將導(dǎo)致NullPointerException。

在沒有外部同步的情況下，多個線程操作一個BitSet是不安全的

下面的圖來自c++庫中bitset的一張圖。

image

基本原理

BitSet是位操作的對象，值只有0或1即false和true，內(nèi)部維護(hù)了一個long數(shù)組，初始只有一個long，所以BitSet最小的size是64，當(dāng)隨著存儲的元素越來越多，BitSet內(nèi)部會動態(tài)擴(kuò)充，最終內(nèi)部是由N個long來存儲，這些針對操作都是透明的。

用1位來表示一個數(shù)據(jù)是否出現(xiàn)過，0為沒有出現(xiàn)過，1表示出現(xiàn)過。使用用的時候既可根據(jù)某一個是否為0表示，此數(shù)是否出現(xiàn)過。

一個1G的空間，有 8102410241024=8.5810^9bit，也就是可以表示85億個不同的數(shù)

使用場景

常見的應(yīng)用是那些需要對海量數(shù)據(jù)進(jìn)行一些統(tǒng)計(jì)工作的時候，比如日志分析、用戶數(shù)統(tǒng)計(jì)等等

如統(tǒng)計(jì)40億個數(shù)據(jù)中沒有出現(xiàn)的數(shù)據(jù)，將40億個不同數(shù)據(jù)進(jìn)行排序等。

現(xiàn)在有1千萬個隨機(jī)數(shù)，隨機(jī)數(shù)的范圍在1到1億之間?，F(xiàn)在要求寫出一種算法，將1到1億之間沒有在隨機(jī)數(shù)中的數(shù)求出來

Java的Bitset

Bitset這種結(jié)構(gòu)雖然簡單，實(shí)現(xiàn)的時候也有一些細(xì)節(jié)需要主要。其中的關(guān)鍵是一些位操作，比如如何將指定位進(jìn)行反轉(zhuǎn)、設(shè)置、查詢指定位的狀態(tài)（0或者1）等。

本文，分析一下java中bitset的實(shí)現(xiàn)，拋磚引玉，希望給那些需要自己設(shè)計(jì)位圖結(jié)構(gòu)的需要的程序員有所啟發(fā)。

Bitmap的基本操作有：

• 初始化一個bitset，指定大小。
• 清空bitset。
• 反轉(zhuǎn)某一指定位。
• 設(shè)置某一指定位。
• 獲取某一位的狀態(tài)。
• 當(dāng)前bitset的bit總位數(shù)。

參考代碼：

import java.util.BitSet;
 
public class BitSetDemo {
 
  public static void main(String args[]) {
     BitSet bits1 = new BitSet(16);
     BitSet bits2 = new BitSet(16);
      
     // set some bits
     for(int i=0; i<16; i++) {
        if((i%2) == 0) bits1.set(i);
        if((i%5) != 0) bits2.set(i);
     }
     System.out.println("Initial pattern in bits1: ");
     System.out.println(bits1);
     System.out.println("\nInitial pattern in bits2: ");
     System.out.println(bits2);
 
     // AND bits
     bits2.and(bits1);
     System.out.println("\nbits2 AND bits1: ");
     System.out.println(bits2);
 
     // OR bits
     bits2.or(bits1);
     System.out.println("\nbits2 OR bits1: ");
     System.out.println(bits2);
 
     // XOR bits
     bits2.xor(bits1);
     System.out.println("\nbits2 XOR bits1: ");
     System.out.println(bits2);
  }
}

package util;
 
import java.util.Arrays;
import java.util.BitSet;
 
public class BitSetDemo {
 
    /**
     * 求一個字符串包含的char
     * 
     */
    public static void containChars(String str) {
        BitSet used = new BitSet();
        for (int i = 0; i < str.length(); i++)
            used.set(str.charAt(i)); // set bit for char
 
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        int size = used.size();
        System.out.println(size);
        for (int i = 0; i < size; i++) {
            if (used.get(i)) {
                sb.append((char) i);
            }
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
 
    /**
     * 求素?cái)?shù) 有無限個。一個大于1的自然數(shù)，如果除了1和它本身外，不能被其他自然數(shù)整除(除0以外）的數(shù)稱之為素?cái)?shù)(質(zhì)數(shù)） 否則稱為合數(shù)
     */
    public static void computePrime() {
        BitSet sieve = new BitSet(1024);
        int size = sieve.size();
        for (int i = 2; i < size; i++)
            sieve.set(i);
        int finalBit = (int) Math.sqrt(sieve.size());
 
        for (int i = 2; i < finalBit; i++)
            if (sieve.get(i))
                for (int j = 2 * i; j < size; j += i)
                    sieve.clear(j);
 
        int counter = 0;
        for (int i = 1; i < size; i++) {
            if (sieve.get(i)) {
                System.out.printf("%5d", i);
                if (++counter % 15 == 0)
                    System.out.println();
            }
        }
        System.out.println();
    }
    
    /**
     * 進(jìn)行數(shù)字排序
     */
    public static void sortArray() {
        int[] array = new int[] { 423, 700, 9999, 2323, 356, 6400, 1,2,3,2,2,2,2 };
        BitSet bitSet = new BitSet(2 << 13);
        // 雖然可以自動擴(kuò)容，但盡量在構(gòu)造時指定估算大小,默認(rèn)為64
        System.out.println("BitSet size: " + bitSet.size());
 
        for (int i = 0; i < array.length; i++) {
            bitSet.set(array[i]);
        }
        //剔除重復(fù)數(shù)字后的元素個數(shù)
        int bitLen=bitSet.cardinality();    
 
        //進(jìn)行排序，即把bit為true的元素復(fù)制到另一個數(shù)組
        int[] orderedArray = new int[bitLen];
        int k = 0;
        for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
            orderedArray[k++] = i;
        }
 
        System.out.println("After ordering: ");
        for (int i = 0; i < bitLen; i++) {
            System.out.print(orderedArray[i] + "\t");
        }
        
        System.out.println("iterate over the true bits in a BitSet");
        //或直接迭代BitSet中bit為true的元素iterate over the true bits in a BitSet
        for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
            System.out.print(i+"\t");
        }
        System.out.println("---------------------------");
    }
    
    /**
     * 將BitSet對象轉(zhuǎn)化為ByteArray
     * @param bitSet
     * @return
     */
    public static byte[] bitSet2ByteArray(BitSet bitSet) {
        byte[] bytes = new byte[bitSet.size() / 8];
        for (int i = 0; i < bitSet.size(); i++) {
            int index = i / 8;
            int offset = 7 - i % 8;
            bytes[index] |= (bitSet.get(i) ? 1 : 0) << offset;
        }
        return bytes;
    }
 
    /**
     * 將ByteArray對象轉(zhuǎn)化為BitSet
     * @param bytes
     * @return
     */
    public static BitSet byteArray2BitSet(byte[] bytes) {
        BitSet bitSet = new BitSet(bytes.length * 8);
        int index = 0;
        for (int i = 0; i < bytes.length; i++) {
            for (int j = 7; j >= 0; j--) {
                bitSet.set(index++, (bytes[i] & (1 << j)) >> j == 1 ? true
                        : false);
            }
        }
        return bitSet;
    }
    
    /**
     * 簡單使用示例
     */
    public static void simpleExample() {
        String names[] = { "Java", "Source", "and", "Support" };
        BitSet bits = new BitSet();
        for (int i = 0, n = names.length; i < n; i++) {
            if ((names[i].length() % 2) == 0) {
                bits.set(i);
            }
        }
 
        System.out.println(bits);
        System.out.println("Size : " + bits.size());
        System.out.println("Length: " + bits.length());
        for (int i = 0, n = names.length; i < n; i++) {
            if (!bits.get(i)) {
                System.out.println(names[i] + " is odd");
            }
        }
        BitSet bites = new BitSet();
        bites.set(0);
        bites.set(1);
        bites.set(2);
        bites.set(3);
        bites.andNot(bits);
        System.out.println(bites);
    }
 
    public static void main(String args[]) {
        //BitSet使用示例
        BitSetDemo.containChars("How do you do? 你好呀");
        BitSetDemo.computePrime();
        BitSetDemo.sortArray();
        BitSetDemo.simpleExample();
        
        
        //BitSet與Byte數(shù)組互轉(zhuǎn)示例
        BitSet bitSet = new BitSet();
        bitSet.set(3, true);
        bitSet.set(98, true);
        System.out.println(bitSet.size()+","+bitSet.cardinality());
        //將BitSet對象轉(zhuǎn)成byte數(shù)組
        byte[] bytes = BitSetDemo.bitSet2ByteArray(bitSet);
        System.out.println(Arrays.toString(bytes));
         
        //在將byte數(shù)組轉(zhuǎn)回來
        bitSet = BitSetDemo.byteArray2BitSet(bytes);
        System.out.println(bitSet.size()+","+bitSet.cardinality());
        System.out.println(bitSet.get(3));
        System.out.println(bitSet.get(98));
        for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
            System.out.print(i+"\t");
        }
    }
}

使用場景解析

Redis用bitset(bitmap)來統(tǒng)計(jì)日活躍量

假設(shè)這樣一個場景，假如每個網(wǎng)站有1億的用戶，那么我們怎么來統(tǒng)計(jì)這個網(wǎng)站的日登陸數(shù)或者說有哪些用戶登錄過這個網(wǎng)站。
最常見的做法就是設(shè)計(jì)一張用戶登錄表：

user_login:

如果平均一個人一天登錄1次，那么1億個用戶一個星期就會產(chǎn)生1 * 1 * 7 = 7億條數(shù)據(jù)，一個月就會產(chǎn)生30億條數(shù)據(jù)，這對數(shù)據(jù)庫的壓力是很大的，只是統(tǒng)計(jì)一下用戶登錄，沒必要花費(fèi)這么多的資源。

這個時候我們就可以用reids 的bitmap來解決。

用戶是否登錄可以用0/1來表示，0代表用戶不登陸，1表示登錄，那么1bit 就可以表示用戶是否登錄。

1億個用戶一天的數(shù)據(jù)量也就 1 0000 0000bit = 11.92m，也就是說用戶一天的登錄信息也就產(chǎn)生11.92m的數(shù)據(jù)量。一個月也就357.63m的數(shù)據(jù)量。

具體實(shí)現(xiàn)過程（為了實(shí)驗(yàn)方便，我們就假設(shè)4個用戶0，1，2，3，統(tǒng)計(jì)兩天的登錄量）：

mon: 1010 （用戶0未登錄，用戶1登錄，用戶2未登錄，用戶3登錄）

tue: 1101 （用戶0登錄，用戶1未登錄，用戶2登錄，用戶3登錄）

初始化數(shù)據(jù):

127.0.0.1:6379> setbit mon 0 0
(integer) 1
127.0.0.1:6379> setbit mon 1 1
(integer) 1
127.0.0.1:6379> setbit mon 2 0
(integer) 0
127.0.0.1:6379> setbit mon 3 1
(integer) 0

127.0.0.1:6379> setbit tue 0 1
(integer) 1
127.0.0.1:6379> setbit tue 1 0
(integer) 1
127.0.0.1:6379> setbit tue 3 1
(integer) 0
127.0.0.1:6379> setbit tue 4 1
(integer) 1

如果要統(tǒng)計(jì)這兩天都登陸的用戶：

127.0.0.1:6379> bitop AND result mon tue
(integer) 1
127.0.0.1:6379> getbit result 0
(integer) 0
127.0.0.1:6379> getbit result 1
(integer) 0
127.0.0.1:6379> getbit result 2
(integer) 0
127.0.0.1:6379> getbit result 3
(integer) 1

可以看到mon 和 tue做and運(yùn)算，得到結(jié)果result為:0001，則表示用戶3連續(xù)兩天都登陸，其他用戶兩天中只有一天登錄。

基于bitset實(shí)現(xiàn)手機(jī)號的黑白名單方案

目前很多應(yīng)用都把手機(jī)號碼作為登錄的賬戶名，本文介紹一種高效的基于手機(jī)號，來實(shí)現(xiàn)黑白名單的方案。

在這里我先用一個例子來說明位圖。

假設(shè)我有一個0到31的集合，集合里面的元素不重復(fù)，比如這樣{0,3,1,5,2,19,7,8,31,21,10}。通過位圖，我可以將這樣的集合表示為11110001101000000001010000000001, 其中1表示該數(shù)值為下標(biāo)的數(shù)存在在集合中，比如第一個1表示0存在集合中，第二個1表示1存在集合中，等等。

通過這樣做，我們起碼可以得到兩個好處

1. 節(jié)省空間--我們可以用二進(jìn)制一個位來存儲存儲兩個信息，一是存不存在，而是存在的數(shù)是多少（通過一個bit就可以得到這么多信息，真了不起）。
2. 排序--從左到右遍歷這個為圖，我們可以得到排序的集合，比如上例中，我們可以得到集合 {0,1,2,3,7,8，10，19,21,31}

如果將所有這電話號碼用位圖表示，那么需要9999999999個bit （10個9， 考慮到手機(jī)號碼的第一位都是1）。 9999999999 bit = （9999999999/8） byte = (9999999999 / (8 * 1024)) KB = (9999999999 / 8 10241024) M = 1192M

嗯....，1192M,內(nèi)存占有還是太大，我們前期的黑白名單所占內(nèi)存遠(yuǎn)遠(yuǎn)低于這個值。 考慮到手機(jī)號碼的前3位都差不多，而且總數(shù)最多30個，所以考慮到手機(jī)號碼拆分為兩部分(頭3位和剩余8位)，這樣就把位圖的位數(shù)就降2個數(shù)量級了。所以如果我們要在內(nèi)存中裝入手機(jī)號碼后8位，需要99999999（8個9）個bit，算一下：99999999 bit = （99999999/8） byte = (99999999 / (8 * 1024)) KB = (99999999 / 8 10241024) M = 11.92M

內(nèi)存中裝入頭2位(手機(jī)號第一位始終為1，因此只需裝入后面2位)，需要99(2個9)個bit,算下
99 bit = 99/8 byte =12.375 byte。

大約12M 內(nèi)存，就能表示所有手機(jī)號碼，達(dá)到黑白名單。

這個比用redis等緩存，高效很多，java里面的bitset也是這個原理。

分享自我的微信訂閱號“猿in”，可以搜索關(guān)注。

參考

[Redis用bitset(bitmap)來統(tǒng)計(jì)日活躍量]

https://blog.csdn.net/qq_30788949/article/details/74120254

[基于bitset實(shí)現(xiàn)手機(jī)號的黑白名單方案]

https://blog.csdn.net/nature502/article/details/52371299

[Java中BitSet的使用及詳解]

https://blog.csdn.net/jiangnan2014/article/details/53735429

[Java Bitset類]

https://www.runoob.com/java/java-bitset-class.html