为什么要启动具有初始容量的 ArrayList？

data-structures java arraylist capacity

2022-08-31 07:17:09

通常的构造函数是：ArrayList

ArrayList<?> list = new ArrayList<>();

但还有一个重载构造函数，其初始容量有一个参数：

ArrayList<?> list = new ArrayList<>(20);

为什么创建具有初始容量的有用，因为我们可以随心所欲地附加到它？ArrayList

答案 1

如果您事先知道将要使用的大小，则指定初始容量会更有效。如果不这样做，则必须随着列表的增长而重复重新分配内部数组。ArrayList

最终列表越大，通过避免重新分配来节省的时间就越多。

也就是说，即使没有预分配，在的后面插入元素也保证需要总时间。换句话说，追加元素是一种摊销的常量时间运算。这是通过使每次重新分配以指数方式增加数组的大小（通常为的系数）来实现的。使用这种方法，操作的总数可以显示为O（n）。。nArrayListO(n)1.5

答案 2

因为是动态调整数组大小的数组数据结构，这意味着它被实现为具有初始（默认）固定大小的数组。当它被填满时，数组将被扩展到一个双倍大小的数组。此操作成本高昂，因此您希望尽可能少。ArrayList

因此，如果您知道上限是 20 个项目，那么创建初始长度为 20 的数组比使用默认值（例如 15）然后将其大小调整为仅使用 20，同时浪费扩展周期要好。15*2 = 30

P.S. - 正如AmitG所说，扩展因子是特定于实现的（在这种情况下(oldCapacity * 3)/2 + 1)