动态数组及其实现
动态数组或者叫可变长数组(Variable-Length Array, VLA),有两种解释。
- 在运行时确定其长度,而不是在编译器确定其长度。
- 在运行时,根据需求,其长度可以自动伸缩。 💥
第一种一般由编程语 言提供支持。不是我们本章的重点,以Java为例。
public class DynamicArrayTest {
public static void main(String[] args) {
Integer[] iarr1 = initArray(10); // 在程序运行期间动态确定数组大小
Integer[] iarr2 = initArray(20);
}
public static Integer[] initArray(int size) {
Integer[] iarr = new Integer[size];
Arrays.fill(iarr, 0);
return iarr;
}
}
数组的长度并不是在编译期间确定,而是在程序运行期间确定。并且其大小可以根据函数参数或其他运行时信息动态变化。
第二种才是我们本章讨论的重点。而第二种的实现是比较复杂的,本文介绍两种实现方式。
我们为什么需要动态数组
很多时候在程序编码期间,我们是无法确定数组的实际大小的。这就需要在程序的运行期间确定,并且可能会出现同一个方法,作用在不同的业务数据上,对数组大小的需求会不一样。这种情况我们很难确定数组长度。一种方法是我们将数组设置的足够大,但是会造成大量内存空间的浪费。而这个足够大也不好确定,比如我们认为当下的业务需求 20 就是一个足够大的数值,但是随着业务量的增长,20 会不够大,这时候就会出现线上问题。我们就需要频繁的调整程序中的数组大小。
这时我们就需要程序能够动态的调整数组的大小,比如初始化时数组的长度为 10,在达到某个阈值后,如 70% 也就是数组中的元素达到 7 个时,数组能够动态的增长 1.5 倍或 2 倍。
使用动态数组有以下好处:
- 动态调整大小:动态数组可以在运行时根据需要增加或减少其容量。这使得程序员无需预先知道所需存储元素的确切数量,从而在设计程序时提供更大的灵活性。
- 避免资源浪费:与静态数组相比,动态数组只在需要时扩展其容量,这有助于避免未使用空间的浪费。当元素被移除时,动态数组可以相应地缩小,释放不再使用的内存空间。
方式一:替换法
所谓替换法,即使用一个新的数组来替换原来的数组。
- 当需要扩充数组时,创建一个更大的数组,并将原数组的内容拷贝到新的数组中,然后替换原来的数组;
- 当需要收缩数组时,则创建一个小的数组,并将原数组的内容拷贝到新的数组中,然后替换原来的数组。
以下是动态扩容的 Java 代码实现,下面的代码并没有考虑并发问题。
public class DynamicArray<T> {
public Object[] data;
private int size = 0;
// 默认扩容因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 伸缩尺度
private static final float DEFAULT_SCALA = 1.5f;
public DynamicArray(int size) {
data = new Object[size];
}
public void add(T t) {
if (size >= data.length * DEFAULT_LOAD_FACTOR) {
grow();
}
data[size] = t;
size++;
}
@SuppressWarnings("unchecked")
public T get(int index) {
return (T) data[index];
}
public void grow() {
Object[] newData = new Object[(int) (data.length * DEFAULT_SCALA)];
System.out.println("扩充数组,原数组大小:" + data.length + ",新数组 大小:" + newData.length + ",已使用:" + size) ;
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
}
测试代码
public static void main(String[] args) {
DynamicArray<Integer> dynamicArray = new DynamicArray<>(5);
dynamicArray.add(1);
dynamicArray.add(2);
dynamicArray.add(3);
dynamicArray.add(4);
dynamicArray.add(5);
dynamicArray.add(6);
dynamicArray.add(7);
dynamicArray.add(8);
dynamicArray.add(9);
}
运行结果
扩充数组,原数组大小:5,新数组大小:7,已使用:4
扩充数组,原数组大小:7,新数组大小:10,已使用:6
扩充数组,原数组大小:10,新数组大小:15,已使用:8
上面的代码并没有实现动态收缩。而JDK中的 ArrayList
同样也没有考虑动态收缩。这样设计是有其原因的。
- 重复伸缩问题:如果
ArrayList
的大小频繁波动,势必会造成更多次数的内存重新分配和数组拷贝。会损失一部分性能。保持ArrayList
的容量比实际大小大一些,可以减少因频繁扩展和收缩而导致的性能波动。程序可以预期较一致的性能表现,而不是在每次内存调整时遇到性能下降。 - 内存利用率:现代系统通常具有足够的内存资源,尤其是相对于频繁的性能开销来说,内存利用率的优化不是首要问题。确保程序运行的流畅性和一致性更加重要。
- 使用场景使然:大部分的使用场景是需要数组的长度增加,而非减少。并且通常情况下,使用动态数组是为了进行数据处理,也即用完之后立即释放。因此不涉及收缩对内存的使用率来说不会有很大的影响。
其实说到底还是为了性能,既然加了,证明有这么多需求,如果收缩,可能还会加回去,那干脆就不收缩了,减少了重新分配内存和数组拷贝的时间。
方法二:链式分段法
另外一种方法是将一个大数组分成很多个段,这些段首尾相接,也即使用链表的结构来保存段。当需要对数组进行扩容时,就在最后一个段上再增加一个段。这就要求数组的长度正好是段的长度的倍数。如每个段的长度为 32,那整个数组的长度就需要时段的倍数。
具体代码此处不再实现,仅传播一 种思想。有兴趣可以自己动手,或通过 AI 工具生成。如在 ChatGPT 中输入 “使用Java实现一个链式分段数组”,ChatGPT能自动生成相应的代码。
优点:
- 无需频繁的拷贝数组。
缺点:
- 数组的内存空间不连续,效率较低。
- 随机访问的时间复杂度是
假设,段的长度为 32,随机访问一个元素或查找一个元素在最坏情况下的时间复杂度是 (即在最后一个段的最后一个元素中),因此随机访问的时间复杂度为
而一种更复杂的方式是将其转为树,可参考 树。
方式三:数组分段法
聪明的你可能已经想到了,既然第一种方式有数组拷贝的问题,而第二种方式有查询效率低的问题,那将这两种方式结合一下是不是就可以解决这个问题了。
数组分段法与上面的链式分段法类似,也是将数组分成一个一个的段。只不过是用数组来保存这些段。动态扩容是扩充保存段的数组。这样在一定程度上能大幅减少数组拷贝。而且即便发生了数组拷贝,拷贝的也是保存段的数组,拷贝时仅拷贝了这些段的引用,拷贝的数据量也大幅减少了。
这涉及到一些算法来计算索引的位置。假设段的长度为 ,要获取索引位置为 的数据。
- 计算段的索引: 。这里表示向下取整。
- 计算段内数据的索引: