ArrayList集合底层原理
目录
ArrayList集合特点及源码分析
ArrayList是List接口的实现类
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
继承了AbstractList类，实现了Cloneable克隆接口、Serializable序列化接口、RandomAccess随机访问接口、List
特点：底层使用数组实现的 查询效率高，增删慢，线程不安全、允许为空、可重复
public static void main(String[] args) {
List<String> list=new ArrayList<String>();
boolean bool=list.add("ylc");//Collection接口添加元素
list.add(1,"ww");//根据索引添加元素
String el=list.get(1);//根据索引获取元素
list.size();//获取元素个数
list.remove(2);//根据元素位置删除
list.remove("ylc");//删除指定元素
list.set(1,"yy");//替换元素
list.clear();//清空集合
list.isEmpty();//判断元素是否为空
list.contains("ylc");//判断集合是否包含某个元素
list.indexOf("ylc");//查找所诉中所在的位置
list.lastIndexOf("ylc");//元素最后出现的索引位置
Object[] objects=list.toArray();//把集合转化为object数组
for (int i = 0; i < objects.length; i++) {
String str=(String) objects[i];
System.out.println(str);
}
String[] strings=list.toArray(new String[list.size()]);//把集合转化为指定类型数组
List<String> list2=new ArrayList<String>();
list2.add("s");
list.addAll(list2);//集合合并操作
list.retainAll(list2);//集合交集操作 list存储交集内容
list.removeAll(list2);//删除list中含有list2集合的元素
}
ArrayList源码分析
成员变量
private static final int DEFAULT_CAPACITY = 10;//数组默认长度
private static final Object[] EMPTY_ELEMENTDATA = {};//给定一个空数组
transient Object[] elementData;//存储ArrayList元素的临时数组 不会被存到磁盘
private int size;//记录数组中元素的个数
protected transient int modCount = 0; // 集合数组修改次数的标识（fail-fast机制）
transient关键字对于不想进⾏序列化的字段，使⽤ transient 关键字修饰
JDK7中，只要创建ArrayList数组，就会默认创建一个长度为10的空数组。
JDK8中，做了一个延迟加载，在创建ArrayList数组时，创建一个长度为0的空数组，只有在用到这数组才会对长度进行改变,做了一个延迟加载
构造函数
里面包含三种构造函数
1.无参构造函数
初始化数组时默认赋值一个空数组
//无参构造函数
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//默认为0
}
2.int类型的构造函数
如果传入数值大于0就创建指定容量大小的数组，数值为0为空对象数组，否则抛出异常
//带容量大小的构造函数
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);
}
}
3.集合类型构造函数
把传入的集合变成数组，赋值给elementData
集合不为空，传入数组类型转为object的话赋值给elementData
否则就直接复制到elementData中
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();//变成数组
if ((size = a.length) != 0) {//集合不为空的话
if (c.getClass() == ArrayList.class) {//判断与ArrayList类型是否一致
elementData = a;//赋值
} else {
elementData = Arrays.copyOf(a, size, Object[].class);//否则直接复制到数组中
}
} else {
elementData = EMPTY_ELEMENTDATA;//设置为空数组
}
}
增加方法
add(E e)方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); //当size=0时
elementData[size++] = e;//Size还是为0，给为0的size赋值
return true;
}
//确保集合数组内部容量
private void ensureCapacityInternal(int minCapacity) {//1
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//返回10
}
//确保显式容量
private void ensureExplicitCapacity(int minCapacity) {//minCapacity=10
modCount++;
if (minCapacity - elementData.length > 0)// 10-0>0 判断扩容关键代码 当第11个数组加入时执行grow代码
grow(minCapacity);//10
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//计算数组容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//0=0
return Math.max(DEFAULT_CAPACITY, minCapacity);// DEFAULT_CAPACITY=10，minCapacity=1 返回最大值作为数组容量
}
return minCapacity;
}
//扩容方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;//0
int newCapacity = oldCapacity + (oldCapacity >> 1); //数组长度加上位移运算（数组长度的一半）每次扩容增加1.5倍 0=0+0
if (newCapacity - minCapacity < 0)//0-10<0
newCapacity = minCapacity; //newCapacity=0
if (newCapacity - MAX_ARRAY_SIZE > 0)//10-MAX_ARRAY_SIZE<0
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);//复制操作 把一个长度为10复制到空的数组中，生成了一个新的长度为10的空数组
}
Size默认是0，add方法给Size加上1，并传入ensureCapacityInternal方法，其中ensureCapacityInternal方法中又调用了ensureExplicitCapacity方法，并传入了两个参数，第一个是elementData代表一个为空的数组，第二个是数组个数。在calculateCapacity方法中，有个if判断如果数组大小等于默认大小，就返回其中最大的数值，默认数组大小为10的话，DEFAULT_CAPACITY也等于10，所以返回的是10。把10传入ensureExplicitCapacity方法中，再把10 传入grow方法中，生成了一个新的长度为10的空数组。ensureCapacityInternal方法执行完毕。add方法Size依然为0，给为下标为0索引赋值，新增一个成功。
扩容模拟
当添加第11个元素时，add方法Size=10+1=11，传入ensureCapacityInternal方法，进入calculateCapacity方法，这时elementData=10，而DEFAULTCAPACITY_EMPTY_ELEMENTDATA=0，不满足直接返回minCapacity=11，值11进入ensureExplicitCapacity方法内部，满足11-10>0进grow方法，grow方法赋值oldCapacity=10，newCapacity=10+10的位移一位操作=10+5=15，最后使用copyOf方法，把原来10大小的数组扩容到15。
add(int index, E element)方法
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); //集合增加容量
//elementData：原数组 index：从原数组这个索引开始复制 elementData：目标数组 index + 1：目标数组的第一个元素 size - index：复制size-index个元素
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;//把当前所有数组替换
size++;//索引增加
}
//判断索引是否越界
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
这样每增加一个元素就要把当前索引复制到该元素的后面，开销很大
删除方法
remove(int index)方法
public E remove(int index) {
rangeCheck(index);//检查索引是否越界
modCount++;//记录的是集合被修改的次数
E oldValue = elementData(index);//根据索引获取元素
int numMoved = size - index - 1;//要移动的元素数量
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//复制
elementData[--size] = null; //集合数量减1
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];//返回当前索引的元素
}
进行删除前检查索引是否合理，然后记录集合被修改的次数，根据索引获取到需要删除的这个元素，然后该索引后面的元素复制到当前索引，进行覆盖，最后集合元素减去。
remove(Object o)方法
public boolean remove(Object o) {
if (o == null) {//判断对象是否为空
for (int index = 0; index < size; index++)//遍历整个集合
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)//遍历整个集合
if (o.equals(elementData[index])) {//在集合中找到该元素
fastRemove(index);//删除
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;//记录的是集合被修改的次数
int numMoved = size - index - 1;//要移动的元素数量
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//复制
elementData[--size] = null; // 集合数量减1
}
该方法利用集合遍历找到该元素，根据索引再进行删除，fastRemove方法同remove(int index)方法类似。
removeAll(Collection<?> c)方法
删除c集合中存在的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);//判断集合是否为空
return batchRemove(c, false);
}
public static <T> T requireNonNull(T obj) {
if (obj == null)
throw new NullPointerException();
return obj;
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)//complement=flase 如果elementData不包含c里面的某个元素
elementData[w++] = elementData[r];//不包含的记录下来！ 赋值到elementData，满足就从索引0开始覆盖掉原来的数组
} finally {
//存在并发修改上面发生异常没遍历完elementData，这里就会不相等 如果不存在这里就会直接跳过
if (r != size) {
//elementData：原数组 r：从原数组这个索引开始复制 elementData：目标数组 w：目标数组的第一个元素 size - r：复制元素数量
System.arraycopy(elementData, r,elementData, w,size - r);//把没有遍历到的元素赋值到已更新元素的后面
w += size - r;//现有的数据
}
if (w != size) {//w容量是不包含的 除非集合里删除一个元素都不包含这里才会跳过
for (int i = w; i < size; i++)
elementData[i] = null;//把不包含的后面多余的数组置为空
modCount += size - w;//增加修改次数
size = w;//当前数据长度
modified = true;//修改成功
}
}
return modified;
}
场景模拟代入数值：在一个10长度的数组a中删除一个3长度的数组b，删除到一半的时候，由于多线程导致数组赋值失败进入finally代码块，此时w=3，r=6，size=10，w存入的是不包含在b数组中的元素现有3个，r是遍历到中断的索引，进入(r != size)判断不相等，arraycopy方法把后面没有遍历到的重新加进来数组，w+=size – r=7;这样w中存储的就是c集合中不包含的全部元素，再遍历整个Size集合，把不包含元素后面的容量置为空。
其他方法
indexOf(Object o)方法
获取索引
public int indexOf(Object o) {
if (o == null) {//判断对象是否为空
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))//判断相等
return i;
}
return -1;//未匹配
}
lastIndexOf(Object o)
倒序获取索引
public int lastIndexOf(Object o) {
if (o == null) {//等于空
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))//判断相等
return i;
}
return -1;//未匹配
}
set(int index, E element)方法
public E set(int index, E element) {
rangeCheck(index);//检查索引
E oldValue = elementData(index);//根据索引获取元素
elementData[index] = element;//把元素赋值给当前索引
return oldValue;
}
get(int index)方法
public E get(int index) {
rangeCheck(index);//检查索引
return elementData(index);//返回根据索引获取当前元素
}
clear方法
public void clear() {
modCount++;//修改次数+1
for (int i = 0; i < size; i++)
elementData[i] = null;//遍历赋值为null
size = 0;//数组中元素的个数置为0
}
总结
- 是一个动态数组，其容量能自动增长，但每次增删都要copy，性能不高，访问的时候通过索引是最快的
- ArrayList线程不安全，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类
