本章主要包含以下內(nèi)容
1 簡(jiǎn)介
2 構(gòu)造函數(shù)
3 擴(kuò)容機(jī)制
4 為什么要1.5倍擴(kuò)容
5 trimToSize
- 簡(jiǎn)介
為了彌補(bǔ)數(shù)組不能動(dòng)態(tài)的調(diào)整容量,Java給我們提供了ArrayList(列表).
ArrayList能夠順序的存儲(chǔ)元素,可以存null值,動(dòng)態(tài)的調(diào)整容量,對(duì)元素進(jìn)行排序等一系列操作.
ArrayList是線程不安全的,如果對(duì)線程安全有要求可以使用Vector,CopyOnWriteArrayList或者使用Collections.synchronizedList(List)返回的列表.
ArrayList內(nèi)部使用數(shù)組進(jìn)行存儲(chǔ),因此可實(shí)現(xiàn)隨機(jī)訪問奇颠、移動(dòng)和刪除元素為O(N)的開銷 - 構(gòu)造函數(shù)
涉及到的變量和常量
//默認(rèn)的存儲(chǔ)容量
private static final int DEFAULT_CAPACITY = 10;
//空元素?cái)?shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//沒有存儲(chǔ)容量的空元素?cái)?shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存儲(chǔ)元素的數(shù)組
transient Object[] elementData;
//ArrayList的元素?cái)?shù)量
private int size;
構(gòu)造方法
/**
*構(gòu)造一個(gè)含有初始容量的空列表
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//構(gòu)造一個(gè)沒有初始容量的空列表
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//構(gòu)造一個(gè)有元素的列表
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 沒有初始容量的空列表
this.elementData = EMPTY_ELEMENTDATA;
}
}
- 擴(kuò)容機(jī)制
主要使用如下四個(gè)方法
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//確認(rèn)所需要的最小容量柿冲，在沒有初始容量的情況下會(huì)使用默認(rèn)容量作為最小容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//確認(rèn)最小容量是否可用
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//原文
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
//大意就是,有一些虛擬機(jī)實(shí)現(xiàn)對(duì)數(shù)組的長(zhǎng)度有限制
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//計(jì)算新的容量凸郑，擴(kuò)容1.5倍映皆。eg:原來是10 添加一個(gè)元素 那么新的容量是 10*2 + 10/2 = 15; 奇數(shù)為11*2+11/2 = 27
int newCapacity = oldCapacity + (oldCapacity >> 1);
//防止初始容量為0的情況 此時(shí)minCapacity = 1, oldCapacity = 0,newCapacity = 0
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//超過單個(gè)數(shù)組的長(zhǎng)度限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 復(fù)制元素到新數(shù)組中
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
關(guān)于MAX_ARRAY_SIZE的異常,跟虛擬機(jī)有關(guān),最大不一定是Integer.MAX_VALUE
堆內(nèi)存溢出
虛擬機(jī)限制
- 為什么要1.5倍擴(kuò)容
假如每次都只是擴(kuò)充1的時(shí)候,每次操作都會(huì)引起內(nèi)存的銷毀和內(nèi)存的開辟,影響程序的效率踢关。而通過這種預(yù)分配方式就能夠提高效率。這種機(jī)制在Redis中也能看到,Redis的String是2倍的預(yù)分配,當(dāng)超過1M的時(shí)候每次回預(yù)分配1M春畔。當(dāng)然這種預(yù)分配也會(huì)引起空閑內(nèi)存的增多,尤其是當(dāng)列表元素過多的時(shí)候蹂匹。假如說數(shù)組的最大長(zhǎng)度為1024,那么這樣就會(huì)有大約300多的空閑內(nèi)存。Java也給我們提供了壓縮的方法trimToSize护锤。 - trimToSize
在使用列表的時(shí)候如果我們能夠確認(rèn)列表不在添加元素,那么我們就可以使用trimToSize減少空閑內(nèi)存官地。elementData的數(shù)組大小會(huì)與實(shí)際元素大小相同。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
