当前位置:网站首页>ArrayList源码分析

ArrayList源码分析

2020-11-08 09:41:48 凯宝宝

1. AzrrayList 简介

java.util.ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它具有容量能动态增长、元素增删慢、查找快的特点。

ArrayList继承于 AbstractList,实现了 ListRandomAccessCloneablejava.io.Serializable 这些接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        --- omit ---
  }
  • ArrayList 继承了AbstractList抽象方法,实现了List接口,提供了相关的添加、删除、修改、遍历等功能。
  • RandomAccess 是一个标志接口,表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中,我们即可以通过元素的序号快速获取元素对象,这就是快速随机访问。
  • ArrayList 实现了 Cloneable 接口,即覆盖了函数clone(),能被克隆。
  • ArrayList 实现了 java.io.Serializable 接口,这意味着ArrayList支持序列化,能通过序列化去传输。
Tips: ArrayList中的操作不是线程安全的!建议在单线程中才使用 ArrayList,多线程中选择使用Vector或者 CopyOnWriteArrayList

2. ArrayList源码简析(JDK 1.8)

2.1 成员属性

// 默认容量大小
private static final int DEFAULT_CAPACITY = 10;

// ArrayList空实例共享的一个空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// ArrayList空实例共享的一个空数组,用于默认大小的空实例。
// 与EMPTY_ELEMENTDATA分开,这样就可以了解当添加第一个元素时需要创建多大的空间。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 真正存储ArrayList中的元素的数组
transient Object[] elementData;

// ArrayList 所包含的元素个数,注意并不是elementData的长度
private int size;

// 数组的最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

AbstractList抽象类中唯一属性:

// 表示elementData被修改的次数,每次add或者remove它的值都会加1
protected transient int modCount = 0;

为什么size不是用来标记elementData数组的长度呢?

在Java中,一般来说:

  • length属性是针对数组而言的,比如下面源码中elementData.length表示elementData数组的长度。
  • length() 方法是针对字符串而言的,可以调用 length() 获取字符串长度。
  • size() 方法是针对泛型集合而言的,可以调用size()来获取集合中个数。

这样,就很好理解为什么size不是ArrayList的长度了,不易记混。

2.2 构造方法

ArrayList有三种初始化方式:

    /**
     * 有参的构造函数
     */    
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 初始化容量大于0,创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 初始化容量等于0,创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 默认无参构造函数(未指定初始化容量大小),使用初始容量10构造一个空列表。
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 使用Collection集合来初始化ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        // 将集合转换为数组
        elementData = c.toArray();
        // 如果数组的长度size不等于0
        if ((size = elementData.length) != 0) {
            // 如果返回的不是Object类型数据
            if (elementData.getClass() != Object[].class)
                // 重新创建一个size大小的数组。
                // 并将原来不是Object[]数组的内容,Copy给新的是Object[]的数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 用空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

从上面的分析中看出EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别

EMPTY_ELEMENTDATA表示在我们实例化对象时指定了容量就是0,当添加1个元素后,那么elementData.length=1。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示实例化时是无参构造,未指定容量,在调用add方法添加第1个元素后会默认扩容容量为10,即elementData.length=10。

2.3 添加元素

    /**
     * 直接将元素添加到数组末尾。
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     * 将元素添加到指定index位置。
     */
    public void add(int index, E element) {
        // 对index进行界限检查
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // native静态方法,原elementData数组的index(包含)之后的数据,复制到目标elementData数组的index + 1之后位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将从index开始之后的所有成员后移一个位,将element插入到index位置。
        elementData[index] = element;
        // 最后size+1
        size++;
    }

    /**
     * 将指定集合中的所有元素追加到此列表的末尾。
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 从指定的位置开始,将指定集合中的所有元素插入到此列表中。
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

源码中大量调用了arraycopy()方法,其具体使用可以参考由 System.arraycopy 引发的巩固:对象引用 与 对象 的区别一文。

2.4 删除元素

    /**
     * 删除列表中指定位置的元素。将任何后续元素移动到左侧(从其索引中减1)。
     */
    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;
          // 从列表中删除的元素
        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++)
                // 返回true,此列表包含指定的元素
                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;
    }

    /**
     * 从列表中删除所有元素。
     */
    public void clear() {
        modCount++;

        // 把数组中所有的元素的值设为null
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    /**
     * 从此列表中删除所有索引为fromIndex (包含)和toIndex之间的元素。
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

    /**
     * 从此列表中删除指定集合中包含的所有元素。
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        // 如果此列表被修改则返回true
        return batchRemove(c, false);
    }

2.5 ArrayList扩容机制

可以发现,ArrayList添加元素时,都会调用ensureCapacityInternal方法。

以add(E e)方法为例:

    /**
     * 直接将元素添加到数组末尾。
     */
    public boolean add(E e) {
        // 检查是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2.5.1 ensureCapacityInternal()ensureExplicitCapacity()

查看ensureCapacityInternal()方法:

    // 获取到满足需求的最小容量
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // elementData是空列表
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
             // 扩容数组到DEFAULT_CAPACITY(10)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // return size+1
        return minCapacity;
    }

    // 判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity - elementData.length > 0)
            //调用grow方法进行真正地扩容
            grow(minCapacity);
    }
  1. 当添加第1个元素到 ArrayList 中时,minCapacity 为size+1=0,elementData还是空的list,elementData.length=0 ,所有会执行return Math.max(DEFAULT_CAPACITY, minCapacity);,minCapacity变为10。此时,minCapacity - elementData.length > 0成立,所以会进入 grow(minCapacity) 方法真正扩容。
  2. 当添加第2个元素时,minCapacity 为 size+1 =2,由于elementData.length在添加第一个元素后已经扩容成10了。此时,minCapacity - elementData.length > 0 不成立,不会执行grow(minCapacity) 方法,即不会扩容。
  3. 添加第 3、4、5......到第10个元素时,依然不会扩容,数组容量还是为10。

直到添加第11个元素,minCapacity - elementData.length > 0 成立,执行grow 方法进行扩容。

2.5.2 grow()

grow方法是整个ArrayList扩容的核心:

    private void grow(int minCapacity) {//11
        // oldCapacity为旧容量
        int oldCapacity = elementData.length;//10
        // 位移运算符比普通运算符的运算快很多。>>表示将oldCapacity右移一位,(oldCapacity >> 1)相当于oldCapacity /2
        // 将新容量更新为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 若新容量还是小于最小需求容量
        if (newCapacity - minCapacity < 0)
            // 直接最小需求容量当作数组的新容量
            newCapacity = minCapacity;
       //如果minCapacity大于最大容量,则新容量则为`Integer.MAX_VALUE`,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
        // 新容量大于MAX_ARRAY_SIZE,
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 执行hugeCapacity()方法
            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    // 比较minCapacity和MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();

        // minCapacity > MAX_ARRAY_SIZE,新数组的大小为Integer.MAX_VALUE
        // 否则,新数组的大小为MAX_ARRAY_SIZE
        // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

由此可知,ArrayList默认扩容大小是原大小的1.5倍左右(oldCapacity为偶数肯定是 1.5 倍,为奇数肯定就是等于1.5倍左右)。

  • 如果扩容后的newCapacity仍小于minCapacity,那么就将数组大小调整为minCapacity大小。
  • 如果minCapacity的值在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间,那么新数组分配Integer.MAX_VALUE大小,否则分配MAX_ARRAY_SIZE。
">>"(右移运算符):”>>1“表示右移1位;右移n位相当于除以2的n次方。

2.6 ensureCapacity

从上面源码分析,在使用Arraylist初始化容量时,就会通过一系列逻辑判断后再进行扩容。如果数据量很大,运行效率岂不是很低。

ensureCapacity()方法,就是让我们预先设置Arraylist的大小,这样就可以大大提高初始化速度了。

    public void ensureCapacity(int minCapacity) {
        // 以此来判断我们实例化时是否调用无参构造函数。如果不是,minExpand=0;如果是,minExpand=10。
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        // 我们设置的minCapacity大于minExpand才进行扩容
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

最好在 add 大量元素之前用 ensureCapacity 方法,以减少增量重新分配的次数

下面就来测试一下使用ensureCapacity前后的区别:

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int minCapacity = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < minCapacity; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("不使用ensureCapacity耗时:" + (endTime - startTime));

        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(minCapacity);
        for (int i = 0; i < minCapacity; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity耗时:" + (endTime1 - startTime1));
    }
}

运行结果:

不使用ensureCapacity耗时:2471
使用ensureCapacity耗时:289

3 遍历

ArrayList主要支持三种遍历方式:

  • foreach循环遍历
Integer value = null;
for (Integer integ:list) {
    value = integ;
}
  • 迭代器遍历
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}
  • 随机访问,通过索引值去遍历

由于ArrayList实现了RandomAccess接口,它支持通过索引值去随机访问元素。

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
    value = (Integer)list.get(i);        
}

4 fail-fast机制

快速失败(fail-fast) 是 Java 集合中的一种错误检测机制。它的特性就是在遍历Java集合时,不允许进行值的修改,否则会抛出ConcurrentModificationException异常。

例如在多线程开发中,线程A正在通过iterator遍历某集合,线程B恰巧对该集合的内容进行了修改,那么线程A继续遍历集合就会抛出ConcurrentModificationException异常,产生fail-fast事件。

查看AbstractList源码:

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    ... ...

    // 用来记录List修改的次数:每修改一次(添加/删除等操作),将modCount+1
    protected transient int modCount = 0;

    // 返回List对应迭代器。实际上,是返回Itr对象。
    public Iterator<E> iterator() {
        return new Itr();
    }

    // Itr是Iterator(迭代器)的实现类
    private class Itr implements Iterator<E> {
        int cursor = 0;

        int lastRet = -1;

        // 修改数的记录值。
        // 每次新建Itr()对象时,都会保存新建该对象时对应的modCount。
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
            checkForComodification();
            --- omit ---
        }

        public void remove() {
            if (lastRet == -1)
                throw new IllegalStateException();
            checkForComodification();
            --- omit ---
        }

        final void checkForComodification() {
            // 每次遍历List中的元素的时候,都会比较expectedModCount和modCount是否相等。
            // 若不相等,则抛出ConcurrentModificationException异常,产生fail-fast事件。
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
     ... ...   
}

可见,ArrayList在添加或者删除元素时,无论是调用add()、remove()还是clear()等其他方法,只要涉及到修改集合中的元素个数时,都会改变modCount的值。

而每当迭代器遍历下一个元素之前,都会检测 modCount 变量是否为 expectedModCount 值。如果在集合被遍历期间修改 modCount 的值,那么 modCount != expectedModCount ,进而抛出 ConcurrentModificationException 异常。

因此,在多线程开发中,建议使用java.util.concurrent包下的线程安全类去取代java.util包下的线程不安全类。比如ArrayList对应的线程安全类为CopyOnWriteArrayList

特别注意的是,并不是只有在多线程中才会出现fail-fast事件。在单线程下,如果遍历过程中对集合对象的内容进行了修改的话也会触发 fail-fast 机制

foreach循环也是借助迭代器进行遍历的。

应该避免写出类似这样的代码:

        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        for (String str : list) {
            if("b".equals(str)){
                list.remove(str);
            }
        }

参考

版权声明
本文为[凯宝宝]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000037760453