本文基于JDK1.8源码剖析来剖析,ArrayList顾名思义,数组的结构来表明一个List,先上一张图抛砖引玉:

ArrayList源码分析

这张图表明的便是恳求了容量capacity为10的array buffer,但是有用容量size为1的情况。 开始剖析源码:

1. 特点及结构办法

先来看他的几个特点和结构办法:

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // non-private to simplify nested class access
    private int size;
    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);
        }
    }
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    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;
        }
    }

相信咱们看完这个代码的第一个疑问肯定是为什么要搞两个空Object数组出来。

  1. EMPTY_ELEMENTDATA
  2. DEFAULTCAPACITY_EMPTY_ELEMENTDATA

这两个都是空数组,其实要搞清楚这个问题看一下他们别离在什么地方运用就好了。

  1. 首先是EMPTY_ELEMENTDATA,他一切被运用的地方都是在初始化的时分size为0的时分被赋值给elementData,所以它的效果便是在size为0的时分不用去创建一个空数组了,而是提前创建好了放在那儿,便利被运用。
  2. 再看DEFAULTCAPACITY_EMPTY_ELEMENTDATA,他被运用的场景是在默许结构办法的时分被赋值给elementData,然后在add扩容的时分,被用来做判别。也便是说它的含义是告诉后边的代码当前是空的,需求被扩容成默许巨细DEFAULT_CAPACITY = 10

其实深一点说它的效果是做一个时刻上的拖延处理,咱们每次new ArrayList()的时分其实这个时分并没有给咱们恳求内存,只要在add的时分才会恳求10个内存空间,它的含义在这儿。

那咱们来看结构办法,三个结构办法,其实没什么好说的,看完上面咱们的一个解说其实咱们应该好了解了。

这儿要留意的是假如咱们调用了一个new ArrayList(20),是直接恳求了一个20的数组,而不是从0开始扩容,即使是new了一个ArrayList(Integer.MAX_VALUE)也是这样,并没有触发扩容,后边add的时分才会扩容。

好的,那既然是调集类,那咱们别离来看它的增修改查办法~

2. add

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        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;
    }

四个add办法,分为两种用法:

  1. add单个
  2. addAll

咱们发现这些办法都调用到了一个叫做ensureCapacityInternal的办法,下面看它的代码:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
//初始化成DEFAULTCAPACITY_EMPTY_ELEMENTDATA的时分容量赋值成DEFAULT_CAPACITY
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0) //①
            grow(minCapacity);
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
     private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? //④
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

首先先回忆一下上面咱们说的add的时分关于赋值成DEFAULTCAPACITY_EMPTY_ELEMENTDATA用来做拖延恳求内存的常识,在calculateCapacity办法里边.

2.1. 扩容

下面就到了ArrayList的核心办法grow扩容。
咱们先从最不鸿沟的情况看起,先了解一个最简略的扩容机制,capacity容量size都为10的时分再add一个是怎样触发grow的,grow办法里边真实起效果的便是下面两句了。

// 15 = 10 + (10 >> 1) = 10 + 5
int newCapacity = oldCapacity + (oldCapacity >> 1);
//复制数据
elementData = Arrays.copyOf(elementData, newCapacity);

看起来也不难,那其实写东西理清了思路逻辑就那么一点,其实真实难处理的和容易出问题的都在鸿沟上。咱们看到在grow办法里边有一些if来处理鸿沟条件,我在上面的if后边标了①②③④的注释,咱们别离看一下能触发这些if的条件。
. 由于每次都会调用查看是否需求扩容,那判别只要大于elementData.length的时分才需求扩容。
. 这句是说oldCapacity扩容1.5倍之后假如比需求的minCapacity还要小,那就直接用minCapacity作为newCapacity来做扩容。这个其实很好了解,在addAll的时分假如需求add的调集很大的时分就会呈现这种情况。
比方:

List src = new ArrayList(10);
List tar = new ArrayList(10);
src.addAll(tar);

那很明显oldCapacity = 10; 扩容1.5后newCapacity = 15,而minCapacity = 20。 ③④,这俩其实是一同的。假如扩容后的newCapacity大于MAX_ARRAY_SIZE,也便是大于Integer.MAX_VALUE - 8或者爽性大于Integer.MAX_VALUE最大值,这个时分就直接赋值为Integer.MAX_VALUE
这个时分其实咱们还留意到hugeCapacity这儿有这么一个判别:

if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();

那什么时分会小于零呢?咱们知道java里边int是没有所谓的unsigned的概念的,也便是无符号的概念。这儿可以看一下我写过的一篇文章一次与或非操作实战,也便是说超过了Integer.MAX_VALUE就变成负数了。所以假如恳求的超过最大值就直接抛OOM了。

那其实看完扩容,add就很简略了,不解说了,直接上图。

2.2. add(E e)

add单个元素:

ArrayList源码分析

2.3. add(int index, E element)

ArrayList源码分析

2.4. Collection<? extends E> c

ArrayList源码分析

这儿需求留意的是addAll的时分,不管被add的List的size是多大的,只会扩一次容。一次性到需求的capacity。

3. get set

那其实getset就简略的很了,没几句代码,由于是ArrayList,优势便是在可以以O(1)的时刻复杂度找到需求的方位,很简略就不解说了。

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
     public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

4. remove

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; // clear to let GC do its work
        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;
    }
     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; // clear to let GC do its work
    }

那看代码来说,remove(int index)remove(Object o)肯定是功率不一样的,一个O(1)一个是O(n)。这是remove单个的时分,便是找到需求移除的index的办法不一样,那找到之后的工作量都是由System.arraycopy来完成的,附图:

ArrayList源码分析

那removeAll的代码如下

     public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
     public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    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)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

我也是在看的时分才发现有retainAll这么个办法,跟removeAll的区别只要一个标志位。那含义便是彻底相反的,咱们知道removeAll是把方针调集全部移除去,retainAll刚好相反,是只保存方针调集里的元素. 就比方说有listA: [0, 1, 2, 3, 4],同时有listB: [1, 2, 3]

  1. listA.removeAll(listB) => listA: [0, 4]
  2. listA.retainAll(listB) => listA: [1, 2, 3]

那咱们来看removeAll,complement为false,关键办法batchRemove ,这儿面有两个变量rw,咱们还是拿listA.removeAll(listB)来举比如:

r会循环0 ... 4:

  1. 第一遍循环,r= 0w = 0 ,这时listB包括elementData[0]=0不建立,所以把elementData[0]赋值给elementData[w=0],然后w++之后w = 1
  2. 第二遍循环,r= 1w = 1,这时listB包括elementData[1] = 1建立,不做赋值
  3. 第三遍循环,r= 2w = 1,这时listB包括elementData[2] = 2建立,不做赋值
  4. 第四遍循环,r= 3w = 1,这时listB包括elementData[3] = 3建立,不做赋值
  5. 第五遍循环,r= 4w = 1,这时listB包括elementData[4] = 4不建立,elementData[4]赋值给elementData[w=1],然后w++之后w = 2

循环完毕。这时分removeAll操作就完成了。retainAll的操作便是刚好相反,下面附一张图,更直观:

ArrayList源码分析