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

问题

通常的构造函数为ArrayList

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

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

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

当我们可以随意添加它时,为什么创建具有初始容量的ArrayList是有用的?


#1 热门回答(181 赞)

如果你事先知道ArrayList的大小,那么指定初始容量会更有效。如果不这样做,则必须在列表增长时重复分配内部数组。

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

也就是说,即使没有预先分配,在anArrayList的后面插入n元素也可以保证总计O(n)时间。换句话说,附加元素是一个摊销的常数时间操作。这是通过使每次重新分配以指数方式增加数组的大小来实现的,通常是因子1.5。使用这种方法,操作总数可以显示为O(n)


#2 热门回答(41 赞)

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

所以,如果你知道你的上限是20个项目,那么创建初始长度为20的数组比使用默认值15更好,然后将其调整为15*2 = 30,并且在浪费扩展周期时仅使用20。

附: - 正如AmitG所说,扩展因子是特定于实现的(在本例中为(oldCapacity * 3)/2 + 1)


#3 热门回答(24 赞)

Arraylist的默认大小是10

/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
    this(10);
    }

因此,如果要添加100个或更多记录,可以看到内存重新分配的开销。

ArrayList<?> list = new ArrayList<>();    
// same as  new ArrayList<>(10);

因此,如果你对将要存储在Arraylist中的元素数量有任何了解,最好使用该大小创建Arraylist,而不是从10开始,然后继续增加它。