我們先來(lái)看個(gè)簡(jiǎn)單的問(wèn)題簿寂。

假如給你20億個(gè)非負(fù)數(shù)的int型整數(shù)漾抬，然后再給你一個(gè)非負(fù)數(shù)的int型整數(shù) t ，讓你判斷t是否存在于這20億數(shù)中常遂，你會(huì)怎么做呢纳令？

有人可能會(huì)用一個(gè)int數(shù)組，然后把20億個(gè)數(shù)給存進(jìn)去克胳，然后再循環(huán)遍歷一下就可以了平绩。

想一下，這樣的話漠另，時(shí)間復(fù)雜度是O(n)捏雌，所需要的內(nèi)存空間

4byte * 20億，一共需要80億個(gè)字節(jié)笆搓，

大概需要8GB的內(nèi)存空間性湿，顯然有些計(jì)算機(jī)的內(nèi)存一次是加載不了這么這么多的數(shù)據(jù)的。

初步優(yōu)化

按照上面的做法满败，時(shí)間復(fù)雜度是O(n)肤频，內(nèi)存是8GB，實(shí)際上我們是可以把時(shí)間復(fù)雜度降低到O(1)的算墨。

例如我們可以這樣來(lái)存數(shù)據(jù)宵荒，把一個(gè)int非負(fù)整數(shù)n作為數(shù)組下標(biāo)，如果n存在净嘀，則對(duì)應(yīng)的值為1报咳，如果不存在，對(duì)應(yīng)的值為0面粮。例如數(shù)組arr[n] = 1少孝，表示n存在，arr[n] = 0表示n不存在熬苍。

那么稍走，我們就可以把20億個(gè)數(shù)作為下標(biāo)來(lái)存，之后直接判斷arr[t]的值柴底，如果arr[t] = 1婿脸，則代表存在，如果arr[t] = 0柄驻，則代表不存在狐树。這樣，我們就可以把時(shí)間復(fù)雜度降低到O(1)鸿脓。不過(guò)空間復(fù)雜度我們并沒(méi)有降低抑钟。還稍微大了點(diǎn)涯曲。

由于int非負(fù)整數(shù)一共有 2^31 個(gè)，所以數(shù)組的大小需要 2^32 這么大在塔。

這里可能有人說(shuō)也可以用HashSet來(lái)存啊幻件，時(shí)間復(fù)雜度也是近似O(1)。不過(guò)這里需要說(shuō)明的是蛔溃，HashSet里面存的必須是對(duì)象绰沥，也就是說(shuō)需要把int包裝成Integer，顯然一個(gè)對(duì)象的話是更花銷(xiāo)內(nèi)存的贺待，需要對(duì)象頭啊什么的.....

再次優(yōu)化

大家想一個(gè)問(wèn)題徽曲，對(duì)于一個(gè)數(shù)，實(shí)際上我們只需要兩種狀態(tài)麸塞，就是這個(gè)數(shù)存在和不存在這兩種可能秃臣。上面我們用1代表存在，用0代表不存在喘垂。

也就是說(shuō)甜刻，我們是可以不用int型的數(shù)組來(lái)存儲(chǔ)的绍撞，一個(gè)int型占用4個(gè)字節(jié)正勒，即32個(gè)二進(jìn)制位，一共可以表示40億多個(gè)狀態(tài)傻铣。用int型的來(lái)存兩個(gè)狀態(tài)章贞，多浪費(fèi)。

所以我們可以考慮用boolean型的來(lái)存的非洲，boolean貌似就占用一個(gè)字節(jié)(java中的boolena貌似是占用一個(gè)字節(jié))鸭限。而一個(gè)boolean有true和false兩種狀態(tài)，所以也是成立的两踏。這樣子的話占用的內(nèi)存就是2GB的內(nèi)存了败京。

這樣，就可以降低到之前的四分之1內(nèi)存了梦染。

最終優(yōu)化：bitmap

大家再想一個(gè)問(wèn)題赡麦，雖然boolean是表示兩種狀態(tài)，但是boolean實(shí)際上占用了8bit啊帕识，按道理8bit是可以表示128種狀態(tài)的泛粹。而被我們拿來(lái)表示兩個(gè)狀態(tài)，是否也有點(diǎn)浪費(fèi)了呢肮疗？

我們都知道晶姊，一個(gè)二進(jìn)制位，有0和1兩種狀態(tài)伪货，所以說(shuō)们衙，其實(shí)我們是可以用一個(gè)二進(jìn)制位來(lái)代表一個(gè)int型的數(shù)是否存在的钾怔。例如對(duì)于1，3蒙挑，5蒂教，7這四個(gè)數(shù)，如果存在的話脆荷，則可以這樣表示：

image

1代表這個(gè)數(shù)存在凝垛，0代表不存在。例如表中01010101代表1蜓谋，3梦皮，5，7存在桃焕，0剑肯，2，4观堂，6不存在让网。

那如果8，10师痕，14也存在怎么存呢溃睹？如圖，8胰坟，10因篇，14我們可以存在第二個(gè)字節(jié)里

image

以此類(lèi)推。這樣子笔横，我們又可以把內(nèi)存降低到之前的8分之一了竞滓。

這種采用一個(gè)二進(jìn)制位來(lái)存儲(chǔ)數(shù)據(jù)的方法，我們也叫做bitmap算法吹缔。

可能有人會(huì)問(wèn)商佑，假如我要添加一個(gè)數(shù)n，我知道它要存在第n個(gè)位那里厢塘，把第n個(gè)二進(jìn)制改為1茶没，可是我要怎么操作呢？

這個(gè)對(duì)于bitmap算法是如何存儲(chǔ)的俗冻，如何進(jìn)行增刪操作的礁叔，我會(huì)在之后的文章里講，這篇就大概介紹下bitmap算法迄薄。

Java中有自帶的bitmap實(shí)現(xiàn)琅关，今天我們就用Java中自帶的bitmap來(lái)做道題練練手。我們換道類(lèi)似題目吧，不知道你一眼是否就能想到用bitmap算法來(lái)做涣易。

題目描述：

現(xiàn)在有五十億個(gè)int類(lèi)型的正整數(shù)画机，要從中找出重復(fù)的數(shù)并返回。

判斷50億個(gè)數(shù)有哪些是重復(fù)和剛才上面那個(gè)判斷是否存在新症，其實(shí)是一樣的步氏。我們采用bitmap算法來(lái)做。不過(guò)這里50億個(gè)數(shù)徒爹，別人肯定是以文件流的形式給你的荚醒。這樣我們?yōu)榱?strong>方便，我們就假設(shè)這些數(shù)是以存在int型數(shù)組的形式給我們的隆嗅。

代碼如下：

public class Test {
    //為了方便界阁，假設(shè)數(shù)據(jù)是以數(shù)組的形式給我們的
    public static Set<Integer> test(int[] arr) {
        int j = 0;
        //用來(lái)把重復(fù)的數(shù)返回，存在Set里胖喳，這樣避免返回重復(fù)的數(shù)泡躯。
        Set<Integer> output = new HashSet<>();
        BitSet bitSet = new BitSet(Integer.MAX_VALUE);
        int i = 0;
        while (i < arr.length) {
            int value = arr[i];
            //判斷該數(shù)是否存在bitSet里
            if (bitSet.get(value)) {
                output.add(value);
            } else {
                bitSet.set(value, true);
            }
            i++;
        }
        return output;
    }
    //測(cè)試
    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);
    }
}

打印結(jié)果:

[3, 4]

當(dāng)然，bitmap算法的應(yīng)用不僅僅是節(jié)省內(nèi)存丽焊，它還有很多其他的優(yōu)點(diǎn)较剃。之后有機(jī)會(huì)就拿一些其他的應(yīng)用來(lái)寫(xiě)篇文章。

本次講解到此結(jié)束技健。如果喜歡写穴，可以分享給更多的小伙伴哦。

bitmap的存儲(chǔ)會(huì)在之后的文章講哦

完

獲取更多原創(chuàng)文章凫乖，可以關(guān)注下我的公眾號(hào)：苦逼的碼農(nóng)确垫，我會(huì)不定期分享一些資源和軟件等弓颈。后臺(tái)回復(fù)禮包送你一份時(shí)下熱門(mén)的資源大禮包帽芽。同時(shí)也感謝把文章介紹給更多需要的人。