当我们创建一个数组时,我们无法改变它的大小; 它是固定的.好吧,看起来不错,我们可以创建一个新的更大的数组并逐个复制值,这有点慢.它的技术背景是什么？
Jar*_*Par 21
这个问题没有提到一种语言,所以我将为我的答案选择基于'C'的数组.
数组被分配为单个内存块.增长阵列是有问题的,因为正确地做这件事的唯一方法是在最后增长它.对于大小为N的增长,在下一个分配的地址之前,数组末尾必须至少有N个空闲字节.
支持这种类型的分配需要将分配分布在虚拟地址空间中.这既消除了使内存分配彼此更接近的好处,又有助于增加碎片.这在大多数内存管理器面前都是如此,这些内存管理器试图将内存打包在一起并减少碎片.
在内存中具有足够空间的位置分配新阵列并复制阵列根本不是一个通用解决方案的选项.原因是消费者可以通过指针看到数组的先前位置.
int* array = malloc(int*someSize);
int* pointer1 = &(arr[2]);
growArray(&array, 12); // Can't move because pointer1 knows the address of the array
取决于您的语言,但通常数组被安排为内存中的一系列连续空格.这样您就不必为数组中的每个点存储内存位置,只需存储一个内存位置(数组的开头),然后添加一个偏移量(偏移量将是每个条目的大小乘以索引你想要找出特定条目在内存中的位置.
这也是数组通常只包含一种类型的原因,否则您无法进行如此简单的计算.允许您存储多种类型的语言实际上是创建一个普通数组并将指针放到数组中的每个条目 - 所有指针通常都是相同的大小.这种间接成本水平,这就是为什么"更容易"的语言往往会慢一点.
无论如何,当你分配更多的内存时,你想把新的内存放在数组的末尾 - 否则你会把你的内存分成一个洞 - 为什么你会这样做？
所以你不能只是在没有物理移动的情况下扩展阵列.
计算机多年来一直这样做,所以大多数语言都有一些方法来分配一大块内存然后告诉CPU将所有条目块复制到新块并更改指针以反映这一点,但通常(C, Java,...)他们把这个留给程序员用特定的命令复制数组而不是为你做(可能只是为了让你知道扩展数组不是"免费"
可以在数组的末尾添加一个指针,以跳转到要添加到数组末尾的新内存块,但现在您的数组查找速度已经非常慢了.
许多语言只是将数组包装为允许这种功能的集合.例如,Java Vector/ArrayList将自动为您重新分配内存.链表实际上每次只用一个指向下一个元素的指针分配一个元素.添加元素非常快,但转到元素5000的速度很慢(你必须读取每个元素,而数组读取元素1的速度与元素5000一样快)