download:图灵 JAVA 互联网架构师五期
ArrayList 的工作原理
ArrayList has 是一个外部的一般数组,它充当数据存储。在大多数情况下,咱们不指定列表的确切大小。然而外部数组必须有一些大小!它的确如此。它的默认大小是 10。
public static void main(String[] args) {
ArrayList<Car> cars = new ArrayList<>();
}
复制代码
首先,让咱们看看增加新元素是什么样的。首要任务是查看
外部数组在外部数组中是否有足够的空间,
以及是否可能再放一个元素。如果有空间,则将新元素增加到列表的开端。当咱们说“到最初”时,咱们并不是指数组中的最初一个地位(那会很奇怪)。咱们指的是最初一个以后元素之后的地位。它的索引将是 cars.size()。咱们的列表目前是空的 ( cars.size() == 0 )。因此,新元素将被增加到地位 0。
ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car(“Ferrari 360 Spider”);
cars.add(ferrari);
复制代码
这很明显。如果咱们在两头插入会发生什么,即在其余元素之间?
public static void main(String[] args) {
ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car(“Ferrari 360 Spider”);
Car bugatti = new Car(“Bugatti Veyron”);
Car lambo = new Car(“Lamborghini Diablo”);
Car ford = new Car(“Ford Modneo”);
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
cars.add(1, ford);// add ford to cell 1, which is already occupied
}
复制代码
同样,首先查看数组中是否有足够的空间。如果有足够的空间,则 元素向右移动,从咱们插入新元素的地位开始。咱们在地位 1 插入。换句话说,从地位 3 的元素被复制到地位 4,元素 2 到地位 3,元素 1 到地位 2。
而后咱们的新元素被插入到它的地位。前一个元素 (bugatti) 已经从那里复制到一个新地位。
现在让咱们看看如果没有地方可能将新元素插入到数组中,这个过程是如何发生的。
当然,首先要查看是否有足够的空间。如果没有足够的空间,则在外部创建一个新数组 ArrayList 其大小是旧数组的大小乘以 1.5 加 1 在咱们的例子中,新数组的大小将为 16。所有以后元素将立即复制到那里。
垃圾收集器将删除旧数组,只保留扩大后的新数组。现在有一个新元素的空间。咱们将它插入到已被占用的地位 3。现在开始熟悉的程序。所有从索引 3 开始的元素都向右移动一个地位,并且新元素被悄悄增加。插入实现!咱们实现了插入。现在让咱们谈谈删除我的项目。你会记得咱们在处理数组时遇到了一个问题:删除元素会在数组中产生“洞”。每次删除,咱们都必须编写自己的代码来执行这个转变。
ArrayList 遵循雷同的原则,但它已经实现了这种机制。
最终咱们失去了咱们想要的:
lambo 元素已被删除。这里咱们从两头移除了一个元素。显然,从列表开端删除一个元素更快,因为该元素被简略地删除而无需移动所有其余元素。让咱们再次讨论一下外部数组的维度以及它在内存中的排列形式。
扩大阵列需要一些资源。
因此,不要创建 ArrayList 如果您必定它至多有 100 个元素,则使用默认大小。插入第 100 个元素时,外部数组必须扩大 6 次,并且每次都必须移动所有元素。
从 10 个元素到 16 个元素
从 16 个元素到 25 个元素
从 25 到 38
从 38 到 58
从 58 到 88
从 88 到 133(即旧数组的大小乘以 1.5 加 1)
可能设想,这是相当耗费资源的。因此,如果您已经知道(以至大概)所需的我的项目数量,最好创建一个具备特定大小数组的列表:
ArrayList<Car> cars = new ArrayList<>(100);
复制代码
现在将一次性调配 100 个元素的数组的内存,使数组更高效(不需要扩大)。这种策略也有另一面。
当您从 中删除对象时 ArrayList,外部数组的大小不会主动减小。
假设咱们有一个 ArrayList 蕴含 88 个元素的完整外部数组:
当程序运行时,咱们删除了 77 个元素,所以只剩下 11 个:
你已经猜到问题出在哪里了吗?你明确了,内存使用效率低下!咱们在这里只使用了 11 个地位,但咱们为 88 个元素调配了内存。这比咱们需要的多 8 倍!ArrayList 在这种情况下,咱们可能使用该类的一种非凡方法来优化内存使用:trimToSize() 此方法将外部数组的长度“修剪”为以后存储在其中的元素数。
现在咱们只调配了咱们需要的内存!