來自：ImportNew/覃佑樺 | 責(zé)編：樂樂
鏈接：tutorials.jenkov.com/java-performance/resizable-array.html

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

為什么不用 ArrayList？

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

• 在數(shù)組中存儲(chǔ)某種對(duì)象類型；

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

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

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

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

本文源代碼

本文實(shí)現(xiàn)的 Java 變長(zhǎng)數(shù)組源代碼可以在 GitHub 下載：github.com/jjenkov/java-resizable-array

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

可變長(zhǎng)數(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ù)器也能滿足要求。

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

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

• ResizableArray

• ResizableArrayBuffer

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

下圖展示了數(shù)組分為三段，每段再分為小塊。

通過為小、中、大不同類型數(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ò)展。

跟蹤空閑塊

ResizableArrayBuffer 內(nèi)部的大數(shù)組同樣分為三段。每段都被分為更小的存儲(chǔ)塊；每段中的存儲(chǔ)塊大小相同；小數(shù)組中的存儲(chǔ)塊大小相同；中型數(shù)組中的存儲(chǔ)塊大小相同；大數(shù)組中的存儲(chǔ)塊大小相同。

每段中的存儲(chǔ)塊大小相同可以更方便地追蹤塊使用狀態(tài)。可以使用隊(duì)列記錄每個(gè)塊的起始索引。還需要一個(gè)隊(duì)列記錄每段中的共享數(shù)組。最終，一個(gè)隊(duì)列來跟蹤空閑小數(shù)據(jù)塊，一個(gè)隊(duì)列用記錄空閑的中型數(shù)據(jù)塊，一個(gè)隊(duì)列用于空閑的大數(shù)據(jù)塊。

根據(jù)數(shù)據(jù)類型從響應(yīng)隊(duì)列獲取下一個(gè)空閑塊起始索引，可以實(shí)現(xiàn)從任意數(shù)據(jù)段分配存儲(chǔ)塊。把起始索引放回相應(yīng)隊(duì)列可以釋放數(shù)據(jù)塊。

這里我用簡(jiǎn)單的環(huán)形緩沖區(qū)實(shí)現(xiàn)隊(duì)列。GitHub 倉庫對(duì)應(yīng)的代碼為 QueueIntFlip。環(huán)形緩沖區(qū)教程：tutorials.jenkov.com/java-performance/ring-buffer.html

擴(kuò)展寫

向數(shù)組寫數(shù)據(jù)時(shí)，可變長(zhǎng)數(shù)組自動(dòng)擴(kuò)展。如果嘗試向數(shù)組寫入的數(shù)據(jù)超出當(dāng)前分配的存儲(chǔ)空間，將分配一個(gè)新的更大的存儲(chǔ)塊并把所有數(shù)據(jù)拷貝到新塊中，然后釋放之前較小的存儲(chǔ)塊。

釋放數(shù)組

一旦可變長(zhǎng)數(shù)組完成了大小調(diào)整，應(yīng)該對(duì)其進(jìn)行釋放以便可以接收其他消息。

使用 ResizableArrayBuffer

下面展示如何使用 GitHub 中 ResizableArrayBuffer。

創(chuàng)建一個(gè) ResizableArrayBuffer

首先，必須創(chuàng)建一個(gè) ResizableArrayBuffer。示例如下：

int?smallBlockSize??=????4?*?1024;?? int?mediumBlockSize?=??128?*?1024;?? int?largeBlockSize??=?1024?*?1024;??int?smallBlockCount??=?1024;?? int?mediumBlockCount?=???32;?? int?largeBlockCount??=????4;??ResizableArrayBuffer?arrayBuffer?=??new?ResizableArrayBuffer(??smallBlockSize?,?smallBlockCount,??mediumBlockSize,?mediumBlockCount,??largeBlockSize,??largeBlockCount);

這個(gè)例子創(chuàng)建的 ResizableArrayBuffer 包含一個(gè)4KB小數(shù)組，128KB中數(shù)組和1MB大數(shù)組。ResizableArrayBuffer存儲(chǔ)空間包含1024個(gè)小數(shù)組（共4MB）、32個(gè)中數(shù)組（共4MB）和4個(gè)大數(shù)組（共4MB），完整的共享數(shù)組大小總計(jì)12MB。

獲取 ResizableArray 實(shí)例

要得到 ResizableArray 實(shí)例，調(diào)用 ResizableArrayBuffer的getArray() 方法，如下所示：

ResizableArray?resizableArray?=?arrayBuffer.getArray();

這里得到一個(gè)最小的 ResizableArray（之前設(shè)置為4KB）。

向 ResizableArray 寫數(shù)據(jù)

調(diào)用 write() 方法向 ResizableArray 寫數(shù)據(jù)。GitHub 中 ResizableArray 類只包含一個(gè) write() 方法，其參數(shù)為 ByteBuffer。不過，可以根據(jù)需要自行添加更多 write() 方法。

下面是寫數(shù)據(jù)示例：

public?byte[]?sharedArray?=?null;?? public?int????offset??????=?0;?? public?int????capacity????=?0;?? public?int????length??????=?0;

上面的代碼把 ByteBuffer 內(nèi)容復(fù)制到 ResizableArray 數(shù)組中。Write() 返回從 ByteBuffer 拷貝的字節(jié)數(shù)。

如果 ByteBuffer 包含的數(shù)據(jù)超出了 ResizableArray 容量，這時(shí) ResizableArray 會(huì)嘗試擴(kuò)展,為 ByteBuffer 中的數(shù)據(jù)留出空間。如果 ResizableArray 即使擴(kuò)展到最大值也無法容納 ByteBuffer 中的所有數(shù)據(jù)，則 write() 方法返回-1，并且不會(huì)復(fù)制任何數(shù)據(jù)！

從 ResizableArray 讀數(shù)據(jù)

從 ResizableArray 中讀數(shù)據(jù)時(shí)，可以直接從 ResizableArray 所有實(shí)例中直接讀取共享數(shù)組。ResizableArray 包含以下 public 字段：

public?byte[]?sharedArray?=?null;?? public?int????offset??????=?0;?? public?int????capacity????=?0;?? public?int????length??????=?0;

• sharedArray 字段對(duì)應(yīng)所有 ResizableArray 實(shí)例中的共享數(shù)組,即ResizableArrayBuffer 的內(nèi)部數(shù)組。

• offset 字段對(duì)應(yīng)共享數(shù)組的起始索引，ResizableArray 在這里保存數(shù)據(jù)。

• capacity 字段包含分配給 ResizableArray 實(shí)例中的塊大小。

• length 字段包含 ResizableArray 實(shí)際使用的塊數(shù)量。

要讀取 ResizableArray 的寫入數(shù)據(jù)，只要讀取從sharedArray[offset] 到sharedArray[offset+ length -1] 的字節(jié)即可。

釋放 ResizableArray

一旦 ResizableArray 實(shí)例使用完畢應(yīng)該釋放。只要在 ResizableArray 上調(diào)用 free() 方法即可，如下所示：

resizableArray.free();

無論分配給 ResizableArray 塊大小如何，調(diào)用 free() 都能將使用的塊正確返還隊(duì)列。

變換設(shè)計(jì)

您可以根據(jù)自己的需要修改 ResizableArrayBuffer 設(shè)計(jì)。例如，可以在其中創(chuàng)建多于三個(gè)數(shù)據(jù)段。操作起來應(yīng)該也很容易,只要看 GitHub 中的源代碼進(jìn)行修改即可。

總結(jié)

以上是生活随笔為你收集整理的扫盲！Java可变长数组，看这篇就对了！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。