Java源码分析 – ArrayList

Java源码分析 – ArrayList

ArrayList是什么

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        // ...
}
  • 继承AbstractList - 说明本身数据结构是列表
  • 实现List, RandomAccess, Cloneable, Serializable 这几个接口 - 说明支持List中的各种常用方法

我们通过一个日常使用的例子来说明:

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();

        list.add(1);
        list.add(2);
        System.out.println(list.size());

        list.remove(0);
        System.out.println(list.isEmpty());
        System.out.println(list.get(0));
    }

打印结果:

2
false
2

  • 添加1,2
  • 打印list.size()结果
  • 移除第0位的值
  • 打印list.isEmpty()结果
  • 打印第0位的值

上面是我们常见的使用方法,既然ArrayList的名字里面有Array,它的底层数据结构也是一个数组,那么我们应该也可以指定初始数组的大小

 List<Integer> list = new ArrayList<>(20);

这样子的话list的初始大小就是20了。

我们到源码里面看看:

    // 1
    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);
        }
    }
    // 2
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    // 3
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList一共有3个不同的构造方法:

  • 第一个是传入一个int型的值作为初始化容量
  • 第二个则是无参构造方法,大小为默认值
  • 第三个是传入一个集合,通过toArray() 方法把集合转成数组,再添加到ArrayList中

这里出现了几个常量:

    // 默认的初始化容量大小为10
    private static final int DEFAULT_CAPACITY = 10;

    // 空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 用于无参构造方法调用时的空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

那么问题来了:

EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 区别是什么?

看起来都是空数组,为什么要创建两个空数组对象呢?

ArrayList构造方法

其实答案在上面的3个构造方法里面就有了:

调用有参构造方法但是传入的初始大小为0,这个时候elementData 都是EMPTY_ELEMENTDATA ,也就是说,EMPTY_ELEMENTDATA 代表的就是大小为0的空数组。

调用无参构造方法,那么初始值为:DEFAULTCAPACITY_EMPTY_ELEMENTDATA,这个对象在后面进行扩容的时候需要用到,我们可以看看源码:

// 2  
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    // 1
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // 3
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

在调用add() 方法添加元素的时候,第一步就是调用ensureCapacityInternal()方法来确保有足够的容量。而在 calculateCapacity() 中判断当前数组是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,按照我们上面说的,调用无参构造方法创建ArrayList,那么这里就是true,因此需要返回一个默认值(10)和传入值之间的最大值,作为数组的容量。

我们从创建说起:

  • 调用无参构造方法,此时数组为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,大小为0
  • 调用add()方法,发现当前是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,于是在10和1(list.size() + 1)之间返回最大值,也就是10
  • 此时10>0,调用grow()方法进行扩容

因此ArrayList在调用无参构造方法创建对象的时候,他的初始数组大小也是为0,只有在调用add()方法添加元素的时候才会扩容到默认大小10。

所以这两个空数组对象看起来是一样的,但是实际作用完全不同,一个确实是为空,另外一个只是暂时为空,真正用到的时候再扩容。

ArrayList扩容机制

一般的数组其容量大小是固定的,也就是说我初始化了一个大小为10的数组,那么当我添加了10个元素,要再添加第11个的时候,数组就会抛出数组越界异常(ArrayIndexOutOfBoundsException)。但是ArrayList则不会。它能够实现自动扩容,具体是怎么做到的呢?

Read the Fking Source Code!**

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //1
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //2 判断扩容1.5倍之后的容量大小和最小需要的容量大小,如果扩容后还是小于后者,那么就取后者。简单来说就是取两者之中最大值。
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //3 再判断是不是比最大容量大,如果是的话调用hugeCapacity()
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //4.复制到新的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

注意这里有一行代码: int newCapacity = oldCapacity + (oldCapacity >> 1); 通过位运算来进行扩容。右移一位相当于除以2,但是位运算的效率要高很多。这一行代码的意思就是扩容1.5倍。然后再进行数组的复制。

然后我们再看看hugeCapacity()

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

如果最小需要容量大于ArrayList定义的最大容量,那么就返回Integer.MAX_VALUE,否则返回MAX_ARRAY_SZIE。

System.arraycopy() 和 ArrayList.copyOf()

在上面扩容方法的最后,我们看到复制数组用到的方法是: Arrays.copeOf(),而System.arraycopy()也能实现复制数组的功能。这两个方法有什么区别呢?

Arrays.copyOf()

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

System.arraycopy()

  * @param      src      the source array.
     * @param      srcPos   starting position in the source array.
     * @param      dest     the destination array.
     * @param      destPos  starting position in the destination data.
     * @param      length   the number of array elements to be copied.
     * @exception  IndexOutOfBoundsException  if copying would cause
     *               access of data outside array bounds.
     * @exception  ArrayStoreException  if an element in the <code>src</code>
     *               array could not be stored into the <code>dest</code> array
     *               because of a type mismatch.
     * @exception  NullPointerException if either <code>src</code> or
     *               <code>dest</code> is <code>null</code>.
     */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

可以看到,在Arrays.copyOf()的内部其实也调用了System.arraycopy()。

这两者的区别就是:

  • Arrays.copyOf() 不需要传入目标数组,因为它会返回一个新的数组
  • System.arrayCopy() 则是可以自己指定需要复制的数组,也就是说我们可以用这个方法进行数组元素的快速移动:例如删除某个元素之后,把剩余元素全部向前移动一位。就可以用数组复制的方法来实现。

ArrayList的内部类

ArrayList中有4个内部类:

(1)private class Itr implements Iterator
(2)private class ListItr extends Itr implements ListIterator
(3)private class SubList extends AbstractList implements RandomAccess
(4)static final class ArrayListSpliterator implements Spliterator

其中ListItrItr 的子类,并且重写了以下几个方法:

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
  • hasPrevious:判断是否有前驱结点
  • nextIndex: 下一个节点的索引值
  • previousIndex: 上一个节点的索引值
  • previous: 返回前一个节点
  • set: 修改当前索引的值(当前索引用 lastRet来表示,调用next()方法的时候会修改lastRet)
  • add: 在ArrayList末尾添加元素

总结

我们通过对ArrayList的源码分析,大概了解了ArrayList的底层数据结构,以及它实现的接口和提供API。由于ArrayList是基于数组来实现的,所以它更适用于频繁查询的场景,因为数组可以直接通过下标在O(1)时间复杂度内找到对应的值/对象。而插入或者删除则需要O(n) 的时间复杂度。因为需要移动数组的其他元素。因此不适用于频繁插入/删除的场景。

另外要注意的就是ArrayList的扩容机制。通过位运算来提高效率。

最后在ArrayList中还提供了几个内部类,通过迭代器的模式实现了类似链表的前驱后继节点功能,可以通过next()/previous() 来获得相邻的值。

 
 
 

本文以创作共用版权协议发布,转载本文要求遵循“署名-非商业性使用-相同方式共享3.0”的创作共用协议,并以链接形式指明本文地址。

本文链接地址: https://www.bluelzy.top/java-foundation-arraylist

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注