本帖最后由 大蓝鲸Java 于 2017-12-1 12:33 编辑
在平时的资料学习中,很多都认为ArrayList底层是数组,默认长度为10,每次扩容1.5倍.但是实际上真的是这样的吗?本文从源码角度做详细的分析. ArrayList 有三个构造: 1, public ArrayList() {} 2,public ArrayList(int initialCapacity) { } 3,public ArrayList(Collection<? extends E> c) {} 其中第一个构造表示将一个空的数组赋值给集合底层的那个数组.
第二个构造表示将创建一个指定容量大小的集合
第三个方法是创建一个集合,将参数集合的数据都添加到现在创建的集合中,类似addAll();
另外ArrayList 承于AbstractList，实现了List接口，是一个长度可变的集合，提供了增删改查的功能。集合中允许null的存在。ArrayList类还是实现了RandomAccess接口，可以对元素进行快速访问。实现了Serializable接口，说明ArrayList可以被序列化，还有Cloneable接口，可以被复制。和Vector不同的是，ArrayList不是线程安全的。
方法解析：
void add(int index, E element) 将指定的元素插入此列表中的指定位置。
//如果集合中最大索引是3.
那么调用此方法，可以在4索引插入元素。但是超过4索引就报错了。
-----------------------------------------------------------------------------------------------------------------------
boolean add(Object e): 向集合中添加元素
//方法源码分析：
public boolean add(E e) {
ensureCapacityInternal(size + 1); //重新计算长度，并让modCount++
//modCount是并发修改异常中的关键，下面会解释
elementData[size++] = e;//每次往数组的末尾存。保证了存取有序
return true; //因为ArrayList可重复所以每次都是true。跟HashSet相对
}
-----------------------
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//默认大小跟实际大小比较
} //保证了ArrayList只要刚开始添加就有一个默认10大小的容量，因为DEFAULT_CAPACITY = 10；
ensureExplicitCapacity(minCapacity);
}
------------------------
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//modCount是并发修改异常中的关键，下面会解释
if (minCapacity - elementData.length > 0)//比较长度
grow(minCapacity);
}
------------------------
private void grow(int minCapacity) {
int oldCapacity = elementData.length;//旧容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量 = 旧容量 + 旧容量/2
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);//数组的拷贝//底层调用System.arraycopy拷贝
}
终上所述：ArrayList 底层是一个长度为0的数组。在刚添加一个元素后，变成默认大小10.
只要是存满了。那么就把原来的长度*1.5（也就是扩容原先的1.5倍大小。）
如果此时一下子添加多个元素,那么会拿添加元素个数 + 原来集合的个数 跟扩容之后的1.5倍相比,比一比谁长. 谁长听谁的.
再创建了一个新的数组，新的数组的长度为比较后的结果
利用 System.arraycopy 的方法将原数组的内容拷贝到新的数组中去。
-----------------------------------------------------------------------------------------------------------------------
void clear():清空集合中所有元素
//方法源码分析
for (int i = 0; i < size; i++) //遍历集合
elementData = null; //得到每一个元素，把每一个元素变成null
size = 0; //将长度变为0
-----------------------------------------------------------------------------------------------------------------------
boolean contains(Object o):判断集合中是否包含某个元素
//方法源码分析
public boolean contains(Object o) {
return indexOf(o) >= 0;//调用indexOf看参数在集合中是多少索引。
//如果索引为正数，那么集合中就包含参数
}
------------------------
public int indexOf(Object o) {
if (o == null) { //判断参数是否为null
for (int i = 0; i < size; i++)//遍历
if (elementData==null)//判断遍历到的是否为null
return i; //如果存在就直接return
} else {
for (int i = 0; i < size; i++)//遍历
if (o.equals(elementData))//利用equals进行判断
return i; //如果存在就直接return
}
return -1;//如果不存在就return-1
}
终上所述："方法底层是依赖 equals" 方法来判断是否是否与集合内部某一个元素相同。
如果我们没有重写equals。那么用的是object里面的equals。此时判断的是地址值。
当遇到一个匹配的直接return，所以当重复时候，只能返回第一个。
-----------------------------------------------------------------------------------------------------------------------
boolean isEmpty():判断集合中的元素是否为空
//方法源码分析
public boolean isEmpty() {
return size == 0;//就是判断长度是否为0
}
-----------------------------------------------------------------------------------------------------------------------
boolean remove(Object o):根据元素的内容来删除某个元素
//方法源码分析
public boolean remove(Object o) {
if (o == null) {//判断参数是否为null
for (int index = 0; index < size; index++)//遍历
if (elementData[index] == null) {
fastRemove(index); //调用另外的方法删除。
return true;//只要成功删除一个，就直接return了。
}
} else {
for (int index = 0; index < size; index++)//遍历
if (o.equals(elementData[index])) {"方法底层是依赖 equals"
fastRemove(index);//调用另外的方法删除。
return true;//只要成功删除一个，就直接return了。
}
}
return false;
}
------------------------
private void fastRemove(int index) {
modCount++; //重新计算长度，并让modCount++
//modCount是并发修改异常中的关键，下面会解释
int numMoved = size - index - 1;//表示要删除的元素右边还有几个
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);//把数组复制给自己。
//从要删除的后一个开始复制给自己
//复制到要删除的索引开始，复制numMoved个。
elementData[--size] = null;
}
"方法底层是依赖 equals"
终上所述："方法底层是依赖 equals" 方法来判断是否是否与集合内部某一个元素相同。
如果我们没有重写equals。那么用的是object里面的equals。此时判断的是地址值。
当遇到一个匹配的直接return，所以当重复时候，只能删除第一个。
删除完毕，数组长度--。调用System.arraycopy拷贝给自己。
"注意点"
boolean remove(Object o)有一个重载的方法
E remove(int index)
在ArrayList<Integer> al = new ArrayList<>();这样创建对象
用al调用remove.传递2
al.remove(2);//此处的2不会自动装箱。删除的是2索引
但是如果 Collection<Integer> al = new ArrayList<>();这样创建对象
用al调用remove.传递2
al.remove(2);//多态创建
编译看左边，Collection中只有remove(Object o)的方法
所以右边会走remove(Object o)
-----------------------------------------------------------------------------------------------------------------------
int size():获取集合的长度
//方法源码分析
public int size() {
return size;//实际上就是数组的长度
}
-----------------------------------------------------------------------------------------------------------------------
Object[] toArray():能够将集合转换成数组并把集合中的元素存储到数组中
//方法源码分析
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
------------------------------------------------------------------------------------------------------------------
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// original 要拷贝的数组 newLength 集合的长度，也就是转成数组后数组的长度
T[] copy = ((Object)newType == (Object)Object[].class)?
(T[]) new Object[newLength]//创建一个Object类型的数组，再转换成T类型的数组。
//T就是toArray()重载方法toArray(T[] a)传递的参数
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
//数组的复制
return copy;//将创建的数组返回。
}
终上所述：如果是 toArray()就创建了一个新的Object类型的数组。
如果有参数toArray(new String[0])就创建了一个新的Object类型的数组再转成String类型
利用System.arraycopy的方法，将元素拷贝到数组中去。再将新数组返回
-----------------------------------------------------------------------------------------------------------------------
<T> T[] toArray(T[] a):能够将集合转换成数组并把集合中的元素存储到数组中
public <T> T[] toArray(T[] a) {
if (a.length < size)//如果参数数组长度小于集合长度
return (T[]) Arrays.copyOf(elementData, size, a.getClass());//按照集合长度进行拷贝
System.arraycopy(elementData, 0, a, 0, size);//如果参数数组长度大于集合长度直接拷贝
if (a.length > size)//将过于的赋值为null
a[size] = null;//引用数据类型默认null。所以不赋值也是可以的，就是初始化值
return a;//将数组返回
}
终上所述：如果有参数toArray(new String[0])
先判断0跟集合长度的大小。如果集合长度大，按照集合长度进行拷贝，创建一个新的Object类型的数组再转成String类型
利用System.arraycopy的方法，将元素拷贝到数组中去。再将新数组返回
如果一样长，直接拷贝
如果参数数组长度大，那么后面的赋值为null。因为集合是引用数据类型。
所以直接是默认初始化值
"从效率而言，此处toArray(new String[list.size()])"
参数大小设置为集合长度最合适。
|
收藏
淘帖
踩
