有時(shí)我們希望將把數(shù)據(jù)保存在單個(gè)連續(xù)的數(shù)組中，以便快速、便捷地訪問數(shù)據(jù)，但這需要調(diào)整數(shù)組大小或者對其擴(kuò)展。Java 數(shù)組不能調(diào)整大小，只用數(shù)組不足以達(dá)成目標(biāo)�？勺冮L原始類型數(shù)組需要自己實(shí)現(xiàn)。本文將展示如何實(shí)現(xiàn) Java 可變長數(shù)組。

　　為什么不用 ArrayList?

　　要滿足文章開頭的需求，為什么不使用 Java ArrayList?如果滿足下面條件之一，可以使用 ArrayList：

　　在數(shù)組中存儲(chǔ)某種對象類型;

　　在數(shù)組中存儲(chǔ)原始類型，沒有特別的性能或內(nèi)存要求。

　　Java ArrayList 類只適用于對象，不適合原始類型(byte、int、long等)。使用 ArrayList 存儲(chǔ)原始類型數(shù)據(jù)，插入 ArrayList 時(shí)會(huì)自動(dòng)裝箱為對象中，從中取出時(shí)會(huì)進(jìn)行拆箱轉(zhuǎn)為原始類型。裝箱和拆箱在插入元素和訪問元素時(shí)會(huì)帶來額外開銷，在嘗試針對性能進(jìn)行優(yōu)化時(shí)，應(yīng)該避免這些開銷(本文是 Java 性能跟蹤的一部分)。

　　不僅如此，這種方式無法確定自動(dòng)裝箱對象在內(nèi)存中的存儲(chǔ)位置。很可能分散存儲(chǔ)在堆中各個(gè)位置。因此，與原始類型數(shù)組相比訪問速度要慢得多，前者在內(nèi)存中連續(xù)存儲(chǔ)。

　　另外，原始類型裝箱會(huì)帶來額外的內(nèi)存開銷，例如 long 會(huì)存到 Long 對象。

　　本文源代碼

　　本文實(shí)現(xiàn)的 Java 變長數(shù)組源代碼可以在 GitHub 下載：

　　github.com/jjenkov/java-resizable-array

　　代碼包含三個(gè) Java 類和兩個(gè)單元測試。

　　可變長數(shù)組用例

　　假設(shè)有一臺(tái)服務(wù)器接收大小不同的郵件。其中有些郵件很小(小于4KB)，另一些很大(1MB 甚至更大)。

　　如果服務(wù)器同時(shí)從多個(gè)(10萬多個(gè))連接接收消息，那么需要為每個(gè)消息限制預(yù)分配內(nèi)存。每個(gè)緩沖區(qū)不能只按最大值(1MB或16MB)分配內(nèi)存。當(dāng)連接和消息數(shù)量增加時(shí)，這種方式會(huì)快速耗盡服務(wù)器內(nèi)存!100_000 x 1MB = 100GB(這是估計(jì)值，幫助問題理解)。

　　假設(shè)大多數(shù)消息比較小，一開始可以使用較小的緩沖區(qū)。如果消息超出緩存大小，則分配一個(gè)更大的新數(shù)組，并把數(shù)據(jù)拷貝到該數(shù)組中。如果消息超出分配的新數(shù)組，接著分配一個(gè)比之前更大的數(shù)組，并把消息復(fù)制到該數(shù)組。

　　使用這種策略，大多數(shù)消息通常只會(huì)存入小數(shù)組。這意味著服務(wù)器內(nèi)存得到了更有效的利用。100_000 x 4KB (小緩沖) = 400MB大多數(shù)服務(wù)器應(yīng)該能夠正常處理。即使是 4GB (1_000_000 x 4KB)，現(xiàn)在的服務(wù)器也能滿足要求。

　　可變長數(shù)組設(shè)計(jì)

　　可變長數(shù)組包含兩個(gè)組件：

　　ResizableArray

　　ResizableArrayBuffer

　　ResizableArrayBuffer 包含一個(gè)大數(shù)組。該數(shù)組被劃分為三個(gè)部分。一段用作小數(shù)組，一段用作中數(shù)組，一段用作大數(shù)組。ResizableArray類表示一個(gè)可變長數(shù)組，底層數(shù)據(jù)存儲(chǔ)在ResizableArrayBuffer中。

　　通過為小、中、大不同類型數(shù)據(jù)預(yù)留空間，ResizableArrayBuffer 能夠確保不會(huì)被某種大小的數(shù)據(jù)塞滿。例如，小數(shù)據(jù)不會(huì)占用數(shù)組的所有內(nèi)存，進(jìn)而阻斷中型和大數(shù)據(jù)存儲(chǔ)。同樣，接收大數(shù)據(jù)也不會(huì)占用所有內(nèi)存，進(jìn)而阻斷小數(shù)據(jù)和中型數(shù)據(jù)存儲(chǔ)。

　　由于底層存儲(chǔ)以小數(shù)據(jù)開始，如果小數(shù)組存儲(chǔ)空間耗盡，那么無論中數(shù)組或大數(shù)組是否還有空間，都無法分配新的數(shù)組�？梢宰屖剐�數(shù)組足夠大，減小發(fā)生這種情況的可能性。

　　即使小數(shù)組已經(jīng)全部用完，仍然可以把小數(shù)據(jù)變成中型和大型數(shù)據(jù)。

　　優(yōu)化方案

　　一種優(yōu)化方案：只用一個(gè)存儲(chǔ)塊。需要的時(shí)候在待擴(kuò)展的塊后面直接分配新塊。這樣不需要把數(shù)據(jù)從舊數(shù)組拷貝到新數(shù)組，可以直接“擴(kuò)展”存儲(chǔ)塊容納舊數(shù)據(jù)和新數(shù)據(jù)，新數(shù)據(jù)直接寫入新增的第二個(gè)擴(kuò)展塊即可。這樣避免了拷貝所有數(shù)組數(shù)據(jù)的情況。

　　上述優(yōu)化的缺點(diǎn)在于，如果無法擴(kuò)展下一個(gè)內(nèi)存塊仍然需要拷貝數(shù)據(jù)。因此需要加入“可擴(kuò)展”檢查，這個(gè)操作開銷不大。此外，如果存儲(chǔ)塊大小設(shè)置過小，在小數(shù)據(jù)、中等數(shù)據(jù)和大數(shù)據(jù)都存在的情況下會(huì)出現(xiàn)頻繁擴(kuò)展。