更多课程 选择中心

Java培训
达内IT学院

400-111-8989

Java可变长数组

  • 发布:Java培训
  • 来源:Java教程
  • 时间:2020-03-14 16:47

有时我们希望将把数据保存在单个连续的数组中,以便快速、便捷地访问数据,但这需要调整数组大小或者对其扩展。Java 数组不能调整大小,只用数组不足以达成目标。可变长原始类型数组需要自己实现。本文将展示如何实现 Java 可变长数组。

为什么不用 ArrayList

要满足文章开头的需求,为什么不使用 Java ArrayList?如果满足下面条件之一,可以使用 ArrayList:

在数组中存储某种对象类型;

在数组中存储原始类型,没有特别的性能或内存要求。

Java ArrayList 类只适用于对象,不适合原始类型(byte、int、long等)。使用 ArrayList 存储原始类型数据,插入 ArrayList 时会自动装箱为对象中,从中取出时会进行拆箱转为原始类型。装箱和拆箱在插入元素和访问元素时会带来额外开销,在尝试针对性能进行优化时,应该避免这些开销(本文是 Java 性能跟踪的一部分)。

不仅如此,这种方式无法确定自动装箱Java可变长数组对象在内存中的存储位置。很可能分散存储在堆中各个位置。因此,与原始类型数组相比访问速度要慢得多,前者在内存中连续存储。

另外,原始类型装箱会带来额外的内存开销,例如 long 会存到 Long 对象。

本文实现的 Java 变长数组源代码可以在 GitHub 下载:

github.com/jjenkov/java-resizable-array

代码包含三个 Java 类和两个单元测试。

可变长数组用例

假设有一台服务器接收大小不同的邮件。其中有些邮件很小(小于4KB),另一些很大(1MB 甚至更大)。

如果服务器同时从多个(10万多个)连接接收消息,那么需要为每个消息限制预分配内存。每个缓冲区不能只按最大值(1MB或16MB)分配内存。当连接和消息数量增加时,这种方式会快速耗尽服务器内存!100_000 x 1MB = 100GB(这是估计值,帮助问题理解)。

假设大多数消息比较小,一开始可以使用较小的缓冲区。如果消息超出缓存大小,则分配一个更大的新数组,并把数据拷贝到该数组中。如果消息超出分配的新数组,接着分配一个比之前更大的数组,并把消息复制到该数组。

使用这种策略,大多数消息通常只会存入小数组。这意味着服务器内存得到了更有效的利用。100_000 x 4KB (小缓冲) = 400MB大多数服务器应该能够正常处理。即使是 4GB (1_000_000 x 4KB),现在的服务器也能满足要求。

可变长数组设计

可变长数组包含两个组件:

ResizableArray

ResizableArrayBuffer

ResizableArrayBuffer 包含一个大数组。该数组被划分为三个部分。一段用作小数组,一段用作中数组,一段用作大数组。ResizableArray类表示一个可变长数组,底层数据存储在ResizableArrayBuffer中。

优化方案

一种优化方案:只用一个存储块。需要的时候在待扩展的块后面直接分配新块。这样不需要把数据从旧数组拷贝到新数组,可以直接“扩展”存储块容纳旧数据和新数据,新数据直接写入新增的第二个扩展块即可。这样避免了拷贝所有数组数据的情况。

上述优化的缺点在于,如果无法扩展下一个内存块仍然需要拷贝数据。因此需要加入“可扩展”检查,这个操作开销不大。此外,如果存储块大小设置过小,在小数据、中等数据和大数据都存在的情况下会出现频繁扩展。

跟踪空闲块

ResizableArrayBuffer 内部的大数组同样分为三段。每段都被分为更小的存储块;每段中的存储块大小相同;小数组中的存储块大小相同;中型数组中的存储块大小相同;大数组中的存储块大小相同。

每段中的存储块大小相同可以更方便地追踪块使用状态。可以使用队列记录每个块的起始索引。还需要一个队列记录每段中的共享数组。最终,一个队列来跟踪空闲小数据块,一个队列用记录空闲的中型数据块,一个队列用于空闲的大数据块。

根据数据类型从响应队列获取下一个空闲块起始索引,可以实现从任意数据段分配存储块。把起始索引放回相应队列可以释放数据块。

这里我用简单的环形缓冲区实现队列。GitHub 仓库对应的代码为 QueueIntFlip。环形缓冲区教程:

tutorials.jenkov.com/java-performance/ring-buffer.html

扩展写

向数组写数据时,可变长数组自动扩展。如果尝试向数组写入的数据超出当前分配的存储空间,将分配一个新的更大的存储块并把所有数据拷贝到新块中,然后释放之前较小的存储块。

释放数组

一旦可变长数组完成了大小调整,应该对其进行释放以便可以接收其他消息。

使用 ResizableArrayBuffer

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

创建一个 ResizableArrayBuffer

变换设计

您可以根据自己的需要修改 ResizableArrayBuffer 设计。例如,可以在其中创建多于三个数据段。操作起来应该也很容易,只要看 GitHub 中的源代码进行修改即可。

免责声明:内容来源于网络,若涉及侵权联系尽快删除!

预约申请免费试听课

填写下面表单即可预约申请免费试听!怕钱不够?可就业挣钱后再付学费! 怕学不会?助教全程陪读,随时解惑!担心就业?一地学习,可全国推荐就业!

上一篇:处理 Java 异常的几个小知识
下一篇:Java 响应式关系数据库
Java程序员学习路线指南

Java程序员学习路线指南

Java培训中的基础知识

Java培训中的基础知识

掌握6条技能快速Java入门

掌握6条技能快速Java入门

如何学习Java的三大框架?

如何学习Java的三大框架?

选择城市和中心
贵州省

福建省

  • 达内厦门软件园中心
广西省

海南省