java集合-ArrayList源码分析
java集合-ArrayList源码分析
1.定义
ArrayList本身直接继承AbstractList,实现List、RandomAccess、Cloneable、Serializable接口。
- RandomAccess: 标记接口，标注该类可随机访问
- Cloneable: 可以克隆拷贝
- Serializable: 可序列化
2. 构造函数
2.1 无参构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是成员变量
// Object 数组，用来存放元素
transient Object[] elementData;
// 空的 Object数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
2.2 ArrayList(int 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);
}
}
该构造函数可以传入一个初始值，若初始值大于0，则相应的创建长度为该值的数组。若初始值等于0时，则使用一个空数组。若初始值小于0，则抛出IllegalArgumentException异常。
2.3 ArrayList(Collection c)
public ArrayList(Collection <? extends E > c) {
elementData = c.toArray();
if((size = elementData.length) != 0) {
if(elementData.getClass() != Object[].class)
elementData =
Arrays.copyOf(elementData, size, Object[].class);
}
else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
该构造函数可以传入一个 Collection，将传入的集合转换为数组，然后将该数组赋值给成员变量elementData，将elementData的长度赋值给成员变量 size，判断是否不等于 0 ，如果传入的集合中有元素该判断是成立的，然后再判断elementData.getClass() != Object[].class，这不会成立的。所以结束方法。如果等于零则将EMPTY_ELEMENTDATA赋值给 elementData。
3.add 方法
public boolean add(E e) {
//确保内部容量能放下元素，如果容量不够，则进行扩容
//传入当前 size + 1
ensureCapacityInternal(size + 1);
//注意 size++ 中 ++ 的位置
elementData[size++] = e;
return true;
}
add方法中其他代码很简单，我们来看一些ensureCapacityInternal方法
3.1 ensureCapacityInternal 方法
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
在方法中调用了ensureExplicitCapacity方法，而ensureExplicitCapacity方法调用了calculateCapacity方法。
3.2 calculateCapacity 方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
判断元素集合是不是等于空数组，如果是则返回 DEFAULT_CAPACITY。DEFAULT_CAPACITY的默认值为 10。使用无参构造方式进行实例化ArrayList，ArrayList 默认的容量长度为 10。
3.3 ensureExplicitCapacity方法
将10传入ensureExplicitCapacity方法，如果传过来的值大于数组长度，则进行扩容
private void ensureExplicitCapacity(int minCapacity) {
//记录修改次数，判断是否出现并发修改异常
modCount++;
//如果传过来的值大于数组长度，则执行grow方法，也就是进行扩容
if(minCapacity - elementData.length > 0) grow(minCapacity);
}
3.4 grow 方法
grow这个方法是ArrayList中最重要的方法。都说ArrayList是基于数组实现的，但又不同于数组，ArrayList可以动态扩容，就是使用 grow实现的。
private void grow(int minCapacity) {
//扩容前元素集合的长度 可能为 0
int oldCapacity = elementData.length;
//进行右移一位，也就是除 2的 1 次方
//假如 oldCapacity 现在为 12
// newCapacity = 12 + (12/2) = 18
//也可以理解新容量为 为旧的容量的1.5倍
//当然旧容量的值需要是偶数，才能保证是 1.5倍。
//比如：oldCapacity 现在为 11
// 11 + (11/2) = 16
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新容量小于最小容量，按照最小容量进行扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//将老数组中的元素拷贝到扩容后新的数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
3.5 add(int index,E element)
该方法作用是在指定位置添加元素
public void add(int index, E element) {
//检查下标是否越界，越界抛出
// IndexOutOfBoundsException 异常
rangeCheckForAdd(index);
//是否需要扩容
ensureCapacityInternal(size + 1);
//进行元素移动
System.arraycopy(elementData, index, elementData, index + 1, size -
index);
elementData[index] = element;
size++;
}
相对于add(E e)方法，指定index下标添加元素的add方法稍微复杂。步骤如下:
- 检查index下标是否越界
- 是否需要扩容
- 进行元素移动
- 把添加的元素放入指定位置
- size加1
4.构造函数和add 方法总结
- 使用无参构造方法实例化ArrayList,默认的容量为10。
- 扩容后容量为原容量的1.5倍。
- 如果元素个数确定的情况下，尽量使用ArrayList(int initialCapacity) 构造方法进行实例化ArrayList,可以减少扩容次数
- ArrayList的元素还可以为null。
5. remove 方法
5.1 remove(int index)
删除指定下标的元素，时间复杂度为O(1)
public E remove(int index) {
//检查越界
rangeCheck(index);
modCount++;
//获得指定下标的元素
E oldValue = elementData(index);
//计算需要删除元素下标 后面还有多少个元素
//比如： 15 - 10 - 1 = 4
int numMoved = size - index - 1;
//如果 numMoved 大于 0，说明需要删除的元素不是数组中最后一个
if(numMoved > 0)
//进行元素移动 跟add正好相反，所有元素向前移动 1 位
System.arraycopy(elementData, index + 1,
elementData, index, numMoved);
//将最后一个元素置为 null
elementData[--size] = null;
//返回被删除的元素
return oldValue;
}
-
检查下标是否越界，越界则抛出IndexOutOfBoundsException
-
获得指定下标的元素
-
计算出需要移动的次数，如果大于 0 ，说明要删除的元素不是数组中最后一位，则调用
System.arraycopy方法进行元素移动。
-
将最后一个元素赋值为null,可以被gc回收
-
返回被删除的元素
5.2 remove(Object o)
按照传入的元素删除，删除匹配到的第一个元素，时间复杂度为O(n)
public boolean remove(Object o) {
if(o == null) {
for(int index = 0; index < size; index++)
if(elementData[index] == null) {
//跟上述 `remove(int index)`方法差不多
fastRemove(index);
return true;
}
}
else {
for(int index = 0; index < size; index++)
if(o.equals(elementData[index])) {
//跟上述 remove(int index) 方法差不多
fastRemove(index);
return true;
}
}
return false;
}
- 当传入元素的值为空，则遍历数组删除第一个为空的元素，并返回true。
- 当传入的值不为空，遍历数组删除第一个与传入元素值相等的元素，并返回true。
- 当想要删除的元素不存在,则返回false。
6. set 方法
修改指定下标元素的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set 方法大致分为以下几步:
- 检查下标是否越界
- 获取指定下标元素
- 将指定下标元素修改为新的值
- 返回旧值
7. get方法
返回指定下标元素，时间复杂度为O(1)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
get 方法大致分为以下几步:
- 检查下标是否越界
- 获得指定下标元素
8. clear 方法
将数组中所有元素置为null,但并不会改变数组容量大小，并将size置为0
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
9. contains 方法
判断集合是否包含指定元素
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
方法内部调用indexOf方法
public int indexOf(Object o) {
//传入元素为 null
if (o == null) {
for (int i = 0; i < size; i++)
//返回等于null的第一个元素下标
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
- 当传入元素的值为空，遍历数组，返回第一个等于null的元素下标
- 当传入的元素值不为空，遍历数组，返回第一个与传入元素值相等的元素下标。
- 不包含则返回-1
10. trimToSize 方法
public void trimToSize() {
modCount++;
if(size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA :
Arrays.copyOf(elementData, size);
}
}
能有效的节约内存。将数组容量的大小变为实际数据的个数，例如：数组容量为10，但只有前三个元素有值，其他为空，那么调用该方法之后，数组的容量变为3。