ArrayList的基本原理
在Eclipse中按着ctrl键鼠标点击ArrayList,打开源代码。
1.new ArrayList()原理
List list = new ArrayList();
List list2 = new ArrayList(10);
源代码(抽取如下):
package test;
public class ArrayList{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//定义一个空数组
private static final Object[] EMPTY_ELEMENTDATA = {};//定义一个空数组
transient Object[] elementData;//定义一个数组
//initialCapacity是定义集合的大小
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;
}
}
解释:首先我们可以看到2个ArrayList构造方法,一个无参构造器,一个有参构造器。
无参构造器:为elementData这个对象数组赋了一个空值,也就是建立了一个空数组
有参构造器:传入集合大小,如果大于0,则创建一个有初始大小的数组;如果等于0,则创建一个空数组;如果小于0,则抛出异常。
2.add()背后的原理
list.add(E e);
在ArrayList源文件中,使用快捷键ctrl+o,找到add(E e)并点击
源代码:
private int size;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
解释:首先可以看到返回的是boolean值。当我们添加一个元素时先执行ensureCapacityInternal(size + 1),然后执行elementData[size] = e,最后size进行自增运算。这里就是list.size()方法所获取的返回值,而这个返回值代表的是集合中添加的元素个数,而不是集合的大小。现在我们来看第一行代码所代表的意思:
ensureCapacityInternal(size + 1);
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
解释:这个方法传入了一个参数(size+1),就是我们添加的所有元素的个数。此时如果数组elementData为空,则选取DEFAULT_CAPACITY和(size+1)中的最大值。那么DEFAULT_CAPACITY又是多少呢?按下ctrl键,点击这个变量,可以看到:
private static final int DEFAULT_CAPACITY = 10;
不错,是10。也就是说,如果我们传入的(size+1),也就是我们添加的元素的总个数小于10的话,那么集合会自动将自己的大小设置为10,但是此时集合中的元素还是(size+1)个,相当于:
List list = new ArrayList(10);//此时elementData.length的值为0,而集合大小为10
如果(size+1)大于10的话,就相当于:
List list = new ArrayList(size+1);//此时elementData.length的值为size+1,而集合长度是(size+1)的1.5倍
下面再看一下最后一行代码:
ensureExplicitCapacity(minCapacity);
源代码:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
解释:首先也是讲我们之前获取的minCapacity这个参数传进来。modCount是我们操作的次数,这个不用管。看后面,此时假设elementData.length的值为1的话,minCapacity为10,明显大于elementData数组长度,会执行grow方法,下面我们看grow方法:
grow(int)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
解释:首先依然传入minCapacity,此时,并创建了一个变量oldCapacity,其值为数组长度1或10,并对其增加自身的一半,赋值给newCapacity,如果newCapacity小于传入的数,就将集合大小设为minCapacity,如果newCapacity大于集合所能存储的最大值,就将集合大小设置为最大值,最后复制一个新的数组。就实现了数组大小的扩展。
3.size()背后的原理
list.size()
public int size() {
return size;
}
解释: 可以看到这里直接返回一个int类型的size,就是我们刚才的那个size
注意:
1. 从源码可以看出,在第一次向集合中添加元素的时候,集合大小就变为10了
2. 默认长度扩展是自身长度的50%
3. 以上写的数组其实也是集合,不必纠结
总结:整体上代码很多但其实就完成了2个功能:
1.通过add(E e)这个方法添加元素
2. 通过以下三个方法对集合(数组)扩展
ensureCapacityInternal(int minCapacity)//获取集合的size
ensureExplicitCapacity(int minCapacity)//判断size是否超出集合大小
grow(int minCapacity)//扩展集合