Bitmap 位圖 Java實作

一、結構思想

以 bit 作為存儲機關進行 0、1存取的資料結構。

可用作布爾值存取，比如給定第i位，該bit為1則表示true，為0則表示false。

二、使用場景及優點

适用于對布爾或0、1值進行（大量）存取的場景。

如：記錄一個使用者365天的簽到記錄，簽了為true，沒簽為false。若是以普通key/value資料結構，每個使用者都需要記錄365條，當使用者量很大時會造成巨大的空間開銷。

是以運用位圖的話，每天簽到記錄隻占1個位(bit)，一共就365位，則隻需48個位元組就能容納一個使用者一年的簽到記錄。

優點：

低空間開銷且高效的0、1存取方案

三、具體實作

實作源碼：https://github.com/SimpleIto/data_structure/blob/master/src/bitmap/Bitmap.java

主要考慮以下問題：

1. 用什麼實體結構存儲一系列bit？
2. 如何通過位操作高效的實作對指定bit的擷取、修改操作？（而不是通過字元串轉去轉來臃腫的實作）

解決思路：

1. Java中，使用 byte[] 位元組數組來存儲bit。 1 byte = 8 bit

2. 對于擷取操作

   思路：拿到目标bit所在的byte後，将其向右位移（并将高位置0），使目标bit在第一位，這樣結果值就是目标bit值。

   1) 通過 byte[index >> 3] （等價于byte[index/8]）取到目标bit所在的byte。

   2) 令 i = index&7（等價于index%8）得到目标bit在該byte中所在的位置。

   3) 為了将目标bit前面的高位置0（這樣位移後的值才等于目标bit本身）：需要建構到目标bit為止的低位掩碼，即 0b11111111 >>>(7 - i)，再與原byte做&運算。

   4) 最後将結果向右位移 i 位，使目标bit處在第一位，結果值即為所求。

3. 對于修改操作

   思路：根據設定值true或false的不同，分為兩種操作邏輯

   1) 如果value為true，則目标位應與1做“或”運算。需建構“目标位為1，其他為0”的操作數（因為實際操作的是byte，為了隻修改目标bit，而不影響其他位）

   2) 如果value為false，則目标位應與0做“與”運算。則需建構“目标位為0，其他為1”的操作數。

   3) 建構目标位為1其他位為0的操作數：1 << (index & 7)

轉載于:https://www.cnblogs.com/simpleito/p/10740288.html