你好，我是你的數據結構課老師蔡元楠，歡迎進入第 02 課時的內容“位數組在 Redis 中的應用”。 在上一講中，我們一起深入學習了數組這個數據結構。這一講我們來探討數組的高階應用，即位數組（Bit Array），以及這種數據結構是如何在 Redis 中應用的。 #### 統計每個月學習專欄的用戶活躍度 在開始之前，我們先來考慮一個關于用戶行為分析的問題，假設要統計《數據結構精講：從原理到實戰》這個專欄每個月的用戶活躍度。在每個月中，只要有用戶登錄并且學習了這個專欄，都會將這個用戶的 ID 寫入一張 MySQL 表中。如果想知道在 2019 年 11 和 12 這兩個月內都在學習這個專欄的用戶有多少，應該怎么做呢？ 很直觀的一個做法是執行類似下面的一個 SQL 語句： ``` SELECT COUNT(*) FROM nov_stats INNER JOIN dec_stats ON nov_stats.user_id = dec_stats.user_id WHERE nov_stats.logged_in_month = "2019-11" AND dec_stats.logged_in_mont = "2019-12" ``` 不過這種做法需要進入到數據庫中去讀取數據并且做內連接，效率不是那么高。是不是有更簡單高效的做法呢？學完這一講的內容后相信就能找到答案了。 * [ ] 比特與字節 我們經常聽到一些人打趣地說：“在程序員的眼中，永遠只有 0 和 1 ”。確實，計算機處理信息時的最小單位其實就是一個二進制單位，即比特（Bit）。而每 8 個二進制比特位都可以組成另一個單位，即字節（Byte），字節是內存空間中的一個基本單位。 因為比特只能表達“0”或者“1”兩種狀態，它非常適合用來表示布爾類型的狀態。例如，我們可以用比特來表示用戶是否有訂閱《數據結構精講：從原理到實戰》這個專欄，“0”的狀態位表示沒有訂閱，“1”的狀態位表示已經訂閱。 如果我們需要聲明一個以比特為基本單位的數組，應該怎么做呢？我們都知道，一般在高級語言里面，是無法直接聲明一個以比特為單位的基本類型的，而比特只有“0”或者“1”這兩種狀態，那最簡單的方法是可以聲明一個以 int 為單位的數組，這個數組的值我們規定只能為“0”或者“1”，用來表示比特位的“0”和“1”。 下面以 Java 為例，假設我們要聲明一個大小為 2 的“比特數組”，其代碼如下所示。 ``` int[] d = new int[2]; ``` 根據上面的聲明，我們可以利用這個數組來表示兩種不同的狀態。但是這種方法有一個很明顯的缺點，那就是消耗了過多的存儲空間。無論是在 32 位還是 64 位的機器上，int 這種基本類型在 Java 中的大小都是占 4 個字節空間的，即總共占有 4 × 8 = 32 個比特位。從理論上來說，我們只是需要其中的一個比特位來記錄狀態，所以在這里整個數組浪費掉了 31 / 32 = 96.875% 的內存空間。 * [ ] 位數組 那有沒有更好的方法呢？當然有，既然一個 int 類型是有 32 個比特位的，我們其實可以把數組中一個 int 類型的元素當作是可以表達布爾狀態的 32 個比特位元素。這種將每個元素中的每一個比特位都作為狀態信息存儲的數組稱之為位數組（Bit Array）或者位圖（Bit Map）。 那我們來看看上面聲明的擁有兩個元素的 int 數組的內存模型是怎么樣的。  這個位數組總共可以表達 64 個狀態位，通過上圖，我們可以得知，位數組在內存中的結構以及這個位數組索引的分布。 當我們要操作位數組中在位置為“i”這個比特位的時候，應該如何定位它呢？很簡單，可以按照下面的公式來定位。 ``` 所在數組中的元素為： i / data_size 比特位在元素中的位置為：i % data_size ``` 那我們以定位索引為 35 這個比特位為例子來說明一下，套用上面的公式，可以得出： ``` 所在數組中的元素為： 35 / 32 = 1 比特位在元素中的位置為：35 % 32 = 3 ``` 所以這個比特位是位于 d[1] 這個元素上索引為 3 的位置。 一般來說因為位數組的元素只保存“0”或者“1”兩種狀態，所以對于位數組的操作有以下幾種： * 獲取某個位置的比特位狀態； * 設置某個位置的比特位，也就是將那個位置的比特位設置為“1”； * 清除某個位置的比特位，也就是將那個位置的比特位設置為“0”。 * [ ] 位數組的實現 下面我們就以 Java 為例，自己動手來實現這三個操作的核心部分。 * （1）GetBit 我們可以聲明 GetBit 的方法簽名為： ``` boolean GetBit(int[] array, long index); ``` 這個方法將用于獲取在 array 位數組中 index 位上的比特位是什么狀態，如果為“1”則返回 true，如果為“0”則返回 false。 根據前面的介紹，獲取比特位所在的元素以及比特位在元素中的位置公式，核心的算法如下： ``` boolean GetBit(int[] array, int index) { ... int elementIndex = index / 32; int position = index % 32; long flag = 1; flag = flag << position; if ((array[elementIndex] & flag) != 0) { return true; } else { return false; } } ``` 我們用以下這個位數組來驗證一下，假設這個位數組的值如下圖所示：  如果調用了 GetBit(d, 35) 這條語句，將得到 elementIndex 為 1、position 為 3、flag 為 0x08，將 d[1] 和 0x08 進行位操作的與運算，最后可以得出一個非 0 的結果，所以這個函數返回 true。 而如果調用了 GetBit(d, 32) 這條語句，我們將得到 elementIndex 為 1、position 為 0、flag 為 0x1，將 d[1] 和 0x1 進行位操作的與運算，最后可以得出一個 0 的結果，所以這個函數返回 false。 * [ ] SetBit 我們可以聲明 SetBit 的方法簽名為： ``` void SetBit(int[] array, long index); ``` 這個方法用于將 array 位數組中 index 位上的比特位設置為 1。 根據前面的介紹，獲取比特位所在的元素以及比特位在元素中的位置公式，核心的算法如下： ``` void SetBit(int[] array, int index) { ... int elementIndex = index / 32; int position = index % 32; long flag = 1; flag = flag << position; array[elementIndex] | flag; } ``` 我們用下面這個位數組來驗證一下，假設這個位數組的值如下圖所示：  如果調用了 SetBit(d, 35) 這條語句，我們將得到 elementIndex 為1、position 為 3、flag 為 0x08，將 d[1] 和 0x08 進行位操作的或運算，設置完之后位數組的狀態如下圖所示  * [ ] ClearBit 我們可以聲明 ClearBit 的方法簽名為： ``` void ClearBit(int[] array, long index); ``` 這個方法用于將 array 位數組中 index 位上的比特位設置為 0。 根據前面的介紹，獲取比特位所在的元素以及比特位在元素中的位置公式，核心的算法如下： ``` void ClearBit(int[] array, int index) { ... int elementIndex = index / 32; int position = index % 32; long flag = 1; flag = ~(flag << position); array[elementIndex] & flag; } ``` 我們用下面這個位數組來驗證一下，假設這個位數組的值如下圖所示：  如果調用了 ClearBit(d,32) 這條語句，我們將得到 elementIndex 為1、position 為 0、flag 為 0xFFFFFFFE，將 d[1] 和 0xFFFFFFFE 進行位操作的與運算，設置完之后位數組的狀態如下圖所示：  上面所介紹的三個位數組的函數操作時間復雜度都是 O(1)。 * [ ] Redis 中的 Bitmap 數據結構 在了解完位數組，以及我們自己實現了位數組的基本操作之后，我想和你介紹位數組在Redis中的應用。Redis 是一個開源的并且使用內存來作為存儲空間的高效數據庫，感興趣的同學可以到官網 https://redis.io 上查看相關文檔。 今天我想介紹的是在 Redis 里面的一個數據結構——Bitmap。Bitmap 在這里其實就是我們剛剛講解的位數組。 Bitmap 的本質其實是在 Redis 里面通過一個 Strings 類型來表示的。在 Redis 中，Strings 的最大長度可以是 512MB。  也就是說，根據上面的計算，Bitmap 可以用來表示大概 42 億多個狀態，這對于大多數的應用已經足夠了。 在 Redis 里面對 Bitmap 的操作命令有以下幾種：BITCOUNT、BITFIELD、BITOP、GETBIT、SETBIT。其中，GETBIT 和 SETBIT 命令和前面我們自己所實現的 GetBit 和 SetBit 操作原理是一樣的，感興趣的同學可以前往 GitHub 鏈接來查看 Redis 中 Bitmap 的源碼。 那回到這一講最開始的那個問題，如果想知道同時在 2019 年 11 和 12 月學習這個專欄的用戶有多少，可以做怎樣的優化呢？ 我們可以用 Redis 里的 BITCOUNT、SETBIT 和 BITOP 來完成。BITCOUNT 這個命令其實是可以計算一個位數組里有多少比特位是為“1”的，而 BITOP 可以針對位數組進行“與”、“或”、“非”、“異或”這樣的操作。 首先針對 11 月學習的用戶和 12 月學習的用戶，我們可以為它們創建單獨的位數組，例如，logins:2019:11 和 logins:2019:12。在 11 月，每當有用戶登錄學習時，程序會自動調用“SETBIT logins:2019:11 user_id 1”，同理，對于 12 月登錄學習的用戶，我們也可以調用“SETBIT logins:2019:12 user_id 1”。SETBIT命令可以將user_id在位數組中相應的位設為“1”。 當要獲得在這兩個月內同時都學習了這個專欄的用戶數時，可以調用“BITOP AND logins:2019:11-12 logins:2019:11 logins:2019:12”。將 logins:2019:11 和 logins:2019:12 這兩個位數組做位運算中的與操作，將結果存放在“logins:2019:11-12”這個位數組中。最后調用“BITCOUNT logins:2019:11-12”來得到結果。 Redis 的 Bitmap 操作之所以強大，是因為所有操作都是位運算以及發生在內存中，所以速度極快。 我們今天一起學習了位數組這個數組的高級概念以及自己實現了它的基本操作，同時通過實例了解了位數組在 Redis 中的應用。位數組這種數據結構可以極大地優化內存空間，當我們要表達的狀態只有true和false時，便可以考慮使用這種數據結構。 OK，這節課就講到這里啦，下一課時我將分享“鏈表基礎原理”，記得按時來聽課哈。 #### 課后問答 * 1、老師，這個redis里面bitmap數據類型strings是一創建類型就有個512m的空間呢，還是動態增長，最大512呢？另外例子中user_id是個整形類型的吧，如果是非整型的字符串呢？在這里這個user_id是bitmap數組的index吧？如果user_id起始值很大，是否浪費了很多空間呢？謝謝？ 講師回復： Redis的strings是動態增長 最大可以有512M，一般來說，處理id這種應用場景很少很少會用到非整數類型的。如果自己控制不了這個要求，可以通過hash function重新映射。這例子中為了方便講解，里面的user_id就是bitmap位數組的index，當然如果實際情況id的offset非常厲害，我們也可以同樣通過hash function重新映射到小一點的區間上。 * 2、假設一個對象有16種數據項，而每一種數據項都只有，是和否2種狀態，那么就可以用一個字符數組 char bitchar[2]={0,0}表示初始狀態。如果該對象其中某一個或者某幾個數據項的狀態為是，那么就修改對應的位為1，而此時bitchar中的數據值會發生相應的變化。這樣只需要一個字符數組就可以存儲該對象的16種狀態值。相應的如果該對象的16個數據項都用一個byte來存放的話，需要16個字節，所以位數組節省了14個字節內存。極大的節省了空間。而且所有操作都是位運算以及發生在內存中，所以速度極快。可以這樣理解嗎？ 講師回復： 是的，理解得完全正確，要保存16個狀態位需要兩個字節，可以像用戶的那樣聲明，也可以short[1]這樣聲明，只要最終數據在內存中占據16 bits就好 * 3、想問下在setbit和clearbit函數中，做完邏輯運算不需要把結果賦值給array中相應的elementindex元素么？？ 講師回復： 需要的，以SetBit(int[] array, int index)為例，這個函數的最后一個statement “array[elementIndex] | flag;”就是將結果賦予array中相應的元素。同理，clearbit函數中的最后一個statement中“array[elementIndex] & flag;”也是起到相應的作用。 * 4、Bitmap類型來表示的?為啥要用這個類型呢？ 講師回復： 這涉及到 Redis 底層的設計了，至于使用 Strings 類型的原因，建議看看 Redis 官方文檔里 Bitmaps 的介紹：https://redis.io/topics/data-types-intro?from=singlemessage&isappinstalled=0&scene=1&clicktime=1578364401&enterid=1578364401#bitmaps 簡單理解為：可以復用最簡單的 Strings 類型而不用再重新設計一個數據結構出來了。