本章主要包含以下内容
1 简介
2 构造函数
3 扩容机制
4 为什么要1.5倍扩容
5 trimToSize
- 简介
为了弥补数组不能动态的调整容量,Java给我们提供了ArrayList(列表).
ArrayList能够顺序的存储元素,可以存null值,动态的调整容量,对元素进行排序等一系列操作.
ArrayList是线程不安全的,如果对线程安全有要求可以使用Vector,CopyOnWriteArrayList或者使用Collections.synchronizedList(List)返回的列表.
ArrayList内部使用数组进行存储,因此可实现随机访问、移动和删除元素为O(N)的开销 - 构造函数
涉及到的变量和常量
//默认的存储容量
private static final int DEFAULT_CAPACITY = 10;
//空元素数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//没有存储容量的空元素数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储元素的数组
transient Object[] elementData;
//ArrayList的元素数量
private int size;
构造方法
/**
*构造一个含有初始容量的空列表
*/
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);
}
}
//构造一个没有初始容量的空列表
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//构造一个有元素的列表
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;
}
}
- 扩容机制
主要使用如下四个方法
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);
}
}
//确认所需要的最小容量，在没有初始容量的情况下会使用默认容量作为最小容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//确认最小容量是否可用
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
*/
//大意就是,有一些虚拟机实现对数组的长度有限制
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;
//计算新的容量，扩容1.5倍。eg:原来是10 添加一个元素 那么新的容量是 10*2 + 10/2 = 15; 奇数为11*2+11/2 = 27
int newCapacity = oldCapacity + (oldCapacity >> 1);
//防止初始容量为0的情况 此时minCapacity = 1, oldCapacity = 0,newCapacity = 0
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//超过单个数组的长度限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 复制元素到新数组中
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;
}
关于MAX_ARRAY_SIZE的异常,跟虚拟机有关,最大不一定是Integer.MAX_VALUE
堆内存溢出
虚拟机限制
- 为什么要1.5倍扩容
假如每次都只是扩充1的时候,每次操作都会引起内存的销毁和内存的开辟,影响程序的效率。而通过这种预分配方式就能够提高效率。这种机制在Redis中也能看到,Redis的String是2倍的预分配,当超过1M的时候每次回预分配1M。当然这种预分配也会引起空闲内存的增多,尤其是当列表元素过多的时候。假如说数组的最大长度为1024,那么这样就会有大约300多的空闲内存。Java也给我们提供了压缩的方法trimToSize。 - trimToSize
在使用列表的时候如果我们能够确认列表不在添加元素,那么我们就可以使用trimToSize减少空闲内存。elementData的数组大小会与实际元素大小相同。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
