上篇我們講了BitMap是如何對數據進行存儲的，沒看過的可以看一下【演算法與數據結構專場】BitMap演算法介紹

這篇我們來講一下BitMap這個數據結構的代碼實現。

回顧下數據的存儲原理

一個二進位位對應一個非負數n，如果n存在，則對應的二進位位的值為1，否則為0。

這個時候，我們的第一個問題：

我們在使用byte,int,short,long等這些數據類型在存儲數據的時候，他們最小的都要佔用一個位元組的內存，也就是8個bit，也就是說，最小的操作單位是8個bit。根本就沒有可以一個一個bit位操作的數據類型啊。

在Java的bitMaP實現中，它採用的是用一個long數據來進行存儲的。一個long佔用8個位元組，即64bit，所以一個long可以存儲64個數。例如 arr 是一個long 類型的數組，則 arr[0]可以存 0 ~ 63，arr[1]可以存64 ~127，以此類推。

不過，我們就採用byte數組的來存吧。一個byte佔用一個位元組，即8bit，可以存8個數字。

當然，你要採用long數組來存也可以。在實現上可以說是一樣的。

例如我們要存儲(1,3,5,7,8,10)時，他們的內存如下所示。

下面我們就來講講如何對一個一個位進行操作的。

如何向bitmap中添加一個數值

我們先來說說如何在bitmap中如何添加一個數值的問題，例如我們我們要添加n=14。

這個其實很簡單，我們先找到n在arr數組中的下標index，顯然index = 1。然後再找到n在arr[index]中的位置position，顯然這裡position = 6。

這裡還是可以很容易找出index和position的公式的。即

index = n / 8 = n >> 3。

position = n % 8 = n & 0x07。

接下來我們把1向右移動position個二進位位，然後把所得的結果和arr[index]做「或(or)」操作就可以了。如下圖

這裡有個需要注意的地方，在畫圖的時候，為了方便，我們是把左邊的位當作低位，右邊的位當作高位來算了。不過在實際的存儲中，左邊的才是存高位，而右邊的存的是低位。所以在我們的代碼實現中，我們所說的右移對應代碼的左移。

代碼實現

//添加數據的操作

public void add(int n){
//用>>的操作是，運算會比較快
 int index = n >> 3;
int position = n & 0x07;
//把1右移和做or操作兩步一起
 //即 << 對應上圖的右移，實際上<<是左移符。
 arr[index] |= 1 << position;
}

知道了add操作，其他的操作差不多類似。

當然，我們實現的add操作只是簡單的實現一下，假如你要嚴謹地實現的話，還是需要很多異常的判斷的。例如判斷這個數是否是非負數，判斷arr數組是否下標越界，進行容量的擴充等等。有興趣的可以嚴謹去實現一下。

刪除操作。

我們只需要把對應的二進位的1變成0就可以了。

我們可以把1右移(代碼中對應左移)後的結果取反，然後與arr[index]做「與」操作就可以了。代碼如下：

public void delete(int n){
int index = n >> 3;
int position = n & 0x07;
arr[index] &= ~(1 << position);
}

判斷是否存在操作

我們把1右移之後，把結果和arr[index]做「與」操作，如何結果不為0，則證明存在，否則就不存在。

public boolean contain(int n){
int index = n >> 3;
int position = n & 0x07;
return (arr[index] & (1 << position)) != 0;
}

三個最基本的操作代碼基本實現了。

希望大家能夠去實踐一下。

全部代碼：

public class BitMap {
private byte[] arr;
//容量，即最多能夠存多少個數據
 private int capacity;

public BitMap(int capacity) {
this.capacity = capacity;
//一個byte可以存8個數據，capacity實際上指的是多少個bit
 arr = new byte[(capacity / 8 + 1)];
}

//添加數據的操作

public void add(int n){
//用>>的操作是，運算會比較快
 int index = n >> 3;
int position = n & 0x07;
//把1右移和做or操作兩步一起
 //即 << 對應上圖的右移，實際上<<是左移符。
 arr[index] |= 1 << position;
}

public void delete(int n){
int index = n >> 3;
int position = n & 0x07;
arr[index] &= ~(1 << position);
}

public boolean contain(int n){
int index = n >> 3;
int position = n & 0x07;
return (arr[index] & (1 << position)) != 0;
}
}

問題

大家看了以上的代碼，有沒發現一些問題呢？

例如我們只在bitmap存儲1個數，並且存的數值是2000000000，我們就會在第2000000000個二進位把0改為1。也就是說arr數組的大小至少為2000000000/8+1。可是這時候前面的二進位位並沒有存數據，那不是超級超級浪費資源？

所以說，像我們上面的那種寫法可以說是暴力寫法，沒有經過任何優化，實際上，在Java自帶的bitMap中是有很多優化的，並不會像我們上面實現的代碼一樣那麼浪費空間資源。有興趣的可以研究下。

至於如何優化，我會在之後的文章講，盡情期待。

獲取更多原創文章，可以關注下我的公眾號：苦逼的碼農，我會不定期分享一些資源和軟體等。後台回復禮包送你一份時下熱門的資源大禮包，同時也感謝把文章介紹給更多需要的人

推薦閱讀：

相关文章