查看原文
其他

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进行并发控制的,只是对我们开发者来说使用起来更方便了。


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


    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存