《数据结构与抽象：Java语言描述（原书第4版）》一2.2.1　可变大小数组-阿里云开发者社区

《数据结构与抽象：Java语言描述（原书第4版）》一2.2.1　可变大小数组

来自：华章出版社 2017-06-26 1147

简介：

+关注继续查看

本节书摘来华章计算机《数据结构与抽象：Java语言描述（原书第4版）》一书中的第2章，第2.2.1节，［美］弗兰克M.卡拉诺（Frank M. Carrano）　蒂莫西M.亨利（Timothy M. Henry）著罗得岛大学　新英格兰理工学院辛运帏　饶一梅　译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.2.1　可变大小数组

策略。当教室满了时，能容纳更多学生的一种办法是移到一间更大的教室。用类似的方式，当数组满了时，可以将它的内容移到一个更大的数组中。这个过程称为调整（resizing）数组大小。图2-7显示两个数组：一个是有5个连续内存单元的原始数组，另一个数组（两倍于原始数组大小）在计算机的另一块内存中。如果将数据从原始的小数组中复制到新的大数组的开头部分，得到的结果像是扩展了原来的数组一样。这种机制的唯一不足是新数组的名字：你想让它与原始数组同名。马上就会看到如何完成这个工作。

细节。假定已有myArray指向的数组，如图2-8a所示。我们先定义一个别名oldArray，它也指向这个数组，如图2-8b所示。下一步是创建一个比原始数组更大的新数组，让myArray指向这个新数组。如图2-8c所示，一般地新数组要两倍于原始数组的大小。最后一步是将原始数组的内容复制到新数组中（见图2-8d），然后丢弃原始数组（见图2-8e）。下列伪代码概括了这些步骤：

图2-8　a）一个数组；b）指向同一数组的两个引用；c）原始数组变量现在指向新的更大的数组；d）原始数组中的项复制到新数组中；e）丢弃原始数组

注：当数组不再被引用时，它的内存在垃圾回收时被收回，就像是对其他对象发生的那样。
代码。将前面的伪代码转换为Java时，可以使用Java类库中的方法Arrays.copyOf (sourceArray, newLength)来做很多事情。例如，对如下的简单整数数组进行操作：

此时，myArray指向一个数组，如图2-9a所示。接下来，调用Arrays.copyOf。将变量myArray中的引用赋给这个方法的第一个参数sourceArray，如图2-9b所示。接下来，方法创建一个新的更大的数组，并将参数数组中的项复制给它（见图2-9c）。最后，方法返回指向新数组的一个引用（见图2-9d），我们将这个引用赋给myArray（见图2-9e）。下面的语句执行这些步骤：

图2-9　语句myArray = Arrays.copyOf(myArray, 2 * myArray.length);的效果。a）参数数组；
b）指向参数数组的参数；c）获得参数数组内容的新的更大的数组；d）指向新数组的返回值；
e）将返回值赋给参数变量

注：图2-9中的数组含有整数。这些整数是基本类型值，且像这样占据数组中的位置。与之相对，例如图2-6中的数组，含有指向对象的引用而不是对象本身。

调整数组的大小或许没有第一眼看上去这样有吸引力。每次扩展数组的大小时，必须复制它的内容。如果每次需要数组外的一个额外空间而让数组增大一个元素，则这个过程将耗时过大。例如，如果含50个元素的数组满了，为了容纳另一个项，需要将数组复制到有51个元素的数组中。再添加一项时又会要求你将含有51个元素的数组复制到含有52个元素的数组中，以此类推。每次添加都会导致复制数组。如果在原含有50个项的数组中添加100项，则要复制100次数组。
另一种做法是将数组扩展m个元素，将复制开销分摊在m次添加上而不是集中在一次上。每次当数组满时倍增它的大小，这是一种典型的方法。
例如，当在含有50个项的满数组中添加一项时，在进行添加前先将50个元素的数组复制到100个元素的数组中。那么接下来的49次添加都可以快速完成而不需要复制数组。所以数组复制只需一次。

程序设计技巧：当增大数组时，将它的项复制到更大的数组中。应该充分地扩展数组，以减少复制代价的影响。常用的办法是倍增数组大小。
注：说“调整数组的大小”实际上是用词不当，因为数组的长度不会改变。调整数组大小的过程是创建了一个含有原始数组项的全新数组。给新数组与原始数组一样的名字——换句话说，指向新数组的引用赋给指向原始数组引用的变量。然后丢弃原始数组。
注：引入一个类

若一个类使用了Java类库中的类，则它的定义前必须有import语句。例如，要使用类Arrays，应该将下面的语句写在你的类定义和描述性注释之前：