Rob*_*Rob 147 java arraylist capacity data-structures
通常的构造函数ArrayList是:
ArrayList<?> list = new ArrayList<>();
但是还有一个重载的构造函数,其初始容量有一个参数:
ArrayList<?> list = new ArrayList<>(20);
ArrayList当我们可以随意添加时,为什么创建具有初始容量的产品很有用？
NPE*_*NPE 195
如果事先知道尺寸ArrayList是多少,则指定初始容量会更有效.如果不这样做,则必须在列表增长时重复分配内部数组.
最终列表越大,通过避免重新分配节省的时间就越多.
也就是说,即使没有预先分配,n在后面插入元素ArrayList也可以保证花费总O(n)时间.换句话说,附加元素是一个摊销的常数时间操作.这是通过使每次重新分配以指数方式增加数组的大小来实现的,通常是因子1.5.通过这种方法,可以显示O(n)操作的总数.
xyz*_*xyz 25
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开头,然后继续增加它.
Dan*_*mms 16
我实际上在2个月前写了一篇关于这个主题的博客文章.这篇文章是针对C#的,List<T>但Java ArrayList有一个非常相似的实现.由于ArrayList使用动态数组实现,因此可根据需要增加大小.因此,容量构造函数的原因是出于优化目的.
当发生其中一个调整操作时,ArrayList将数组的内容复制到一个新数组中,该数组的容量是旧数组的两倍.此操作在O(n)时间内运行.
这是一个如何ArrayList增加尺寸的例子:
10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308
所以列表有能力的开始10,当加入第11项是通过增加50% + 1对16.在第17项上ArrayList再次增加25,依此类推.现在考虑我们创建一个已知所需容量的列表的示例1000000.创建ArrayList而不尺寸构造函数会调用ArrayList.add 1000000倍这需要O(1)正常或为O(n)在调整大小.
1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851操作
使用构造函数进行比较,然后调用ArrayList.add哪个保证在O(1)中运行.
1000000 + 1000000 = 2000000次操作
Java如上所述,从10每个resize 开始并增加每个resize 50% + 1.C#开始4并且更积极地增加,每次调整大小加倍.在1000000从上述用于C#使用添加了示例3097084操作.
设置ArrayList的初始大小(例如,to ArrayList<>(100))可以减少重新分配内部存储器的次数.
例:
ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2,
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added.
正如您在上面的示例中所看到的 - ArrayList如果需要,可以扩展.这没有告诉你的是,Arraylist的大小通常加倍(尽管注意新的大小取决于你的实现).以下是Oracle引用的:
"每个ArrayList实例都有一个容量.容量是用于存储列表中元素的数组的大小.它始终至少与列表大小一样大.当元素添加到ArrayList时,其容量会自动增长.除了添加元素具有不变的摊销时间成本这一事实之外,未指定增长政策的细节."
显然,如果你不知道你将持有什么样的范围,设置大小可能不是一个好主意 - 但是,如果你确实有一个特定的范围,设置初始容量将提高内存效率.