【資料結構】BitMap使用

BitMap介紹

大資料是越來越火熱的一個詞語，對大資料的處理也同樣是各種公司面試的常問題目。對大資料處理有幾種通用的方式：分治，分布式，bitmap，bloom filter。bitmap與bloom filter主要是用于對大資料進行過濾，找到符合某些條件的資料。本文對bitmap進行簡單分析。

java中有對bitmap的實作，是java,util.BitSet。

其提供了兩種構造方法：

BitSet() 建立一個新的位 set。

BitSet(int nbits) 建立一個位 set，它的初始大小足以顯式表示索引範圍在 到 nbits-1 的位。

BitSet所有的操作都是對某一位進行操作的，比如public void set(int bitIndex, boolean value) 就是對bitIndex這一位進行指派操作，而不是對大小進行指派。比如set(1, true)表示對第二位指派為true，真實表現為10.如果想表示2曾經出現過，那麼就需要set(1, true)，因為2的二進制表示就是10。

其中BitSet提供了兩種擷取大小的方法，length()，size()，注意這兩種方法是不同的。

length()：傳回此

BitSet

的“邏輯大小”：

BitSet

中最高設定位的索引加 1。如果

BitSet

中不包含任何設定位，則傳回零；比如你new了一個bitSet，bitSet(100，true)。那麼對其調用length()，則傳回的是101.

size()：而這個方法傳回的是在實際存儲中，

BitSet

為了存儲你的資料總過占據了實際位數是多少。比如，你使用了第二種構造方法new

BitSet

(100)，在計算機中都是按照位元組來辨別，是以對于100肯定需要一個大約100的整位元組數進行存儲，這時候傳回的size就是128.其實最主要的是BitSet内部封裝了一個long型的數組，每次new一個新的BitSet對象都是對long型的數組進行分析和處理的。最後傳回的位數其實就是需要幾個long型的數字，比如128位，則其實是16個位元組，則表示需要兩個long型的數字來表示整個bitset。

最長子序列

給定一個數組，求該數組中最長的連續子序列。思路可以是先排序，但是排序都是需要O(nlogn)的複雜度，那有沒有O(n)的負責度的算法那。答案肯定是有的，而且有很多種辦法。本文是利用了bitmap，也可以利用hashmap。

思路：是先對數組進行周遊，對數組中的每個數在bitmap中設定為1，然後對bitmap進行周遊，查找最長連續出現的序列

private static void process() {
        int[] array = {15, 7, 12, 6, 14, 13, 9, 11};
        BitSet bitSet = new BitSet();
        for(int e : array){
            bitSet.set(e);
        }
        int max = 0;
        int tmp = 0;
        for(int i = 0; i < bitSet.size(); i ++){
            if(bitSet.get(i)){
                tmp += 1;
            }else{
                if(tmp > max){
                    max = tmp;
                }
                tmp = 0;
            }
        }
        System.out.println(max);
    }

    public static void main(String[] args) {
        process();
    }