我們先來看個簡單的問題。

假如給你20億個非負數的int型整數，然后再給你一個非負數的int型整數t,讓你判斷t是否存在于這20億數種，你會怎么做呢?

有人可能會用一個int數組，然后把20億個數給存進去，然后再循環遍歷以下就可以了。

想一下，這樣的話，時間復雜度是O(n),所需要的內存空間

4byte * 20億，一共需要80億個字節。

大概需要8GB的內存空間，顯然有些計算機的內存一次是加載不了這么多的數據的。

初步優化

? ?按照上面的做法，時間復雜度是O(n),內存是8GB，實際上我們是可以把時間復雜度降低到O(1)的。

? ?例如我們可以這樣來存數據，把一個int非負整數n作為數組下標，如果n存在，則對應的值為1，如果不存在，對應的值為0，例如數組arr[n]=1,表示n存在，arr[n]=0表示n不存在。

? ? 那么，我們就可以把20億個數作為下標來存，之后直接判斷arr[t]的值，如果arr[t]=1,則代表存在，如果arr[t]=0,則代表不存在。這樣，我們就可以把時間復雜度降低到O(1)。不過空間復雜度我們并沒有降低。還稍微大了點。

? ?由于int非負整數一共有2^31個，所以數組的大小需要2^31這么大。

? ?這里可能有人說也可以用HashSet來存啊，時間復雜度也是近似O(1)。不過這里需要說明的是，HashSet里面存的必須是對象，也就是說需要把int包裝成Integer，顯然一個對象的話是更花銷內存的，需要對象頭啊什么的…..

再次優化

大家想一個問題，對于一個數，實際上我們只需要兩種狀態，就是這個數存在和不存在這兩種可能。上面我們用1代表存在，用0代表不存在。

也就是說，我們是可以不用int型的數組來存儲的，一個int型占用4個字節，即32個二進制位，一共可以表示40億多個狀態。用int型的來存兩個狀態，多浪費。

所以我們可以考慮用boolean型的來存的，boolean貌似就占用一個字節(java中的boolena貌似是占用一個字節)。而一個boolean有true和false兩種狀態，所以也是成立的。這樣子的話占用的內存就是2GB的內存了。

這樣，就可以降低到之前的四分之1內存了。

最終優化:bitmap

大家再想一個問題，雖然boolean是表示兩種狀態，但是boolean實際上占用了8bit啊，按道理8bit是可以表示128種狀態的。而被我們拿來表示兩個狀態，是否也有點浪費了呢？

我們都知道，一個二進制位，有0和1兩種狀態，所以說，其實我們是可以用一個二進制位來代表一個int型的數是否存在的。例如對于1，3，5，7這四個數，如果存在的話，則可以這樣表示：

1代表這個數存在，0代表不存在。例如表中01010101代表1，3，5，7存在，0，2，4，6不存在。

那如果8，10，14也存在怎么存呢？如圖，8，10，14我們可以存在第二個字節里

以此類推。這樣子，我們又可以把內存降低到之前的8分之一了。

這種采用一個二進制位來存儲數據的方法，我們也叫做bitmap算法。

可能有人會問，假如我要添加一個數n，我知道它要存在第n個位那里，把第n個二進制改為1，可是我要怎么操作呢？

這個對于bitmap算法是如何存儲的，如何進行增刪操作的，我會在之后的文章里講，這篇就大概介紹下bitmap算法。

Java中有自帶的bitmap實現，今天我們就用Java中自帶的bitmap來做道題練練手。我們換道類似題目吧，不知道你一眼是否就能想到用bitmap算法來做。

題目描述：

現在有五十億個int類型的正整數，要從中找出重復的數并返回。

判斷50億個數有哪些是重復和剛才上面那個判斷是否存在，其實是一樣的。我們采用bitmap算法來做。不過這里50億個數，別人肯定是以文件流的形式給你的。這樣我們為了方便，我們就假設這些數是以存在int型數組的形式給我們的。

代碼如下：

public class Test {//為了方便，假設數據是以數組的形式給我們的public static Set<Integer> test(int[] arr) {int j = 0;//用來把重復的數返回，存在Set里，這樣避免返回重復的數。Set<Integer> output = new HashSet<>();BitSet bitSet = new BitSet(Integer.MAX_VALUE);int i = 0;While(i < arr.length) {int value = arr[i];//判斷該數是否存在bitSet里if (bitSet.get(value)) {output.add(value);} else {bitSet.set(value, true);}i++;}return output;}//測試public static void main(String[] args) {int[] t = {1,2,3,4,5,6,7,8,3,4};Set<Integer> t2 = test(t);System.out.println(t2);} }

? 打印結果:

[3,4]

?

當然，bitmap算法的應用不僅僅是節省內存，它還有很多其他的優點。之后有機會就拿一些其他的應用來寫篇文章。

本次講解到此結束。如果喜歡，可以分享給更多的小伙伴哦。

參考鏈接:

https://mp.weixin.qq.com/s?__biz=MzUxNzg0MDc1Mg==&mid=2247484151&idx=1&sn=259faf3159b7ad3ca221dc3685b116de&chksm=f99348e8cee4c1fe591fde5ee6df0f771eff4a4c1e88bfb861eb6b6aff9d1aff20e9f8d563bd&scene=21#wechat_redirect

總結

以上是生活随笔為你收集整理的《算法与数据结构专场》BitMap算法介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

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