ArrayList必知必会

作者：feigeswjtu

GitHub地址：https://github.com/feigeswjtu

ArrayList一些说法

顾名思义，以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy（）复制到新的数组。因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。 

按数组下标访问元素－get(i）、set(i, e) 的性能很高，这是数组的基本优势。 如果按下标插入元素、删除元素－add（i,e）、 remove（i）、remove（e），则要用System.arraycopy（）来复制移动部分受影响的元素，性能就变差了。 越是前面的元素，修改时要移动的元素越多。直接在数组末尾加入元素－常用的add（e），删除最后一个元素则无影响。

我们先通过一段简单的代码来看下内存变化。

1. List<String> list = new ArrayList<>();

2. list.add("语文: 99");

3. list.add("数学: 98");

4. list.add("英语: 100");

5. list.remove(0);

内存变化图: 

 其中，add操作可以理解为直接将数组的内容置位，remove操作可以理解为删除index为0的节点，并将后面元素移到0处。 

ArrayList的类声明如下:

1. public class ArrayList<E> extends AbstractList<E>

2.        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

3. {

4.    //...

5. }

实现了List接口，说明ArrayList是List的一个实现类，实现了RandomAccess(RandomAccess接口说明)说明ArrayList支持随机访问。

ArrayList初始化

ArrayList重载了多个构造方法，我们挑两个介绍一下。

1. /**

2.     * 默认初始化容量

3.     */

4.    private static final int DEFAULT_CAPACITY = 10;

5.    /**

6.     * ArrayList共享的空数组，这样节省内存

7.     */

8.    private static final Object[] EMPTY_ELEMENTDATA = {};

9.    /**

10.     * 如果使用默认size时，共享的空数组

11.     * 第一个元素增加时会重新初始化elementData

12.     */

13.    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

14.    /**

15.     * 真正存储的数组

16.     */

17.    transient Object[] elementData; // non-private to simplify nested class access

18.    /**

19.     * List的元素数量

20.     */

21.    private int size;

22.     /**

23.     * 带有初始化容量的构造方法

24.     */

25.    public ArrayList(int initialCapacity) {

26.        if (initialCapacity > 0) {

27.            this.elementData = new Object[initialCapacity];

28.        } else if (initialCapacity == 0) {

29.            this.elementData = EMPTY_ELEMENTDATA;

30.        } else {

31.            throw new IllegalArgumentException("Illegal Capacity: "+

32.                                               initialCapacity);

33.        }

34.    }

35.     /**

36.     * 使用默认容量的构造方法，在放入第一个元素时进行初始化

37.     */

38.    public ArrayList() {

39.        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

40.    }

ArrayList的add方法

当然我们向ArrayList放入元素时，会使用add方法，这个方法会把元素放在队尾，源码如下:

1. public boolean add(E e) {

2.        ensureCapacityInternal(size + 1);  // Increments modCount!!

3.        elementData[size++] = e;

4.        return true;

5.    }

代码表面很简单，但是有一个稍微复杂的ensureCapacityInternal方法，可以看出ensureCapacityInternal方法才是add的核心，这段代码就是用来扩容的，代码如下:

1. // 计算最小扩容的大小

2.    private static int calculateCapacity(Object[] elementData, int minCapacity) {

3.        //如果List初始化之后还未进行过插入操作，返回默认容量和扩容容量的最大的值

4.        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

5.            return Math.max(DEFAULT_CAPACITY, minCapacity);

6.        }

7.        return minCapacity;

8.    }

9.    // 扩容操作入口

10.    private void ensureCapacityInternal(int minCapacity) {

11.        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

12.    }

13.    // 真正的扩容操作

14.    private void ensureExplicitCapacity(int minCapacity) {

15.        // 修改次数+1

16.        modCount++;

17.        // 如果扩容的容量大于已经存在的容量，则才进行扩容

18.        if (minCapacity - elementData.length > 0)

19.            grow(minCapacity);

20.    }

21.    private void grow(int minCapacity) {

22.        // overflow-conscious code

23.        int oldCapacity = elementData.length;

24.        // 扩展为原来的1.5倍

25.        int newCapacity = oldCapacity + (oldCapacity >> 1);

26.        // 如果扩为1.5倍还不满足需求，直接扩为需求值

27.        if (newCapacity - minCapacity < 0)

28.            newCapacity = minCapacity;

29.        if (newCapacity - MAX_ARRAY_SIZE > 0)

30.            newCapacity = hugeCapacity(minCapacity);

31.        // minCapacity is usually close to size, so this is a win:

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

33.    }

ArrayList的get和set方法

get和set操作比较简单了，就是对下标对应的元素进行set和get操作。

1. public E get(int index) {

2.        rangeCheck(index);

3.        return elementData(index);

4.    }

5.    public E set(int index, E element) {

6.        rangeCheck(index);

7.        E oldValue = elementData(index);

8.        elementData[index] = element;

9.        return oldValue;

10.    }

在这两个方法的最前面会校验一下传入的下标(index)是否合法，如果不再合法的范围内会抛出异常IndexOutOfBoundsException。

1. private void rangeCheck(int index) {

2.        if (index >= size)

3.            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

4.    }

remove方法

最后介绍一下remove方法:

1. public E remove(int index) {

2.        //检测下标值(index)的合法性

3.        rangeCheck(index);

4.        modCount++;

5.        E oldValue = elementData(index);

6.        int numMoved = size - index - 1;

7.        //如果remove的不是最后一个元素，把后面的往前移动

8.        if (numMoved > 0)

9.            System.arraycopy(elementData, index+1, elementData, index,

10.                             numMoved);

11.        //下标对应的值赋值为null，以便于GC可以回收这个对象占用的内存

12.        elementData[--size] = null; // clear to let GC do its work

13.        return oldValue;

14.    }

ArrayList不是线程安全的

最后说明一下ArrayList不是线程安全的，如果要做到线程安全，需要我们自己对ArrayList进行加锁操作，或者使用锁或者使用synchronized，另外还可以用Collections提供的synchronizedList()进行操作，实际上synchronizedList()方法就是使用了synchronized进行并发控制的，只是对我们开发者来说使用起来更方便了。

关注后端技术精选，每天推送优质好文