親愛的小屋客人，昨天小夕將小屋的討論室重新裝修啦！希望您會喜歡哦~除了口令[d]，現在也可以通過主頁下方的“喵了個咪”進入討論室啦。

ps：昨天小夕裝修討論室的時候發生了N次差點吐血的事件，明天小夕與大家含淚分享T_T。

在上一篇文章中，小夕為大家講解了鏈表與遞增式擴容的姿勢，而這一篇，將會是本系列文章的高潮哦（不！要！污！）

源于數組

上篇文章中，小夕為了避免大家理解起來抽象，讓大家注意了幾個數據結構：

如果您是C++程序喵，那么請注意一下Vector數據結構；如果是Java程序喵，請注意一下ArrayList、LinkedList、哈希系列(HashSet/ HashTable/ HashMap)；如果是不用Java也不用C++的程序喵，或者是已經脫離XX編程語言層次的程序喵，那么請注意一下可變數組（可增長順序表）、鏈表、哈希（散列）。

上篇文章中小夕講解了基于鏈表實現的數據結構都是遞增式擴容最優。那么對于C++中的Vector，Java中的ArrayList、HashSet/ HashTable/ HashMap，也就是數據結構中的可變數組、哈希來說，空間增長方式是怎樣呢？可能有可愛的讀者寶寶此時在想“天吶，這些數據結構又特喵的不一樣，怎么放到一起討論了呢？”好啦，讓小夕碾壓這些讀者寶寶吧（小夕再次跑路）！其實這些表面看似不同的東西，底層的實現方式確是一樣的，它們在底層都是通過操縱靜態數組來實現他們的動態空間增長功能，下文會詳細介紹哦。

講到這里，可能愛思考的讀者寶寶會記得小夕在上一篇中也提到過哈希，說哈希的橫向增長是基于鏈表的，因此遞增式擴容是最優動態空間增長方案。那這一篇中又說哈希是基于靜態數組的，這是怎么回事呢？下面給沒有接觸過哈希的讀者寶寶先科普一下哈希：

哈希的橫向增長是基于鏈表實現的，即當新元素的哈希值與已有元素哈希值相同時，新元素會插入到某個鏈表中，因此是遞增式增長。但是更多的情況下，哈希是縱向增長的。學過數據結構的寶寶知道，哈希在縱向上就是一個指針數組，數組的每個索引值即代表一個哈希值，數組的每個元素是一個指向某鏈表的指針。畫個圖來看就是這樣的。

所以，在本篇文章中，我們不看哈希的橫向增長啦，就看豎著的，也就是縱向增長，此時顯然是基于靜態數組實現的哦。

下面小夕直接以“數據結構”代稱所有這些基于靜態數組實現的動態空間分配的數據結構，包括但不限于C++中的Vector（即數據結構中的動態數組），Java中的ArrayList（即動態數組）、Hash系列（即哈希/散列）等~

具體來說，如何用靜態數組實現上述的動態空間增長的數據結構呢？其實很簡單，每次數據結構要擴容時只需要依次進行下述操作就完成啦：

開辟一段新的內存空間，空間大小就是擴容后的數據結構大小。

把舊數據結構，也就是舊的內存空間的元素一個個的復制到新的內存空間

釋放舊的內存空間（代碼上就是刪除舊空間的指針，當然像Java這種自動管理內存的語言就不用程序喵操心這一步了）

通過上述擴容的三步操作，可以看到每次哈希表的擴容操作的代價還是挺大的。第1步和第3步的代價不算大，但是第2步的代價會隨著要搬移元素數量的增加而直線上升。所以這就相當于一個完整搬家的過程：先買個新房子，再把舊房子里的全部家當搬到新房子里去，再把舊房子注銷，你說麻不麻煩喵=￣ω￣=

加倍式擴容

既然代價如此之大，那么顯然我們要盡量減小擴容次數呀~每次擴容都是大出血...怎么擴呢？一個很creative的想法就是每次使數據結構變為自身的兩倍！再機智一點，每次使數據結構變為自身的N倍！其中N只要大于1就可以！這種每次使自身的大小變為之前N倍的數據結構動態空間增長方式稱為【加倍式擴容】。實際上，在基于靜態數組的數據結構的動態空間增長問題上，加倍式擴容遠遠優于遞增式擴容。口說無憑，待小夕用萌味算法分析來證明！

假如數據結構A使用【遞增式擴容】。每次數據結構滿了的時候就固定的增加10個單位的空間（增加單位的數量不會影響最終分析出來的復雜度哦）。好，那小夕現在手里有n個元素想添加進數據結構，假如n的數值很大，遠遠的大于10，那么要執行多少次擴容操作呢？當然是n/10次啦~這n/10次擴容的累計開銷大約為cost=10+2*10+3*10+…+(n/10)*10，計算一下這個級數，就是cost=[(n/10)/2]*[(n/10)+1]*10,所以復雜度是O(n²)的數量級，所以平均每個元素被添加進哈希表時的開銷為cost/n，也就是O(n)的復雜度。

?

假如數據結構B使用【加倍式擴容】。每次數據結構滿了的時候，數據結構的大小就變成原來的2倍（與之前同樣的，這個倍數取不同的值并不會影響最終分析出來的復雜度哦~當然倍數必須大于1！）。同樣，小夕將n個元素添加進數據結構，假如n的數值很大，遠遠的大于2，那么要執行的擴容操作的次數是…小夕去算一會...嗯…應該是log₂n！令c=log₂n，則這c次擴容操作的累計開銷為cost=2¹+2²+…+2^c。這個級數的和為cost=[2/(1-2)]*(1-2^c)，代入c=log₂n得cost=2(n-1)。也就是說復雜度為O(n)，所以平均每個元素被添加進哈希表時的開銷為cost/n，也就是O(1)的復雜度！注意前面我們計算過，這里數據結構A（遞增式擴容）的復雜度為O(n)!

怎么樣~小夕說的沒錯吧，讀者寶寶有沒有撥開云彩見到日呢(￣?￣)。所以說呀，正是因為這類數據結構采用了加倍式擴容，導致這類數據結構申請內存的時候翻倍翻倍的要。結果當時在那個機器學習任務中，小夕算的是一個超大哈希表只需要占用5個G作右的內存空間，而實際上在往這個哈希表加數據時，從4個G直接爆到了接近8個G，導致小夕內存8G的小電腦直接崩盤了~

等等，看似此文可以結了，實際上，敏銳的讀者寶寶可能想到了，“遞增式擴容你都告訴我了每次擴容增加一個單位的空間就最優了，那加倍式擴容每次增大幾倍最優呢？”如果讀者寶寶能發現這一點的話，真的非常棒啦！答案是2倍嗎？當然不！那是幾呢？下篇萌貨（萌味干貨的簡稱）見分曉(￣?￣)。

啊啊，高潮果然是最累的（我說文章的高潮啊喂~），小夕好累喵(′Д` )。所以親愛的讀者寶寶是不是有一種抑制不住要鼓勵小夕的沖動吖(?????????)

小夕已委托維權騎士對小夕發布文章的版權行為進行追究與維權。如需轉載，請聯系微信xiyaomengmengda。

總結

以上是生活随笔為你收集整理的【萌味】小夕说,不了解动态空间增长的程序喵都是假喵（中）的全部內容，希望文章能夠幫你解決所遇到的問題。

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