Java ArrayList工作原理及实现

1. 概述

关于Java集合的小抄中是这样描述的:

以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组,因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。按数组下标访问元素—get(i)/set(i,e) 的性能很高,这是数组的基本优势。
直接在数组末尾加入元素—add(e)的性能也高,但如果按下标插入、删除元素—add(i,e), remove(i), remove(e),则要用System.arraycopy()来移动部分受影响的元素,性能就变差了,这是基本劣势。

然后再来学习一下官方文档:

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

ArrayList是一个相对来说比较简单的数据结构,最重要的一点就是它的自动扩容,可以认为就是我们常说的“动态数组”。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList类主要是继承AbstractList类并实现了List接口,实现Cloneable和Serializable接口使得ArrayList具有克隆和序列化的功能。

属性

ArrayList类中主要有两个属性,如下:

transient Object[] elementData; //elementData数组用来存储ArrayList中的元素,从这个可以看出,ArrayList是底层是借组于数组来实现的。
private int size;//此属性用来记录ArrayList中存储的元素的个数。

ArrayList中还有一个默认容量大小属性以及两个空数组属性。它们的声明如下:

1、默认初始容量

private static final int DEFAULT_CAPACITY = 10;//默认初始容量

2、下面两个是共享空常量数组,用于空的实例对象,第二个与第一个的区别文档上面是这么说的:

We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.

翻译一下就是与EMPTY_ELEMENTDATA数组的区别在于当第一个元素被加入进来的时候它知道如何扩张;在源码中函数add(E e)中的第一行代码中的所在的函数就是这句话的实现。

private static final Object[] EMPTY_ELEMENTDATA = {};
//下面这个是共享空常量数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

构造函数

ArrayList类共有3个构造函数,下面一一进行介绍。

1、无参构造函数
/**
  * Constructs an empty list with an initial capacity of ten.
    构造一个初始容量为10的空列表
  */
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

源码上介绍的功能为:
构造一个初始容量为 10 的空列表。

但是这里,默认构造方法只干了一件事,就是将elementData初始化为一个空数组。

那么,为什么说它的默认初始容量是10呢?

答案是 -- 第一次添加元素时。

2、指定容量作为参数的构造函数
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);                                       
        }
    }

从源码可以看到,就是根据参数的大小作为容量来实例化底层的数组对象,其中对参数的3中情况进行了处理。当参数小于0时,抛异常。当参数等于0时,用空的常量数组对象EMPTY_ELEMENTDATA来初始化底层数组elementData。

3、Collection作为参数的构造函数
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;
        }
    }

从源码可以看到,将容器Collection转化为数组赋给数组elementData,还对Collection转化是否转化为了Object[]进行了检查判断。如果Collection为空,则就将空的常量数组对象EMPTY_ELEMENTDATA赋给了elementData;

来看一段简单的代码:

ArrayList<String> list = new ArrayList<String>();
list.add("语文: 99");
list.add("数学: 98");
list.add("英语: 100");
list.remove(0);

在执行这四条语句时,是这么变化的:

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

2. add函数

当我们在ArrayList中增加元素的时候,会使用add函数。他会将元素放到末尾。具体实现如下:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

我们可以看到他的实现其实最核心的内容就是ensureCapacityInternal。这个函数其实就是自动扩容机制的核心。我们依次来看一下他的具体实现

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩展为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩为1.5倍还不满足需求,直接扩为需求值
    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);//第一次添加元素时,newCapacity的大小其实就是DEFAULT_CAPACITY (10)
}

上面grow函数中最后一条语句elementData = Arrays.copyOf(elementData, newCapacity);的功能就是将原来的数组中的元素复制扩展到大小为newCapacity的新数组中,并返回这个新数组。Arrays.copyOf(elementData, newCapacity)的源码如下:

public static int[] copyOf(int[] original, int newLength) {
        int[] copy = new int[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

也就是说,当增加数据的时候,如果ArrayList的大小已经不满足需求时,那么就将数组变为原长度的1.5倍,之后的操作就是把老的数组拷到新的数组里面。例如,默认的数组大小是10,也就是说当我们add10个元素之后,再进行一次add时,就会发生自动扩容,数组长度由10变为了15具体情况如下所示:

3 set和get函数

Array的put和get函数就比较简单了,先做index检查,然后执行赋值或访问操作:

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

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);
    // 把最后的置null
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;

clear

最后要介绍的函数就是这个了,清除ArrayList中所有的元素。

直接将数组中的所有元素设置为null即可,这样便于垃圾回收。

public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

小结:

  1. ArrayList的默认初始容量的确是10;
  2. 使用默认构造方法实例化ArrayList,只初始化了一个空数组;
  3. 第一次调用add()方法时,数组才会被扩容,数组大小为默认的初始容量--10(2是前提)
ArrayList的插入速度比LinkedList的慢?
  • 所以:应该改为 -- 随机插入元素时,ArrayList的速度比LinkedList的慢。
  • 并且 删除元素的道理也是一样的,所以应该是 -- 随机增删元素时,ArrayList的速度比LinkedList的慢
为什么ArrayList的elementData是用transient修饰的?

看到ArrayList实现了Serializable接口,这意味着ArrayList是可以被序列化的,用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么?因为序列化ArrayList的时候,ArrayList里面的elementData未必是满的,比方说elementData有10的大小,但是我只用了其中的3个,那么是否有必要序列化整个elementData呢?显然没有这个必要,因此ArrayList中重写了writeObject方法:

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

每次序列化的时候调用这个方法,先调用defaultWriteObject()方法序列化ArrayList中的非transient元素,elementData不去序列化它,然后遍历elementData,只序列化那些有的元素,这样:

  • 1、加快了序列化的速度
  • 2、减小了序列化之后的文件大小

http://yikun.github.io/2015/04/04/Java-ArrayList%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
https://blog.csdn.net/u010412719/article/details/51108357
https://www.cnblogs.com/xrq730/p/4989451.html
http://www.cnblogs.com/shadowdoor/p/9203926.html

添加新评论