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类

ArrayList集合底层原理

ArrayList集合特点及源码分析

ArrayList源码分析

成员变量

构造函数

增加方法

add(E e)方法

add(int index, E element)方法

删除方法

remove(int index)方法

remove(Object o)方法

removeAll(Collection<?> c)方法

其他方法

indexOf(Object o)方法

lastIndexOf(Object o)

set(int index, E element)方法

get(int index)方法

clear方法

总结

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

ArrayList集合底层原理

ArrayList集合特点及源码分析

ArrayList源码分析

成员变量

构造函数

增加方法

add(E e)方法

add(int index, E element)方法

删除方法

remove(int index)方法

remove(Object o)方法

removeAll(Collection<?> c)方法

其他方法

indexOf(Object o)方法

lastIndexOf(Object o)

set(int index, E element)方法

get(int index)方法

clear方法

总结

热门文章

最新文章

相关课程

相关电子书