为什么启动一个具有初始容量的ArrayList?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (21)

通常的构造函数ArrayList是:

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

但是也有一个重载的构造函数,它的初始容量有一个参数:

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

ArrayList如果我们可以随意添加初始容量,为什么有用?

提问于
用户回答回答于

如果事先知道ArrayList要发生的大小,指定初始容量会更有效。如果你不这样做,内部数组将不得不随着列表的增长而重复分配。

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

也就是说,即使没有预先分配,n在后面插入元素ArrayList也会保证占用O(n)时间。换句话说,附加一个元素是一个摊销的恒定时间操作。这是通过每次重新分配以指数形式增加阵列的大小来达到的,典型地通过一个因子1.5。通过这种方法,可以显示O(n)操作的总数。

用户回答回答于

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

所以,如果你知道你的上限是20个项目,那么创建初始长度为20的数组比使用默认值15(例如15)要好,然后将其大小调整为15*2 = 3020,同时浪费扩展周期。

扫码关注云+社区