有时，我们希望将数据(通常是原始字节)保存在单个连续的数组中，以便快速，轻松地进行访问，但是需要该数组可调整大小或者至少可扩展。 Java数组不可调整大小，因此仅使用数组是不够的。因此，要获得用于原始类型的可调整大小的数组，我们需要自己实现它。在本教程中，我将向我们展示如何在Java中实现可调整大小的数组。

为什么不使用ArrayList？

我们可能想知道为什么不能仅为此目的使用Java ArrayList。答案是，如果满足以下条件之一，则可以：

• 我们正在数组中存储某种对象类型。
• 我们将原始类型存储在数组中，而性能和内存使用情况无关紧要。

Java ArrayList类仅适用于不适用于基本类型(字节，整数，长整数等)的对象。如果我们使用Java ArrayList存储原始数据，则将其插入到ArrayList中后将自动装箱到一个对象中，并从该对象中取消装箱回到原始类型。这种装箱和拆箱会在尝试优化性能时增加不必要的插入和访问每个元素的开销(本文是Java Performance的一部分)。

此外，我们不能保证自动装箱的对象在内存中的存储位置。它们可以散布在整个堆中。因此，与以原始类型数组连续存储在内存中相比，对它们的连续访问要慢得多。

另外，将原语存储在其对象副本中(例如Long对象中的long)会导致每个元素显着的额外内存开销。

可调整大小的阵列用例

假设我们有一台服务器接收大小不同的邮件。有些邮件非常小(例如小于4KB)，另一些则高达1MB甚至更大。如果服务器从消息的开头看不到消息的大小，则无法为该消息预分配正确的内存量。另一种选择是"过度分配"，这意味着分配一个我们认为足以容纳消息的内存块。

如果服务器同时从多个(100K +)连接中接收消息，则需要限制为每个消息分配的内存量。我们不能只为每个消息缓冲区分配最大消息大小(例如1MB或者16MB等)。当连接和消息数量增加时，这将快速耗尽服务器内存！ 100.000 x 1MB = 100GB(大约不精确，但是我们得到了图片)。

另一种选择是从一个较小的缓冲区开始，如果该缓冲区的大小不足以容纳完整的消息，则我们将扩展该缓冲区。

阵列扩展很昂贵

要扩展数组，我们必须：

• 分配一个更大的新阵列。
• 将所有数据从旧阵列复制到新阵列。
• 取消分配旧数组。

这是一组昂贵的操作！尤其是，随着旧阵列的增大，将旧数据复制到新数据的成本越来越高。

请注意，在具有内置垃圾收集的语言(如Java，Cetc。)中，我们不必显式地取消分配旧数组，但是VM仍必须这样做，因此应用程序迟早仍要为解除分配付出代价。

最小化阵列扩展

为了最大程度地减少为数组扩展支付的价格，我们希望尽可能少地扩展数组，以使其足够大以容纳整个消息。

如果我们假设大多数消息很小，那么我们可以从一个小的缓冲区开始。如果消息增长到超出小缓冲区大小的范围，我们将分配一个新的中等大小的数组，然后将数据复制到新的中等大小的数组。如果消息也超出了中等大小的数组，则会分配一个大数组，然后将消息复制到该数组。大数组应为消息允许的最大大小。如果消息超出了大的消息缓冲区，则该消息太大而无法处理，应被服务器拒绝。

使用此策略，大多数邮件将仅使用较小的缓冲区。这意味着可以更有效地使用服务器内存。 100.000 x 4KB(较小的缓冲区大小)只有400MB。大多数服务器应该能够处理该问题。即使是4GB(1.000.000 x 4KB)的现代服务器也应该能够处理它。

可调整大小的阵列设计

可调整大小的数组设计为包含两个组件：

• ResizableArray
• ResizableArrayBuffer

" ResizableArrayBuffer"包含一个大数组。该数组分为三个部分。一节用于小型阵列，一节用于中型阵列，一节用于大型阵列。

" ResizableArray"表示单个可调整大小的数组，其数据存储在" ResizableArrayBuffer"中的数组中。

这是将大阵列划分为多个部分，并将每个部分划分为多个块的示意图。

通过为每个消息大小间隔(小，中，大)在ResizableArrayBuffer中保留大数组的区域，我们确保数组不能被任何大小的消息完全填充。例如，接收大量小消息无法占用所有内存，因此会阻塞中型和大型消息。同样，接收大量大邮件不会占用所有内存，也不会阻塞中小型邮件。

由于所有消息都是从小消息开始的，因此，如果小数组的数量已用完，则无论中大数组部分中是否有空间，都无法分配新的数组。但是，可以使小阵列部分足够大，以使发生这种情况的可能性非常低。

即使小消息部分已被完全使用，仍然有可能将小消息变成大消息和大消息。

优化选项

一种可能的优化是仅使用单个块大小。因此，有时可能刚在需要扩展的块之后分配新分配的块。在这种情况下，我们无需将数据从旧阵列复制到新阵列。我们可以简单地"扩展"该块以包括两个分配的块，然后将新数据写入添加了第二个块的扩展块中。当可以将存储块"扩展"到下一个连续的块时，可以节省所有阵列数据的复制。

上述可能的优化的缺点是，在不可能扩展到下一个存储块的情况下，仍然需要复制数据。因此，我们只需很少的开销即可检查是否可以扩展。另外，如果我们使用较小的块大小，则可能需要比使用例如小，中和大块大小。

跟踪免费块

ResizableArrayBuffer内部的大数组分为三个部分。每个部分都分成较小的块。每个部分中的每个块都具有相同的大小。小消息部分中的块具有相同的小块大小。中等消息部分中的块具有相同的中等块大小。大消息部分中的块具有相同的大块大小。

当一个节中的所有块都具有相同的大小时，更容易跟踪已使用和未使用的块。我们可以简单地使用包含每个块的起始索引的队列。共享阵列的每个部分都需要一个队列。因此，需要一个队列来跟踪空闲的小块，一个队列用于空闲的中型块，一个队列用于空闲的大块。

通过从与所需节段关联的队列中获取下一个空闲块开始索引，可以简单地从任何节段分配一个块。释放块是通过将起始索引放回相应的队列中来完成的。

作为队列，我使用了一个简单的环形缓冲区实现。 GitHubRepository中使用的实现称为" QueueIntFlip"。

写时扩展

当我们向数组中写入数据时，Resizable数组将自行扩展。如果我们尝试向其写入的数据超出其当前分配的块中的空间，它将分配一个更大的新块并将所有数据复制到该新块中。然后释放先前的较小块。

释放数组

一旦完成了可调整大小的数组操作，就应该再次释放它，以便可以将其用于其他消息。

使用ResizableArrayBuffer

我想向我们展示如何使用ResizableArrayBuffer(来自GitHub存储库)。

创建一个ResizableArrayBuffer

首先，我们必须创建一个" 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);

这个例子创建了一个" ResizableArrayBuffer"，它的小数组大小为4KB，中数组大小为128KB，大数组大小为1MB。 " ResizableArrayBuffer"包含1024个小型阵列(总计4MB)，32个中型阵列(总计4MB)和4个大型阵列(总计4MB)的空间，共享阵列大小为12MB。

获取ResizableArray实例

要获得ResizableArray实例，请调用ResizableArrayBuffer的getArray()方法，如下所示：

ResizableArray resizableArray = arrayBuffer.getArray();

这个例子获得了最小大小的" ResizableArray"(较小的大小设置为4KB)。

写入ResizableArray

我们可以通过调用它的write()方法来写入ResizableArray。 GitHub存储库中的ResizableArray类仅包含一个单独的write()方法，该方法以ByteBuffer作为参数。不过，自己添加更多的write()方法应该很容易。

这是一个写示例：

ByteBuffer byteBuffer = ByteBuffer.allocate(1024);

for(int i=0; i < 1024; i++){
    byteBuffer.put((byte) i);
}
byteBuffer.flip():

int bytesCopied = resizableArray.write(byteBuffer);

本示例将" ByteBuffer"的内容复制到" ResizableArray"的数组(块)中。 write()返回的值是从ByteBuffer复制的字节数。

如果ByteBuffer包含的数据多于ResizableArray，则ResizableArray会尝试扩展自身以为ByteBuffer中的数据腾出空间。如果ResizableArray在将自身扩展到最大大小后不能在ByteBuffer中包含所有数据，则write()方法将返回-1并且根本没有数据被复制！

从ResizableArray读取

当我们从ResizableArray中读取时，我们将直接在所有ResizableArray实例共享的共享数组中进行读取。 ResizableArray包含以下公共字段：

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

" sharedArray"字段引用共享数组，所有" ResizableArray"实例会将其数据保存在该共享数组中。该数组也内部保留在" ResizableArrayBuffer"中。

" offset"字段包含共享数组中的起始索引，该" ResizableArray"用于保存其数据(分配给它的块)。

"容量"字段包含分配给此" ResizableArray"实例的共享阵列中块的大小。

"长度"字段包含" ResizableArray"实际使用的已分配块的数量。

要读取写入" ResizableArray"的数据，只需将字节从" sharedArray [offset]"读取到" sharedArray [offset + length -1]"即可。

释放一个ResizableArray

使用完ResizableArray实例后，应该释放它。我们只需在ResizableArray上调用free()方法即可，如下所示：

resizableArray.free();

调用free()会确保将使用过的块返回到正确的块队列，而与分配给ResizableArray的块的大小无关。

设计上的变化

我们可以更改我的ResizableArrayBuffer的设计以满足需求。例如，我们可以其中创建3个以上的部分。它应该很容易做到。只需查看GitHub存储库中的代码并进行修改即可。