假如要表示4個int數字：1，2，5，7，初步估計內存占用4 * 4byte（32bit） = 16byte，如果有10億個這樣的數字，那么內存占用是：
10億 * 4 / （102410241024）= 3.72G，這么大的數據如果做查找或者排序，內存吃不消。

看看用位圖如何解決這個問題：用bit來表示數字，0代表數字不存在，1代表存在，那么一個byte就可以表示8個數字，將這些byte組成一個數組，就可以表示很多數字：

如圖所示，1，2，5，7都可以放入數組的第一個byte中，即bytes[0]，10放入bytes[1]，22放入bytes[2]

計算數字n在的bytes數組中索引：
bytes_index(n) = n/8
（注意：整數除整數，結果還是取整，比如 3/8 = 0, 10/8 = 1, 22/8 = 2）

計算數字n在byte中的位置，取模：
position(n) = n%8，比如：5%8 = 5，22 % 8 = 6

給定byte數組及位置，反推數字大小：
bytes[2]，p6 => 2 * 8 + 6 = 22

之前一個int數字占用4byte（32位），現在只需要1位即可表示。10億個的數字所需的空間也大大減小：3.72G/32 = 119M
而且可以用多線程的方式去讀取，時間復雜度是O（M/N），M是bytes[]數組的大小，N 是線程大小

基于位的邏輯運算，可以用于打標的場景，比如角色、權限等

運算符說明：
|= 或等于
1 << p 將1向左移動p個位置，這樣第p位將變?yōu)?，剩余位置補零

位圖進行增，刪，以及是否存在的操作，都可以通過位運算進行，代碼如下：

package test;public class BitMap {/*** 存儲數據*/private byte[] bytes;/*** 位圖容量*/private int capacity;public BitMap(int capacity) {this.capacity = capacity;// 根據容量，初始化數組的長度this.bytes = new byte[(capacity/8)+1];}/*** 位圖中存入一個數字* @param num*/public void add(int num) {int index = num / 8;int position = num % 8;// 1左移p位后，第p位是1，然后按位做或運算，即可將指定byte的指定bit標記為1this.bytes[index] |= 1<<position;}/*** 位圖中刪除一個數字* @param num*/public void remove(int num) {int index = num / 8;int position = num % 8;// 1左移p位后，第p位是1，按位取反后，第p位是0，然后按位做與運算this.bytes[index] &= ~(1<<position);}/*** 位圖是否包含某個數字* @param num* @return*/public boolean contains(int num) {int index = num / 8;int position = num % 8;// 1左移p位后，第p位是1（剩余位全0），做與運算后，如果byte的p位也是1，那么結果一定不是0，否則是0return (this.bytes[index] & 1<<position) != 0;}public static void main(String[] args) {BitMap bitMap = new BitMap(1000);bitMap.add(34);bitMap.add(7);bitMap.add(235);System.out.println(bitMap.contains(6)); // falseSystem.out.println(bitMap.contains(34)); // truebitMap.remove(34);System.out.println(bitMap.contains(34)); // falseSystem.out.println(bitMap.contains(7)); // true}}

總結

以上是生活随笔為你收集整理的bitmap 位图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。