ArrayList是List接口的实现类

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
}

image-20210624173750562

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));
}

这样每增加一个元素就要把当前索引复制到该元素的后面,开销很大

评论

暂无评论