前言

本文改編自小夕的訂閱號文章《【萌味】小夕說，不瞭解動態空間增長的程式喵都是假喵（上）》、《【萌味】小夕說，不瞭解動態空間增長的程式喵都是假喵（中）》、《【萌味】小夕說，不瞭解動態空間增長的程式喵都是假喵（下）》。萌氣已過濾，需要呼吸萌氣的讀者請戳上面原文哦。

筆者學了資料結構後，知道了連結串列、樹、雜湊表等資料結構與靜態陣列的固定容量不同，它們是可以動態新增元素的。這種資料結構的初始大小可能很小，甚至幾乎為零，但是隨著新元素的加入，其大小（記憶體空間佔用）會不斷增長，這個過程就叫做動態空間增長。

那麼問題來了，所有支援動態空間增長的資料結構都是相同的增長方式嗎？瞭解這個又有什麼意義呢？

筆者曾經很傻很天真的認為所有支援動態空間增長的資料結構都是每增加一個元素，資料結構的大小就增加1個單位。直到在一箇中規模機器學習任務的資料預處理過程中遇到了“記憶體爆炸”的問題，即筆者明明計算的記憶體夠用，但是筆者可憐的電腦的記憶體卻意外爆滿了。這是怎麼回事呢？

筆者為了避免講解太過抽象，所以建議：如果您擅長C++，那麼請注意一下Vector資料結構；如果擅長Java，請注意一下ArrayList、LinkedList、雜湊系列（HashSet/ HashTable/ HashMap）；如果您不用Java也不用C++，或者已經脫離XX程式語言的層次，那麼請注意一下可變陣列（可增長順序表）、連結串列、雜湊（雜湊）。筆者將基於上述資料結構展開講解。

遞增式擴容

對於Java的LinkedList，也就是資料結構中的連結串列，其空間增長方式就是筆者一開始的設想：每增加一個元素，其大小就增加一個單位（這裡的一個單位就是指一個元素佔用的空間大小）。原因就在於連結串列在記憶體中的儲存可以是不連續的。例如一個依次由節點1、節點2、節點3連線而成的連結串列在計算機記憶體中完全有可能是下面的儲存方式。

這樣的話，連結串列每增加一個元素，只需要在記憶體中找個縫將新元素插進去就可以。所以如果筆者手裡有n個元素想插入連結串列，則需要開闢n次記憶體，每次均開闢一個元素的大小。

這種

資料結構建立後，每次資料結構要擴容時均增加固定空間大小的做法被稱為【遞增式擴容】

。顯然連結串列的空間增長方式就是遞增式擴容，而且遞增的單位為1（這裡是指1個單位，即一個結點的大小）。

可以看到，如果是連結串列資料結構，或者是底層基於連結串列而實現的資料結構，採用遞增式擴容是最優選擇。因為要增加一個元素，則最好的情況就是其他什麼都不動，僅僅是為該元素開闢一個單位的空間，然後塞入該元素。而遞增式擴容用於連結串列確實達到了這個最理想情況呢。

因此，對於連結串列，以及底層基於連結串列結構實現的資料結構，都是採用遞增式擴容即可達到最優擴容效率（最優動態空間增長）。

例如雜湊中的橫向增長，再如基於連結串列實現的樹（如Java中的TreeSet，TreeMap等）。

因此在操縱大量資料的時候，尤其機器學習任務中常見的操縱大量樣本的時候，在記憶體的問題上可以安心的使用此類資料結構，不會導致“記憶體爆炸”的問題，記憶體只會慢慢的起火然後輕輕的告訴你滿了。當然了，不能僅考慮記憶體，有時操縱大量資料時對資料處理效率要求更高，這時候就要舍記憶體保速度啦。

那麼哪些常見資料結構採用遞增式擴容無法達到最優呢？它們有什麼共性嗎？還有，小夕遇到的記憶體爆炸是怎麼回事呢？

源於陣列

那麼對於C++中的Vector，Java中的ArrayList、HashSet/ HashTable/ HashMap，也就是資料結構中的可變陣列、雜湊來說，空間增長方式是怎樣呢？可能有讀者此時在想“這些資料結構又不一樣，怎麼放到一起討論了呢？”

其實這些表面看似不同的東西，底層的實現方式確是一樣的，它們在底層都是

透過操縱靜態陣列來實現他們的動態空間增長功能

，下文會詳細介紹。

講到這裡，可能有讀者會記得筆者在上一篇中也提到過雜湊，說雜湊的橫向增長是基於連結串列的，因此遞增式擴容是最優動態空間增長方案。那這一篇中又說雜湊是基於靜態陣列的，這是怎麼回事呢？下面給沒有接觸過雜湊的讀者先科普一下雜湊：

雜湊的橫向增長是基於連結串列實現的，即當新元素的雜湊值與已有元素雜湊值相同時，新元素會插入到某個連結串列中，因此是遞增式增長。但是更多的情況下，雜湊是縱向增長的。學過資料結構的寶寶知道，雜湊在縱向上就是一個指標陣列，陣列的每個索引值即代表一個雜湊值，陣列的每個元素是一個指向某連結串列的指標。畫個圖來看就是這樣的。

所以，在本篇文章中，我們不看雜湊的橫向增長，只關注縱向增長，此時顯然是基於靜態陣列實現的。

基於陣列的擴容原理

下面筆者直接以“資料結構”代稱所有這些

都是採用遞增式擴容即可達到最優擴容效率（最優動態空間增長）。

資料結構，包括但不限於上文提到的C++中的Vector（即資料結構中的動態陣列），Java中的ArrayList（即動態陣列）、Hash系列（即雜湊/雜湊）等。

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

開闢一段新的記憶體空間，空間大小就是擴容後的資料結構大小。

把舊資料結構，也就是舊的記憶體空間的元素一個個的複製到新的記憶體空間

釋放舊的記憶體空間（程式碼上就是刪除舊空間的指標，當然像Java這種自動管理記憶體的語言就不用操心這一步了）

透過上述擴容的三步操作，可以看到每次雜湊表的擴容操作的代價還是挺大的。第1步和第3步的代價不算大，但是第2步的代價會隨著要搬移元素數量的增加而直線上升。所以這就相當於一個完整搬家的過程：先買個新房子，再把舊房子裡的全部家當搬到新房子裡去，再把舊房子登出。

加倍式擴容

既然代價如此之大，那麼顯然我們要儘量減小擴容次數。怎麼擴呢？一個很creative的想法就是每次使資料結構變為自身的兩倍！再機智一點，每次使資料結構變為自身的N倍！其中N只要大於1就可以！口說無憑，下面給出演算法分析的過程。

假如資料結構A使用【遞增式擴容】。每次資料結構滿了的時候就固定的增加10個單位的空間（增加單位的數量不會影響最終分析出來的複雜度哦）。好，那小夕現在手裡有n個元素想新增進資料結構，假如n的數值很大，遠遠的大於10，那麼要執行多少次擴容操作呢？當然是n/10次啦~這n/10次擴容的累計開銷大約為

計算一下這個級數，就是

所以複雜度是O（

）的數量級，所以平均每個元素被新增進雜湊表時的開銷為cost/n，也就是O（n）的複雜度。

假如資料結構B使用【加倍式擴容】。每次資料結構滿了的時候，資料結構的大小就變成原來的2倍（與之前同樣的，這個倍數取不同的值並不會影響最終分析出來的複雜度，當然倍數必須大於1！）。同樣，將n個元素新增進資料結構，假如n的數值很大，遠遠的大於2，那麼要執行的擴容操作的次數是log2n！令c=log2n，則這c次擴容操作的累計開銷為

這個級數的和為

代入c=log2n得cost=2（n-1）。也就是說複雜度為O（n），所以平均每個元素被新增進雜湊表時的開銷為cost/n，也就是O（1）的複雜度！注意前面我們計算過，這裡資料結構A（遞增式擴容）的複雜度為O（n）！

講到這裡讀者應該清楚了吧？所以如果有一天你要自己寫一個基於陣列的動態空間增長的資料結構的話，可千萬不要寫成遞增式擴容了。

記憶體爆炸

正是因為這類資料結構採用了加倍式擴容，導致這類資料結構申請記憶體的時候翻倍翻倍的要。結果當時在那個中規模機器學習任務中，筆者算的是一個超大雜湊表只需要佔用5個G作右的記憶體空間，而實際上在往這個雜湊表加資料時，從4個G直接爆到了接近8個G，導致筆者記憶體8G的小電腦直接崩盤了。

等等，看似此文可以結了，實際上，敏銳的讀者可能想到了：“遞增式擴容你都告訴我了每次擴容增加一個單位的空間就最優了，那加倍式擴容每次增大幾倍最優呢？”如果讀者能發現這一點的話，真的非常棒啦！答案是2倍嗎？當然不！那是幾呢？真的有最優倍率嗎？

一個視角：記憶體複用

如果倍率採用2甚至更大的數，那麼

基於靜態陣列實現的動態空間分配的

。小夕舉個栗子。

被開闢過的舊空間永遠都不會被新開闢的空間利用

那麼以下是小夕為大家畫的三次擴容後的記憶體塊的佔用情況

上圖中，記憶體塊一共有15個位元組。粉色實心框是資料結構佔用的記憶體塊，空心框是空閒的記憶體。

假如一開始資料結構的大小是1位元組，佔用了0xFF00這個位元組，如圖中第一列。然後第一次擴容後資料結構大小變成2位元組，無法利用之前的舊記憶體空間。

同樣，第二次擴容，第三次擴容後，資料結構的大小總是要比之前累計佔用的舊記憶體空間之和還要大，總是大1個位元組，所以永遠都無法重新利用之前的舊記憶體空間。

if(倍率≥2){

小夕還沒有探索出嚴謹的結論，讀者有思路可以跟小夕一起討論哦~

如果倍率改為比2大的數，結果是一樣的。有興趣的讀者可以自行畫畫圖~當然，數學好的喵喵不用畫圖也能證明出來的~（利用幾何級數的性質）

那麼無法複用舊記憶體空間，對應有程式與作業系統各有什麼影響呢？

}

比如倍率採用1。5。小夕再畫一下圖~

可以看到，第三次擴容後的新資料結構大小約為338B！而舊空間的大小是250+225=475>338，也就是說新的雜湊表可以挪到舊的記憶體空間了！記憶體得到了複用！

好咯，說到這裡，讀者應該懂了，對於加倍式擴容，倍率必須小於2才能複用記憶體。那麼為什麼預設值取1。5，而不是1。6，1。7呢？小夕查了很多資料，發現這是一個

if(倍率<2&&倍率>1){

（啟發式策略就是拍腦袋想出來的看似合理而沒有嚴謹理論依據的方法）。

一個疑問

啟發式策略

那麼既然看似倍率用1.5要優於2，為什麼C++中部分Vector的實現中卻採用2呢？

這就是理論與工程的不同之處。在工程中不僅要考慮記憶體複用這一個問題，還要考慮到

注：感謝@冒泡 指正，有的C++中Vector的實現採用的1.5倍。

。

關於浮點運算：此處感謝@謝天奇指正，小夕之前想當然了，深深抱歉！浮點運算速度不會因有效位的增加而降低，但一般來說浮點運算效率確實比整型運算的效率低。因此確實存在浮點運算問題，但若採用浮點數運算，計算浮點數時的速度在理論上是幾乎無變化的。

擴容速度也很好理解。大量資料時，2倍擴容速度會比1。5倍擴容速度少很多次擴容次數，因此效率會比1。5倍高很多。那麼當程式不怎麼看重記憶體複用，卻有大量資料待填入資料結構時，2倍是更合理的。

補充：關於雜湊的擴容倍率

該章節由@冒泡提供，對雜湊的擴容倍率的考慮不在上一章節討論範圍內。雜湊之所以採用2倍的擴容倍率（更準確的說雜湊的擴容倍率應採用2的冪次），是處於雜湊表元素找位置的角度考慮的。

下面引用@冒泡清晰的講解：

一般來說，hash表元素找位置的辦法是元素的hash值對錶大小取模

理論上表大小是個正數就可以，不過對於一般的數字，計算機的整數除法是很慢的

如果表大小是2的冪，則可以用位運算來代替除法，比如表大小為1024，則K%1024可以最佳化為K&0x3FF，速度就快很多，所以hash表大小最好保持為2的冪，因此擴容時候只能乘以2，或乘以2的冪

因為這個原因，java的hash表擴容，才是翻兩倍

So

雖然很多資料結構都是基於靜態陣列實現的動態空間增長，但是有的是上述提到的2倍的擴容倍率甚至更高，有的像Java中的ArrayList和C++中Vector的部分實現中則為1。5倍的擴容倍率。