點陣圖的基本介紹概念

什麼是點陣圖?BitMap,大家直譯為點陣圖. 我的理解是:點陣圖是記憶體中連續的二進位制位(bit),可以用作對大量整形做去重和統計.

引入一個小例子來幫助理解一下:

假如我們要儲存三個int數字 (1,3,5),在java中我們用一個int陣列來儲存,那麼佔用了12個位元組.但是我們申請一個bit陣列的話.並且把相應下標的位置為1,也是可以表示相同的含義的,比如

下標	0	1	2	3	4	5	6	7
二進位制值	0	1	0	1	0	1	0	0

可以看到,對應於1,3,5為下標的bit上的值為1,我們或者計算機也是可以get到1,3,5這個資訊的.

優勢

那麼這麼做有什麼好處呢?感覺更麻煩了呀,下面這種儲存方式,在申請了bit[8]的場景下才佔用了一個位元組,佔用記憶體是原來的12分之一,當資料量是海量的時候,比如40億個int,這時候節省的就是10幾個G的記憶體了.

這就引入了點陣圖的第一個優勢,佔用記憶體小.

再想一下,加入我們現在有一個位圖,儲存了使用者今天的簽到資料.下標可以是使用者的ID.

A:

使用者ID	0	1	2	3	4	5	6	7
二進位制值	0	1	0	1	0	1	0	0

這代表了使用者(1,3,5)今天簽到了.

當然還有昨天的點陣圖,

B:

使用者ID	0	1	2	3	4	5	6	7
二進位制值	0	1	1	1	0	0	0	1

這代表了使用者(1,2,3,7)昨天簽到了.

我們現在想求:

昨天和今天都簽到的使用者.昨天或者今天簽到的使用者.

在關係型資料庫中儲存的話,這將是一個比較麻煩的操作,要麼要寫一些表意不明的SQL語句,要麼進行兩次查詢,然後在記憶體中雙重迴圈去判斷.

而使用點陣圖就很簡單了,A & B, A | B 即可.上面的操作明顯是一個集合的與或操作,而二進位制天然就支援邏輯操作,且眾所周知貓是液體.錯了,眾多周知是計算機進行二進位制運算的效率很高.

這就是點陣圖的第二個優點: 支援與或運算且效率高.

哇,這麼完美,那麼哪裡可以買到呢?,那麼有什麼缺點呢?

不足

當然有,點陣圖不能很方便的支援非運算,(當然,關係型資料庫支援的也不好).這句話可能有點難理解.繼續舉個例子:

我們想查詢今天沒有簽到的使用者,直接對點陣圖進行取非是不可以的.

對今天簽到的點陣圖取非得到的結果如下:

使用者ID	0	1	2	3	4	5	6	7
二進位制值	1	0	1	0	1	0	1	1

這意味著今天(0,2,4,6,7)使用者沒有簽到嗎?不是的,存在沒有7(任意數字)號使用者的情況,或者他登出了呢.

這是因為點陣圖只能表示布林資訊,即true/false.他在這個點陣圖中,表示的是XX使用者今天有簽到或者沒有簽到,但是不能額外的表達,xx使用者存在/不存在這個狀態了.

但是我們可以曲線救國,首先搞一個全集使用者的點陣圖.比如:

全集:

使用者ID	0	1	2	3	4	5	6	7
二進位制值	1	1	1	1	1	0	1	0

然後用全集的點陣圖和簽到的點陣圖做異或操作,相同則為0,不相同則為1.

該業務的邏輯為: 使用者存在和是否簽到兩個bool值,共四種組合.

使用者存在,且簽到了. 兩個集合的對應位都為1,那麼結果就為0. 使用者存在,但是沒簽到. 全集對應位為1,簽到為0,所以結果是1. 使用者不存在,那麼必然沒可能簽到, 兩個集合的對應位都是0,結果為0.

所以結果中,為1的只有一種可能:使用者存在且沒有簽到,正好是我們所求的結果.

A ^ 全集:

使用者ID	0	1	2	3	4	5	6	7
二進位制值	1	0	1	0	1	0	1	0

此外,點陣圖對於稀疏資料的表現不是很好,(當然聰明的大佬們已經基本解決掉了這個問題).原生的點陣圖來講,如果我們只有兩個使用者,1號和100000000號使用者,那麼直接儲存int需要8個位元組也就是32個bit,而用點陣圖儲存需要1億個bit.當資料量少,且跨度極大也就是稀疏的時候,原生的點陣圖不太適合.

總結

那麼我們來做一下總結:

點陣圖是用二進位制位來儲存整形資料的一種資料結構,在很多方面都有應用,尤其是在大資料量的場景下,節省記憶體及提高運算效率十分實用.

他的優點有:

節省記憶體. -> 因此在大資料量的時候更加顯著.與或運算效率高. ->可以快速求交集和並集.

缺點有:

不能直接進行非運算. -> 根本原因是點陣圖只能儲存一個布林資訊,資訊多了就需要藉助全量集合等資料輔助.資料稀疏時浪費空間. -> 這個不用很擔心,後面會講到大佬們的解法,基本可以解決掉.只能儲存布林型別. -> 有限制,但是業務中很多資料都可以轉換為布林型別.比如上面的例子中, 業務原意:使用者每天的簽到記錄,以使用者為維度. 我們可以轉換為: 每天的每個使用者是否簽到,就變為了布林型別的資料.Java中的點陣圖

上面講了點陣圖的原理,那麼我們先來自己手動實現一個!

簡陋版本

說明:因為後面還有JDK版本,所以這裡只實現了很簡陋的版本,方便理解點陣圖的核心原理即可.這個簡陋版本完全不可以直接使用,能跑,但是在很多情況下都會直接報錯.

雖然簡陋,但是必須的還是要有.

構造方法

寫了一個僅支援bit數量的構造引數. 因為我們是用int陣列來儲存實際的資料,所以對傳入的值右移5(相當於除以32,因為int是32位的嘛)就是int陣列的大小.

set方法

支援將某一個位設定為true/false.

為了實現set-true,其實是有粗暴的符合人類思路的邏輯的,比如當呼叫set(5,true)的時候,我們將int數字轉化為二進位制字串,得到000000000000000000000000000000(應該是32個我沒數),然後將其右邊第六位置為1,得到000000000000000000000000100000,然後再轉回int數字.

這個方法很符合點陣圖的直接定義,也很好理解,但是對於計算機來說,太麻煩了,而且過程中需要一個String,佔用太多的記憶體空間了.

計算機更喜歡使用或運算來解決. 假設現有數字為3,即000000000000000000000000001000,這時候我們呼叫了set(10,true),怎麼辦呢,首先使用左移,將第11位置為1,然後與原來的值進行或操作.像下面這樣子:

原來值 :     0000000000000000000000000010001右移10位:   000000000000000000010000000000或操作的結果: 000000000000000000010000001000   ----> 可以直接表示 3 和 10 兩個位上都為1了.複製程式碼

設定某一個位為false,和上面的流程不太一樣.除去粗暴的辦法之外,還可以 對1右移x位的非區域.很拗口,下面是示例:

我們將3上的設為0.

原來值 :              000000000000000000010000001000    ----> 10和3上為1,1右移3位:             0000000000000000000000000010001右移3位取非後:        111111111111111111111111110111原來的值與取非後取與:   000000000000000000010000000000   ----> 只有10上為1了.複製程式碼

get方法

獲取某個位上的值.

當然也可以用粗暴的轉換二進位制字串解決,但是使用與操作更加快速且計算機友好.

對set方法中的例子來說,設定了3和10之後,如果獲取10上的值,可以:

當前值:        0000000000000000000100000010001右移10位:     000000000000000000010000000000與操作的結果:   000000000000000000010000000000    ---> 只要這個數字不等於0,即說明10上為1,等於0則為0.複製程式碼

實際的程式碼加註釋如下:

/** * Created by pfliu on 2019/07/02. */public class BitMapTest {    // 實際使用int陣列儲存    private int[] data;    /**     * 構造方法,傳入預期的最大index.     */    public BitMapTest(int size) {        this.data = new int[size >> 5];    }    /**     * get 方法, 傳入要獲取的index, 返回bool值代表該位上為1/0     */    public boolean get(int bitIdx) {        return (data[bitIdxToWorkIdx(bitIdx)] & (1 << bitIdx)) != 0;    }    /**     * 將對應位置的值設定為傳入的bool值     */    public void set(int idx, boolean v) {        if (v) {            set(idx);        } else {            clear(idx);        }    }    // 將index的值設定為1    private void set(int idx) {        data[bitIdxToWorkIdx(idx)] |= 1 << idx;    }    // 將index上的值設定為0    private void clear(int bitIdx) {        data[bitIdxToWorkIdx(bitIdx)] &= ~(1L << bitIdx);    }    // 根據bit的index獲取它儲存的實際int在陣列中的index    private int bitIdxToWorkIdx(int bitIdx) {        return bitIdx >> 5;    }    public static void main(String[] args) {        BitMapTest t = new BitMapTest(100);        t.set(10, true);        System.out.println(t.get(9));        System.out.println(t.get(10));    }}複製程式碼

JDK版本(BitSet原始碼閱讀)

JDK中對點陣圖是有實現的,實現類為BitSet,其中大致思想和上面實現的簡陋版本類似,只是其內部資料是使用long陣列來儲存,此外加了許多的容錯處理.下面看一下原始碼.還是按照方法分類來看.

常量及變數

    // long陣列,64位的long是2的6次方    private final static int ADDRESS_BITS_PER_WORD = 6;    // 每一個word的bit數量    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;    // 儲存資料的long陣列    private long[] words;    // 上面的陣列中使用到了的word的個數    private transient int wordsInUse = 0;    // 陣列的大小是否由使用者指定的(註釋裡寫明瞭:如果是true,我們假設使用者知道他自己在幹什麼)    private transient boolean sizeIsSticky = false;複製程式碼

構造方法及工廠方法

BitSet提供了兩個公開的構造方法以及四個公開的工廠方法,分別支援從long[],LongBuffer,bytes [], ByteBuffer中獲取BitSet例項.

各個方法及其內部呼叫的方法如下:

    // ---------構造方法-------    // 無參的構造方法,初始化陣列為長度為64個bit(即一個long)以及設定sizeIsSticky為false.    public BitSet() {        initWords(BITS_PER_WORD);        sizeIsSticky = false;    }    // 根據使用者傳入的bit數量進行初始化,且設定sizeIsSticky為true.    public BitSet(int nbits) {        // nbits can't be negative; size 0 is OK        if (nbits < 0)            throw new NegativeArraySizeException("nbits < 0: " + nbits);        initWords(nbits);        sizeIsSticky = true;    }    // ---------構造方法的呼叫鏈 -------    // 初始化陣列    private void initWords(int nbits) {        words = new long[wordIndex(nbits-1) + 1];    }    // 根據bit數量獲取long陣列的大小,右移6位即可.    private static int wordIndex(int bitIndex) {        return bitIndex >> ADDRESS_BITS_PER_WORD;    }    // ---------工廠方法,返回BitSet例項 -------    // 傳入long陣列    public static BitSet valueOf(long[] longs) {        int n;        for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)            ;        return new BitSet(Arrays.copyOf(longs, n));    }    // 傳入LongBuffer    public static BitSet valueOf(LongBuffer lb) {        lb = lb.slice();        int n;        for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)            ;        long[] words = new long[n];        lb.get(words);        return new BitSet(words);    }    // 傳入位元組陣列    public static BitSet valueOf(byte[] bytes) {        return BitSet.valueOf(ByteBuffer.wrap(bytes));    }    // 傳入ByteBuffer    public static BitSet valueOf(ByteBuffer bb) {        bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);        int n;        for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)            ;        long[] words = new long[(n + 7) / 8];        bb.limit(n);        int i = 0;        while (bb.remaining() >= 8)            words[i++] = bb.getLong();        for (int remaining = bb.remaining(), j = 0; j < remaining; j++)            words[i] |= (bb.get() & 0xffL) << (8 * j);        return new BitSet(words);    }複製程式碼

set方法

BitSet提供了兩類set方法,

單點set. 將某個index設定為tue/false.範圍set. 將某個範圍值設定為tue/false.

因此BitSet有四個重要的set方法.

   // 將某個index的值設定為true. 使用和上面自己實現的簡陋版本相同的或操作.    public void set(int bitIndex) {        if (bitIndex < 0)            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        int wordIndex = wordIndex(bitIndex);        expandTo(wordIndex);        words[wordIndex] |= (1L << bitIndex); // Restores invariants        checkInvariants();    }    // 將某個index設定為傳入的值,注意當傳入值為false的時候,呼叫的是clear方法.    public void set(int bitIndex, boolean value) {        if (value)            set(bitIndex);        else            clear(bitIndex);    }    // 將index上bit置為0    public void clear(int bitIndex) {        if (bitIndex < 0)            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        int wordIndex = wordIndex(bitIndex);        if (wordIndex >= wordsInUse)            return;        words[wordIndex] &= ~(1L << bitIndex);        recalculateWordsInUse();        checkInvariants();    }    // 將from->to之間的所有值設定為true    public void set(int fromIndex, int toIndex) {        checkRange(fromIndex, toIndex);        if (fromIndex == toIndex)            return;        // Increase capacity if necessary        int startWordIndex = wordIndex(fromIndex);        int endWordIndex   = wordIndex(toIndex - 1);        expandTo(endWordIndex);        long firstWordMask = WORD_MASK << fromIndex;        long lastWordMask  = WORD_MASK >>> -toIndex;        if (startWordIndex == endWordIndex) {            // Case 1: One word            words[startWordIndex] |= (firstWordMask & lastWordMask);        } else {            // Case 2: Multiple words            // Handle first word            words[startWordIndex] |= firstWordMask;            // Handle intermediate words, if any            for (int i = startWordIndex+1; i < endWordIndex; i++)                words[i] = WORD_MASK;            // Handle last word (restores invariants)            words[endWordIndex] |= lastWordMask;        }        checkInvariants();    }    // 將from->to之間的所有值設定為傳入的值,當傳入的值為false的適合,呼叫的是下面的clear.    public void set(int fromIndex, int toIndex, boolean value) {        if (value)            set(fromIndex, toIndex);        else            clear(fromIndex, toIndex);    }    // 將範圍內的bit置為0    public void clear(int fromIndex, int toIndex) {        checkRange(fromIndex, toIndex);        if (fromIndex == toIndex)            return;        int startWordIndex = wordIndex(fromIndex);        if (startWordIndex >= wordsInUse)            return;        int endWordIndex = wordIndex(toIndex - 1);        if (endWordIndex >= wordsInUse) {            toIndex = length();            endWordIndex = wordsInUse - 1;        }        long firstWordMask = WORD_MASK << fromIndex;        long lastWordMask  = WORD_MASK >>> -toIndex;        if (startWordIndex == endWordIndex) {            // Case 1: One word            words[startWordIndex] &= ~(firstWordMask & lastWordMask);        } else {            // Case 2: Multiple words            // Handle first word            words[startWordIndex] &= ~firstWordMask;            // Handle intermediate words, if any            for (int i = startWordIndex+1; i < endWordIndex; i++)                words[i] = 0;            // Handle last word            words[endWordIndex] &= ~lastWordMask;        }        recalculateWordsInUse();        checkInvariants();    }複製程式碼

這裡有一個需要注意點,那就是當傳入的值為true/fasle的時候,處理邏輯是不同的.具體的邏輯見上面簡陋版本中的示例.

get方法

BitSet提供了一個獲取單個位置bit值的方法,以及一個範圍獲取,返回一個新的BitSet的方法.

    // 獲取某個位置的bit值    public boolean get(int bitIndex) {        if (bitIndex < 0)            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        checkInvariants();        int wordIndex = wordIndex(bitIndex);        return (wordIndex < wordsInUse)            && ((words[wordIndex] & (1L << bitIndex)) != 0);    }    // 返回一個子集,包含傳入範圍內的bit    public BitSet get(int fromIndex, int toIndex) {        checkRange(fromIndex, toIndex);        checkInvariants();        int len = length();        // If no set bits in range return empty bitset        if (len <= fromIndex || fromIndex == toIndex)            return new BitSet(0);        // An optimization        if (toIndex > len)            toIndex = len;        BitSet result = new BitSet(toIndex - fromIndex);        int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;        int sourceIndex = wordIndex(fromIndex);        boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);        // Process all words but the last word        for (int i = 0; i < targetWords - 1; i++, sourceIndex++)            result.words[i] = wordAligned ? words[sourceIndex] :                (words[sourceIndex] >>> fromIndex) |                (words[sourceIndex+1] << -fromIndex);        // Process the last word        long lastWordMask = WORD_MASK >>> -toIndex;        result.words[targetWords - 1] =            ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)            ? /* straddles source words */            ((words[sourceIndex] >>> fromIndex) |             (words[sourceIndex+1] & lastWordMask) << -fromIndex)            :            ((words[sourceIndex] & lastWordMask) >>> fromIndex);        // Set wordsInUse correctly        result.wordsInUse = targetWords;        result.recalculateWordsInUse();        result.checkInvariants();        return result;    }複製程式碼

邏輯操作

JDK實現的點陣圖當然是有邏輯操作的,主要支援了與,或,異或,與非四種操作,由於程式碼不難,這裡就不貼程式碼了,簡略的貼一下API.

    // 與操作    public void and(BitSet set);    // 或操作    public void or(BitSet set);    // 異或操作    public void xor(BitSet set);    // 與非操作    public void andNot(BitSet set);複製程式碼

到這裡,BitSet的原始碼就讀完了,但是有沒有發現一個問題 ? 前面說的稀疏資料的問題並沒有得到解決,別急,下面就來了.

EWAHCompressedBitmap

這是google開發的javaEWAH包中的一個類.名字中的EWAH = Enhanced Word-Aligned Hybrid.而Compressed是指壓縮.

複習一下稀疏資料的問題,假設我們在一個位圖中,首先set(1),然後set(1億)會怎樣?

我們使用JDK中的BitSet來試一下,在執行過程中打斷點看一下內部的陣列是什麼樣子.如下圖:

將其序列化輸出到檔案中,檔案大小如下圖:

可以看到,我們為了儲存1和1億這兩個數字,花費了一個一千多萬長度的long陣列,序列化後佔用記憶體將近200m.這是不科學的.

接下來就是EWAHCompressedBitmap了,名字裡面都帶了壓縮,那麼想必表現不錯.

可以看到long陣列的長度僅僅為4,且輸出的檔案大小為96byte.

這就很符合預期了.

在EWAHCompressedBitmap中,資料也是使用long陣列來儲存的,不過對每一個long有類別的定義,Literal Word和Running Length Word.

Literal Word: 儲存真正的bit位.Running Length Word: 儲存跨度資訊.

什麼是跨度資訊呢? 舉個例子:

在剛才使用BitSet儲存1億的時候,截圖中long陣列有一千多萬個0,以及之後的一個值.

使用BitSet儲存1和1億(2048為虛擬值,不想算了):

long	long	long	long	long	long	long	long	long	long	long	long
2	0	0	0	0	0	0	0	...1千萬個0呢	0	0	2048

而在EWAHCompressedBitmap中,則是類似下面這樣:

long	long	long
2	一千萬個0	2048

這樣看起來好像沒什麼區別....但是在BitSet中,一千萬個0是真的使用了一千萬個long來儲存的.而在EWAHCompressedBitmap中,這個資訊使用一個long來儲存,long的值表示具體有多少個0在這個區間內.

這樣子做,點題了.與名字中的壓縮相對應.將連續的0或者1進行壓縮,以節省空間.

這樣做有沒有什麼副作用呢?有的,當你的每一次插入都在一個Running Length Word上,也就是每一次插入都涉及到了Running Length Word的分裂,會降級效能,因此官方建議最好資料的插入從小到大進行.

EWAHCompressedBitmap基本解決了稀疏資料的問題,而當資料很稠密的時候,他的壓縮率沒有那麼好,但是通常也不會差於不壓縮的儲存方式,因此在日常的使用中,還是建議大家使用這個類,除非你很清楚且能確保自己的資料不會過於稀疏.

總結

在本節,我們手動實現了一個極其簡陋的點陣圖,然後閱讀了JDK中點陣圖實現類BitSet的原始碼,然後分析瞭如何使用EWAHCompressedBitmap來解決稀疏資料的問題,對於EWAHCompressedBitmap的原始碼具體實現沒有詳細分析,有興趣的朋友可以自己去檢視.

Java語言使用者廣泛,因此對於點陣圖的實現,網上各種版本都有,既有大廠維護的開源版本,也有個人編寫的版本.在使用時也不用完全侷限於EWAHCompressedBitmap,可以使用各種魔改版本,由於點陣圖的實現邏輯不是特別複雜,因此在使用前清楚其具體的實現邏輯即可.

Redis中的點陣圖

Redis是支援點陣圖的,但是點陣圖並不是一個單獨的資料結構,而是在String型別上定義的一組面向位的操作指令.也就是說,當你使用Redis點陣圖時,其實底層儲存的是Redis的string型別.因此:

由於Redis的string是二進位制安全的,所以用它當做點陣圖的儲存方式是可行的.Redis 的String型別最大是512Mb.所以Redis的單個位圖只能儲存2的32個次方個int.這應該是夠用了.(不夠用的話可以分key,用字首來搞.)由於底層是string,因此redis是沒有對稀疏資料進行處理的,因此在使用時要額外注意這一點,防止這個key拖垮redis伺服器.

Redis支援的操作如下:

getbit: 獲取某個key的某個位置的值. getbit key offset.setbit: 設定某個位置的值. setbit key offset value.bitcount: 計算某個key中為1的bit數量.支援範圍. bitcount key start endbitpos: 返回範圍內第一個為特定bit的位置. bitpos key bit(0/1) start endbitop: 邏輯運算,支援四種邏輯運算,和上面BitSet支援的四種一樣,具體的命令如下:

BITOP AND destkey srckey1 srckey2 srckey3 ... srckeyNBITOP OR destkey srckey1 srckey2 srckey3 ... srckeyNBITOP XOR destkey srckey1 srckey2 srckey3 ... srckeyNBITOP NOT destkey srckey複製程式碼

其中destkey是結果儲存的key,其餘的srckey是參與運算的來源.

應用場景

應用場景其實是很考驗人的,不能學以致用,在程式設計師行業裡基本上就相當於沒有學了吧...

經過自己的摸索以及在網上的瀏覽,大致見到了一些應用場景,粗略地寫出來,方便大家理解並且以後遇到類似的場景可以想到點陣圖並應用他!

使用者簽到/搶購等唯一限制

使用者簽到每天只能一次,搶購活動中只能購買一件,這些需求導致的有一種查詢請求,給定的id做沒做過某事.而且一般這種需求都無法接受你去查庫的延遲.當然你查一次庫之後在redis中寫入:key = 2345 , value = 簽到過了.也是可以實現的,但是記憶體佔用太大.

而使用點陣圖之後,當2345使用者簽到過/搶購過之後,在redis中呼叫setbit 2019-07-01-簽到 2345 1即可,之後使用者的每次簽到/搶購請求進來,只需要執行相應的getbit即可拿到是否放行的bool值.

這樣記錄,不僅可以節省空間,以及加快訪問速度之外,還可以提供一些額外的統計功能,比如呼叫bitcount來統計今天簽到總人數等等.統計速度一般是優於關係型資料庫的,可以用來做實時的介面查詢等.

使用者標籤等資料

大資料已經很普遍了,使用者畫像大家也都在做,這時候需要根據標籤分類使用者,進行儲存.方便後續的推薦等操作.

而使用者及標籤的資料結構設計是一件比較麻煩的事情,且很容易造成查詢效能太低.同時,對多個標籤經常需要進行邏輯操作,比如喜歡電子產品的00後用戶有哪些,女性且愛旅遊的使用者有哪些等等,這在關係型資料庫中都會造成處理的困難.

可以使用點陣圖來進行儲存,每一個標籤儲存為一個位圖(邏輯上,實際上你還可以按照尾號分開等等操作),在需要的時間進行快速的統計及計算. 如:

使用者	0	1	2	3	4	5	6	7	8
愛旅遊	1	0	0	1	0	0	1	0	0

可以清晰的統計出,0,3,6使用者喜歡旅遊.

使用者	0	1	2	3	4	5	6	7	8
00後	1	1	0	0	0	0	1	0	0

使用者0,1,6是00後.

那麼對兩個點陣圖取與即可得到愛旅遊的00後用戶為0,6.

總結

總之,bitmap可以高效且節省空間的儲存與使用者ID相關聯的布林資料.常見的可以應用其做大量資料的去重以及統計.更多的應用就開發你的想象力吧.

原文連結：https://juejin.cn/post/6844903879201718280