在java中，一個int類型占4個字節，也就是32bit，我們用一個int數組來表示時 new int[32],總計占用內存大概32*32bit,如果說我們存放的海量數據，億萬級非常大，那么這些基本數據類型都不夠用的，則可以用int字節碼的每一位表示一個數字，比如int類型32位，可以存放0-31共32個數值，那么32個數字只需要一個int類型所占內存空間大小就夠了，這樣在大數據量的情況下會節省很多內存。

?一、位圖作用

存放海量數據，節省存儲空間有明顯優勢

二、位圖實現

一、思路分析

位圖的定義我們大概了解，就是通過定義一個整形數值后，將原本只表示1個數值的情況下，擴大了可以存放幾十個數及以上的結構，比如我們要存放0-63的數，共64個數，那么我們就定義一個long型變量，有8個字節，64位，二進制就是64位，那么每一位從左到右就可以表示0，1，2..,63，如果有數則可以賦值1 沒有則表示0 比如保存1，那么就是第二位賦值1 ，以此類推

下面我們演示下，傳遞一個數值，保存到一個long[] arr數組中，簡單了解下:

arr[0]存放的值： 0 - 63? ? ? ? ??

arr[1]存放的值： 64 - 127

arr[2]存放的值： 128 - 191

.....

num =4? 存放的位置就是 arr[0] 第一個元素 因為 num /64 = 0 ，元素二進制?00..10000 第五位賦值1

?二、代碼演示

package class05;import java.util.HashSet;public class Code02_BitMap2 {// 這個類的實現是正確的public static class BitMap {//定義long數組，一個元素可以存放64個數，因為long類型是8字節 64位private long[] bits;//定義數組長度，需要先給需要存儲的數集的最大值 (max+64/64) 表示需要多少個，如 max是63 那個得 1 只需一個元素就可以//如果是64 得 2，就需要2個元素 因為一個Long64位 存放0-63的數值， 接著是64-127public BitMap(int max) { bits = new long[(max + 64) >> 6];}/*保存數值1.num>>6 表示先將目標數值除以64 得到該數值是位于bits數組的第幾個，比如63 / 64 = 0 在bit[0] 64/64=1 bit[1]..2.num & 63 表示num % 64 , 即看在該元素的第幾位， 2的6次方=64 第7位1000000 所以可以知道求模后肯定余數是1-6位的數，那么與運算 111111 即 63 就能表示1-6的值，也就是余數，也就得到是位于該元素中的第幾位了 比如余數0 那么就是第一位 ，1 就是第二位... 確定了這個余數 即第幾位，那么我們就用 1l << 余數(1必須要為long型 1L 取值長度才不會越界，int是32位，所以右移63肯定位數不夠) 將1右移余數位，比如余數1 那么就1L右移一位，表示在這個位置標1了。3.前面得到了對應在第幾個元素中的第幾位，最后就是需要在這個元素的這個位置賦值1. 那么就是可以將元素位置bits[num >>6] =bits[num >>6] | (1L << (num & 64) 即或運算 前面得到的具體位置，有1 則表示1 所以就給元素的對于位置賦值1了*/public void add(int num) {bits[num >> 6] |= (1L << (num & 63));}/*刪除數值， 就是將對應的元素中的第幾位 將其1改成01.bits[num >> 6] 元素所在數組的元素， 1L << (num & 63) 64位元素中的第幾位 表示存放著num2.對1L << (num & 63) 取反， 就得到一個 1111...01111 即將存放位賦值0 其他為13.將取反后的數 與bits[num >> 6] 所在元素就行 與運算， 此時其他位都位1 與完元素不變，而num所在位是0 與完則為0，則表示將數組刪除*/public void delete(int num) {bits[num >> 6] &= ~(1L << (num & 63));}/*判斷數值是否包含，那么就是判斷 bits[num >> 6] 所在元素的(1L << (num & 63)) 所在位 進行與運算，(1L << (num & 63))所在位為1 其他位都為0 所以與運算后 如果為一 表示bits[num >> 6] 的所在位也是1 那么就返回true*/public boolean contains(int num) {return (bits[num >> 6] & (1L << (num & 63))) != 0;}}public static void main(String[] args) {System.out.println("測試開始！");int max = 10000;BitMap bitMap = new BitMap(max);HashSet<Integer> set = new HashSet<>();int testTime = 10000000;for (int i = 0; i < testTime; i++) {int num = (int) (Math.random() * (max + 1));double decide = Math.random();if (decide < 0.333) {bitMap.add(num);set.add(num);} else if (decide < 0.666) {bitMap.delete(num);set.remove(num);} else {if (bitMap.contains(num) != set.contains(num)) {System.out.println("Oops!");break;}}}for (int num = 0; num <= max; num++) {if (bitMap.contains(num) != set.contains(num)) {System.out.println("Oops!");}}System.out.println("測試結束！");}}

三、核心總結?

定義數組長度，需要先給需要存儲的數集的最大值 (max+64/64) 表示需要多少個，如 max是63 那個得 1 只需一個元素，如果是64 得 2，就需要2個元素 因為一個Long64位 存放0-63的數值， 接著是64-127

num>>6 表示先將目標數值除以64 得到該數值是位于bits數組的第幾個，比如63 / 64 = 0 在bit[0] 64/64=1 bit[1]

num & 63 表示num % 64 , 即看在該元素的第幾位， 2的6次方=64 第7位1000000 所以可以知道求模后肯定余數是1-6位的數，那么與運算 111111 即 63 就能表示1-6的值，也就是余數，也就得到是位于該元素中的第幾位了 比如余數0 那么就是第一位 ，1 就是第二位...

確定了這個余數 即第幾位，那么我們就用 1l << 余數(1必須要為long型 1L 取值長度才不會越界，int是32位，所以右移63肯定位數不夠) 將1右移余數位，比如余數1 那么就1L右移一位，表示在這個位置標1了。

保存數值，將對應位賦值1：前面得到了對應在第幾個元素中的第幾位，最后就是需要在這個元素的這個位置賦值1. 那么就是可以將元素位置bits[num >>6] =bits[num >>6] | (1L << (num & 64) 即或運算 前面得到的具體位置，有1 則表示1 所以就給元素的對于位置賦值1了

刪除數值，就是將對應的元素中的第幾位 將其1改成0 1.bits[num >> 6] 元素所在數組的元素， 1L << (num & 63) 64位元素中的第幾位 表示存放著num 2.對1L << (num & 63) 取反， 就得到一個 1111...01111 即將存放位賦值0 其他為1 3.將取反后的數 與bits[num >> 6] 所在元素就行 與運算， 此時其他位都位1 與完元素不變，而num所在位是0 與完則為0，則表示將數組刪除

判斷數值是否包含，那么就是判斷 bits[num >> 6] 所在元素的(1L << (num & 63)) 所在位 進行與運算，(1L << (num & 63)) 所在位為1 其他位都為0 所以與運算后 如果為一 表示bits[num >> 6] 的所在位也是1 那么就返回true

總結

以上是生活随笔為你收集整理的【算法数据结构初阶篇】：位图bitMap的全部內容，希望文章能夠幫你解決所遇到的問題。

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