小提示：小夕會將小屋的最新動態更新到小屋的布告欄哦，口令是【nb】（口令在訂閱號主界面直接回復即可使用）。 ? ? ? ? ?

小夕學了數據結構后，知道了鏈表、樹、哈希表等數據結構與靜態數組的固定容量不同，它們是可以動態添加元素的。這種數據結構的初始大小可能很小，甚至幾乎為零，但是隨著新元素的加入，其大小（內存空間占用）會不斷增長，這個過程就叫做動態空間增長。那么問題來了，所有支持動態空間增長的數據結構都是相同的增長方式嗎？了解這個又有什么意義呢？

前言

小夕曾經很傻很天真的認為所有支持動態空間增長的數據結構都是每增加一個元素，數據結構的大小就增加1個單位。直到在一個中規模機器學習任務的數據預處理過程中遇到了“內存爆炸”的問題，即小夕明明計算的內存夠用，但是小夕可憐的電腦的內存卻意外爆滿了。最終小夕在某大神的指導下才知道原來數據結構的容量還能是加倍加倍的擴！小夕瞬間感到自己的智商可能只剩23.333了。

作為程序喵，不能光講大道理。小夕為了避免講解太過抽象，如果您是C++程序喵，那么請注意一下Vector數據結構；如果是Java程序喵，請注意一下ArrayList、LinkedList、哈希系列(HashSet/HashTable/HashMap)；如果是不用Java也不用C++的程序喵，或者是已經脫離XX編程語言層次的程序喵，那么請注意一下可變數組（可增長順序表）、鏈表、哈希（散列）。小夕將基于上面這些程序喵肯定知道的東西來花式講解（哈？都不知道？報告老師，這里有一只假喵中的假喵！）。

由于文章過長（也就是說小夕的講解過于認真\(//?//)\），小夕將文章拆為三部分。萬一讀到停不下來，聽說交出小紅包，小夕就會出現哦(￣?￣)

遞增式擴容

對于Java的LinkedList，也就是數據結構中的鏈表，其空間增長方式就是小夕一開始的設想：每增加一個元素，其大小就增加一個單位（這里的一個單位就是指一個元素占用的空間大小）。原因就在于鏈表在內存中的存儲可以是不連續的。例如一個依次由節點1、節點2、節點3連接而成的鏈表在計算機內存中完全有可能是下面的存儲方式。

這樣的話，鏈表每增加一個元素，只需要在內存中找個縫將新元素插進去就好啦~所以如果小夕手里有n個元素想插入鏈表，則需要開辟n次內存，每次均開辟一個元素的大小。這種數據結構建立后，每次數據結構要擴容時均增加固定空間大小的做法被稱為【遞增式擴容】。顯然鏈表的空間增長方式就是遞增式擴容，而且遞增的單位為1（這里是指1個單位，即一個結點的大小）。

可以看到，如果是鏈表數據結構，或者是底層基于鏈表而實現的數據結構，采用遞增式擴容是最優選擇。因為要增加一個元素，則最好的情況就是其他什么都不動，僅僅是為該元素開辟一個單位的空間，然后塞入該元素。而遞增式擴容用于鏈表確實達到了這個最理想情況呢。因此，對于鏈表，以及底層基于鏈表結構實現的數據結構，都是采用遞增式擴容即可達到最優擴容效率（最優動態空間增長）。例如哈希中的橫向增長，再如基于鏈表實現的樹（如Java中的TreeSet，TreeMap等）。因此在操縱大量數據的時候，尤其機器學習任務中常見的操縱大量樣本的時候，在內存的問題上可以安心的使用此類數據結構，不會導致“內存爆炸”的問題，內存只會慢慢的起火然后輕輕的告訴你滿了，23333。當然了，不能僅考慮內存，有時操縱大量數據時對數據處理效率要求更高，這時候就要舍內存保速度啦。

?

那么哪些常見數據結構采用遞增式擴容無法達到最優呢？還有，小夕遇到的內存爆炸是怎么回事呢？敬請期待小夕明天的大作啦！

如果覺得小夕的講解幫到了或者萌到了您，記得用小紅包鼓勵小夕哦~小夕都要買不起返校車票了嚶嚶嚶...

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

總結

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

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