• ArrayList源码

    ArrayList源码


    参考资料：JDK集合源码之ArrayList解析(附带面试题举例)
    1、注意：此次我用的版本是jdk1.8.0_271，各个版本之间源码还是有差异的
    2、实现RandomAccess接口的ArrayList 进行随机访问的效率高于进行顺序访问的效率。
    继承结构

    ArrayList的属性及构造函数
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    /**
 * 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 空的元素数据：new ArrayList(int initialCapacity)初始容量为0的时候使用
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 默认容量空元素数据：new ArrayList()的时候使用
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 元素数据：集合中真正存储数据元素的数组容器
transient Object[] elementData; // transient标识不被序列化。

/**
 * 集合中元素的个数
 *
 * @serial
 */
private int size;

/**
 * 构造具有指定初始容量的空数组
 *
 * @param  initialCapacity  列表的初始容量
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
	// 传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于0抛出异常。
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

/**
 * 构造一个初始容量为10的空数组
 */
public ArrayList() {
	// 不传初始容量，初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，会在添加第一个元素的时候扩容为默认的大小，即10。
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 根据传入的集合进行构造成ArrayList
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection c) {
	// 1、将构造方法中的集合参数转换成数组
    Object[] a = c.toArray();
    // 2、先将a的长度赋值给size，如果size是否不为0，即表示有数据
    if ((size = a.length) != 0) {
    	// 3、如果类型是ArrayList则直接替换即可
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
        	// 数组的创建与拷贝
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // 如果c是空的集合，则初始化为空数组EMPTY_ELEMENTDATA
        elementData = EMPTY_ELEMENTDATA;
    }
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    }
    ArrayList的add(E e)刨析
    功能：数组尾部直接插入元素，时间复杂度都O(1)
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /**
    * 数组尾部直接插入元素
    */
    public boolean add(E e) {
    // 确保内部容量：当前数据能否容纳size + 1的元素，如果不够，则调用grow(minCapacity)来扩容
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
    }

    // 确保内部容量
private void ensureCapacityInternal(int minCapacity) {
	// 拆分两步
    // 第一：计算能力获取最少容纳的容量数calculateCapacity(elementData, minCapacity)
    // 第二：确保明确容量，进行扩容等处理
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算能力获取最少容纳的容量数
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// 如果是空数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    	// 返回大的一方
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}   
// 确保明确容量，进行扩容等处理
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 当前数组不够存储了，进行扩容操作
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * 增加容量以确保其至少可以容纳最小容量元素数。
 *
 * @param minCapacity 所需的容量数
 */
private void grow(int minCapacity) {
    // 原来的容量
    int oldCapacity = elementData.length;
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量发现比需要的容量还小，则以需要的容量为准
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量已经超过最大容量了，则使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 以新容量拷贝出来一个新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}    

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    }
    ArrayList的add(int index, E element)刨析
    指定数组索引位置插入元素，时间复杂度都O(n)
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /**
    * 指定数组索引位置插入元素
    */
    public void add(int index, E element) {
    // 范围检查是否添加
    rangeCheckForAdd(index);

        // 确保内部容量，这个见add(E e)
    ensureCapacityInternal(size + 1);
    // 数组移动：从elementData数组的index位置开始，复制到elementData数组的index + 1的位置开始，需要复制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));
}    

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    }
    ArrayList的addAll()刨析
    数组尾部直接插入集合元素
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /**
    * 数组尾部直接插入集合元素
    */
    public boolean addAll(Collection c) {
    // 传参集合转换成数组并计算集合长度
    Object[] a = c.toArray();
    int numNew = a.length;

    	// 确保内部容量，这个见add(E e)
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 数据拷贝
    System.arraycopy(a, 0, elementData, size, numNew);
    // 长度累加
    size += numNew;
    return numNew != 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    }
    ArrayList的get()刨析
    获取指定索引位置的元素
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /**
    * 获取指定索引位置的元素
    /
    public E get(int index) {
    // 检查是否越界
    rangeCheck(index);
    // 根据索引取数据
    return elementData(index);
    }
    // 根据索引取数据
    E elementData(int index) {
    return (E) elementData[index];
    }
    }
    ArrayList的remove()刨析
    删除
    ● public E remove(int index)：删除指定索引下标的元素
    ● public boolean remove(Object o) ：删除指定元素
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /    *
    * 删除指定索引位置的元素
    */
    public E remove(int index) {
    // 检查是否越界
    rangeCheck(index);

        modCount++;
    // 根据索引取数据
    E oldValue = elementData(index);
	
    // 计算需要移动的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
    	// 数组移动：从elementData数组的index+1位置开始，复制到elementData数组的index的位置开始，需要复制numMoved个
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // 将最后一个元素删除，帮助GC
	// 返回旧值
    return oldValue;
}

/**
 * 删除指定的元素值：如果存在多个相同元素值,只会删除最先插入的那个
 */
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;
}
/*
 * 快速删除，同public E remove(int index)一样，对比可以看出这源码为了性能还是很用心的。
 */
private void fastRemove(int index) {
    modCount++;
    // 计算需要移动的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
    	// 数组移动：从elementData数组的index+1位置开始，复制到elementData数组的index的位置开始，需要复制numMoved个
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}    

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    }
    ArrayList的retainAll()交集刨析
    两个集合的交集
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /**
    * 两个集合的交集，最终当前数组会删除所有未包含在指定集合中的元素。
    /
    public boolean retainAll(Collection c) { // 空值判断：c == null 抛异常 Objects.requireNonNull(c); // 批量删除，这时complement传入true，表示删除不包含在c中的元素 return batchRemove(c, true); } /** * 批量删除元素 * complement为true表示删除c中不包含的元素 * complement为false表示删除c中包含的元素 * @param c * @param complement * @return */ private boolean batchRemove(Collection c, boolean complement) {
    final Object[] elementData = this.elementData;
    /    *
    * 使用读写两个指针同时遍历数组
    * 读指针每次自增1，写指针放入元素的时候才加1
    * 这样不需要额外的空间，只需要在原有的数组上操作就可以了
    /
    int r = 0, w = 0;
    boolean modified = false;
    try {
    // 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准）
    for (; r < size; r++)
    if (c.contains(elementData[r]) == complement)
    elementData[w++] = elementData[r];
    } finally {
    // Preserve behavioral compatibility with AbstractCollection,
    // even if c.contains() throws.
    // 正常来说r最后是等于size的，除非c.contains()抛出了异常
    if (r != size) {
    // 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
    System.arraycopy(elementData, r, elementData, w, size - r);
    w += size - r;
    }
    if (w != size) {
    // 将写指针之后的元素置为空，帮助GC
    for (int i = w; i < size; i++)
    elementData[i] = null;
    // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）
    modCount += size - w;
    size = w;
    modified = true;
    }
    }
    // 有修改返回true
    return modified;
    }
    }
    ArrayList的removeAll刨析
    从当前集合中移除
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /    *
    * 删除传入集合的元素值
    /
    public boolean removeAll(Collection c) { // 空值判断：c == null 抛异常 Objects.requireNonNull(c); // 批量删除，同样调用批量删除方法，这时complement传入false，表示删除包含在c中的元素 return batchRemove(c, false); } /** * 批量删除元素 * complement为true表示删除c中不包含的元素 * complement为false表示删除c中包含的元素 * @param c * @param complement * @return */ private boolean batchRemove(Collection c, boolean complement) {
    final Object[] elementData = this.elementData;
    /    *
    * 使用读写两个指针同时遍历数组
    * 读指针每次自增1，写指针放入元素的时候才加1
    * 这样不需要额外的空间，只需要在原有的数组上操作就可以了
    */
    int r = 0, w = 0;
    boolean modified = false;
    try {
    // 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准）
    for (; r < size; r++)
    if (c.contains(elementData[r]) == complement)
    elementData[w++] = elementData[r];
    } finally {
    // Preserve behavioral compatibility with AbstractCollection,
    // even if c.contains() throws.
    // 正常来说r最后是等于size的，除非c.contains()抛出了异常
    if (r != size) {
    // 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
    System.arraycopy(elementData, r, elementData, w, size - r);
    w += size - r;
    }
    if (w != size) {
    // 将写指针之后的元素置为空，帮助GC
    for (int i = w; i < size; i++)
    elementData[i] = null;
    // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）
    modCount += size - w;
    size = w;
    modified = true;
    }
    }
    // 有修改返回true
    return modified;
    }
    }
    ArrayList的toString()刨析

    public abstract class AbstractCollection implements Collection {
    /**
    *
    /
    public String toString() {
    // 获取集合的迭代器对象
    Iterator it = iterator();
    // 没有元素，返回[]
    if (! it.hasNext())
    return “[]”;
    // 有数据进行拼接[e1, e2]
    StringBuilder sb = new StringBuilder();
    sb.append(‘[’);
    for (;😉 { // 无限循环 == while(true)
    E e = it.next();
    sb.append(e == this ? “(this Collection)” : e);
    if (! it.hasNext())
    return sb.append(‘]’).toString();
    sb.append(‘,’).append(’ ');
    }
    }
    }
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    public Iterator iterator() {
    return new Itr();
    }
    }
    总结
    （1）ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
    （2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
    （3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
    （4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
    （5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；
    （6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；
    （7）ArrayList支持求并集，调用addAll(Collection c)方法即可；
    （8）ArrayList支持求交集，调用retainAll(Collection c)方法即可；
    （7）ArrayList支持求单向差集，调用removeAll(Collection c)方法即可；
    transient关键字如何序列化&反序列化
    public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    /    *
    * 实例的状态保存到流中 (即对其序列化).
    *
    * @serialData The length of the array backing the ArrayList
    * instance is emitted (int), followed by all of its elements
    * (each an Object) in the proper order.
    */
    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    // 防止序列化期间有修改
    int expectedModCount = modCount;
    // 写出非transient非static属性（会写出size属性）
    s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
    // 写出元素个数
    s.writeInt(size);

    // 依次写出元素
    for (int i=0; i ArrayList 实例（即,反序列化）
 */
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
	// 声明为空数组
    elementData = EMPTY_ELEMENTDATA;

    // 读入非transient非static属性（会读取size属性）
    s.defaultReadObject();

    // 读入元素个数，没什么用，只是因为写出的时候写了size属性，读的时候也要按顺序来读
    s.readInt(); // 忽略

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        // 计算容量
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        // 检查是否需要扩容
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        // 依次读取元素到数组中
        for (int i=0; i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    }
    面试题
    扩容机制
    第一次扩容10，以后每次都扩容原容量的1.5倍，扩容通过位运算右移动1位。
    频繁扩容导致添加性能急剧下降的处理
    指定初始化容量：public ArrayList(int initialCapacity)
    ArrayList插入或删除元素是否一定比LinkedList慢？
    效率对比：
    ● 首部插入：LinkedList首部插入数据很快，因为只需要修改插入元素前后节点的prev值和next值即可。ArrayList首部插入数据慢，因为数组复制的方式移位耗时多。
    ● 中间插入：LinkedList中间插入数据慢，因为遍历链表指针（二分查找）耗时多；ArrayList中间插入数据快，因为定位插入元素位置的速度快，移位操作的元素没那么多。
    ● 尾部插入：LinkedList尾部插入数据慢，因为遍历链表指针（二分查找）耗时多；ArrayList尾部插入数据快，为定位插入元素位置的速度快，插入后移位操作的数据量少；
    总结：
    ● 在集合里面插入元素速度比对结果是：首部插入，LinkedList更快；中间和尾部插入，ArrayList更快；
    ● 在集合里面删除元素类似，首部删除，LinkedList更快；中间删除和尾部删除，ArrayList更快；
    因此，数据量不大的集合，主要进行插入、删除操作，建议使用LinkedList；数据量大的集合，使用ArrayList就可以了，不仅查询速度快，并且插入和删除效率也相对较高。
    线程安全问题
    1、使用Vector类
    2、List list = Collections.synchronizedList(new ArrayList());
    3、CopyOnWriteArrayList
    并发修改
    public static void main(String[] args) {
    ArrayList strings = new ArrayList<>(Arrays.asList(“A”, “B”, “C”, “D”, “E”));
    for (String s : strings) {
    // 抛异常java.util.ConcurrentModificationException
    strings.add(“111”);
    }

    CopyOnWriteArrayList copyOnWriteArrayList = new CopyOnWriteArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
for (String s : copyOnWriteArrayList) {
    // 正常
    copyOnWriteArrayList.add("111");
}

    • 1
    • 2
    • 3
    • 4
    • 5

    }

  • 相关阅读:
    RHCSA认证考试---8.配置 autofs
    js垃圾回收机制
    阿里技术大牛亲自编写，将高难度的 Java 高并发知识讲解得浅显易懂
    有限体积法求解一维非稳态对流扩散方程
    【QT】界面布局-登陆窗口
    Java编程案例：买飞机票
    ​软考-高级-系统架构设计师教程（清华第2版）【第14章 云原生架构设计理论与实践（P496~526）-思维导图】​
    Windows如何将软件安装在移动硬盘上？
    数据结构基础学习
    系统架构师案例分析（真题知识点整理、记忆）
  • 原文地址：https://blog.csdn.net/u013474568/article/details/126529360