上篇我們講了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實際上指的是多少個bitarr = 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中是有很多優化的，并不會像我們上面實現的代碼一樣那么浪費空間資源。有興趣的可以研究下。

至于如何優化，我會在之后的文章講，盡情期待。覺得有幫助的話可以轉發分享給更多的小伙伴哦

參考鏈接:https://mp.weixin.qq.com/s?__biz=MzUxNzg0MDc1Mg==&mid=2247484157&idx=1&sn=0826f11852cbfe3043bfac22e4aff27c&chksm=f99348e2cee4c1f48862e5d7536e24f4517f3d88753f452f03a2096ff2e7ab113706b3e54652&scene=21#wechat_redirect

總結

以上是生活随笔為你收集整理的【算法与数据结构专场】BitMap算法基本操作代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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