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

简介:

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

2.2.1 可变大小数组

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

image

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

image

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

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

image

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

图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,应该将下面的语句写在你的类定义和描述性注释之前:
image

有些程序员将这条语句中的Arrays替换为星号,目的是在程序中可以使用包java.util中的所有类。

自测题18 考虑下列语句定义的字符串数组:

image

为数组text增大5个元素的容量且不改变当前内容的Java语句是什么?

自测题19 考虑字符串数组text。如果放到这个数组中的字符串的个数小于它的长度(容量),你如何减少数组的长度而不改变它的当前内容?假定字符串的个数保存在变量size中。

相关文章
|
8天前
|
Java
|
3天前
|
Java
Java数组的应用场景
Java数组的应用场景
10 1
|
3天前
|
存储 机器学习/深度学习 Java
Java数组
Java数组
10 1
|
8天前
|
存储 Java API
|
7天前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
25 0
|
8天前
|
存储 搜索推荐 算法
在 Java 中如何更改数组列表的顺序
【8月更文挑战第23天】
7 0
|
8天前
|
存储 安全 Java
在 Java 中如何存储数组列表
【8月更文挑战第23天】
14 0
|
8天前
|
Java API
如何在 Java 中将 Arraylist 变成数组?
【8月更文挑战第23天】
15 0
|
8天前
|
Java API
如何在 Java 中将 Arraylist 变成数组?
【8月更文挑战第23天】
16 0
|
8天前
|
存储 Java API
如何在 Java 中填充数组列表?
【8月更文挑战第23天】
8 0
下一篇
云函数