Java容器解析——ArrayList

Java容器解析——ArrayList

Java容器解析——LinkedList

Java容器解析——Hashtable

1 前言

Java的JDK中为开发者封装了各种类型的容器，以帮助开发人员提高开发效率。为了不当一名只会搬代码的码农，我们需要了解容器背后的秘密，能够更好的掌握Java。本系列开篇将从最简单的容器——ArrayList讲起。

2 ArrayList类定义

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

从ArrayList的定义可以得出：

1. ArrayList<E>：说明ArrayList支持泛型。
2. ArrayList继承了AbstractList。AbstractList是List接口的骨干实现，以最大限度地减少“随机访问”数据存储（如ArrayList）实现Llist所需的工作。
3. implements List<E>：实现了List接口。实现了所有可选列表操作。
4. implements RandomAccess：实现RandomAccess接口，说明ArrayList支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
5. implements Cloneable：实现Cloneable接口，表明其可以调用clone()方法来返回实例的field-for-field拷贝。
6. implements java.io.Serializable：实现Serializable接口，说明ArrayList具有序列化功能。

3 属性值

ArrayList中主要包含以下属性，对于属性的说明在代码注释中。

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

// 指定该ArrayList容量为0时，返回该空数组。
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。
 * 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 保存添加到ArrayList中的元素。
 * ArrayList的容量就是该数组的长度。
 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，数组将扩容值DEFAULT_CAPACITY。
 * 被标记为transient，在对象被序列化的时候不会被序列化。
 */
transient Object[] elementData; 

// 容器中实际存储的元素个数
private int size;

elementData对象标记为transient，表明在对象被序列化的时候不会被序列化。那么该对象的序列化和反序列化过程就需要由ArrayList实现，下面为ArrayList中实现elementData序列化的过程。

    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();
        }
    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i = 0; i < size; i++) {
                a[i] = s.readObject();
            }
        }
    }

4 构造函数

1）无参数构造，初始容量采用默认值为10

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2）指定初始化容量为capacity

    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）使用集合创建

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {

            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

5 核心方法

方法名	含义	时间复杂度
get(int index)	根据索引获取元素	O(1)
add(E e)	添加元素	O(1)
add(int index, E element)	添加元素到指定位置	O(n)
remove(int index)	删除索引为index的元素	O(n)
set(int index, E element)	设置索引为index的元素值	O(1)
size()	返回当前容器元素大小	O(1)
isEmpty()	判断容器是否为空	O(1)
contains(Object o)	判断是否包含某个元素	O(n)
indexOf(Object o)	获取某元素在列表中索引	O(n)
clear()	清空列表	O(n)

6 add()方法

add()方法是向集合中添加一个元素，那么在添加过程中都发生了什么呢？

    /**
     * 添加元素到list末尾.
     *
     * @param e 被添加的元素
     * @return true
     */
    public boolean add(E e) {
        //确保list的容量大小，如果当前空间不足，容量加1。
        ensureCapacityInternal(size + 1);
        //将新元素添加在末尾位置       
        elementData[size++] = e;
        return true;
    }
    
    /**
     * 在制定位置插入元素。当前位置的元素和index之后的元素向后移一位
     *
     * @param index 即将插入元素的位置
     * @param element 即将插入的元素
     * @throws IndexOutOfBoundsException 如果索引超出size
     */
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //确保list的容量大小，如果当前空间不足，容量加1。
        ensureCapacityInternal(size + 1); 
        //将index位置之后的元素后移
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        //将元素添加在index位置
        elementData[index] = element;
        //容量加1
        size++;
    }

    // 数组容量检查，不够时则进行扩容
    private void ensureCapacityInternal(int minCapacity) {
        // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
    // 数组容量检查，不够时则进行扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 确保指定的最小容量 > 数组缓冲区当前的长度 
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    //扩容，保证ArrayList至少能存储minCapacity个元素
    private void grow(int minCapacity) {
        
        // 获取当前数组的容量
        int oldCapacity = elementData.length;
        // 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一半。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容后的容量还是小于想要的最小容量
        if (newCapacity - minCapacity < 0)
        //将扩容后的容量再次扩容为想要的最小容量
        newCapacity = minCapacity;
        //如果扩容后的容量大于临界值，则进行大容量分配
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //元素内容复制
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    // 进行大容量分配
    private static int hugeCapacity(int minCapacity) {
        //如果minCapacity<0，抛出异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //如果想要的容量大于MAX_ARRAY_SIZE，则分配Integer.MAX_VALUE，否则分配MAX_ARRAY_SIZE
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    

综合上述过程：add()方法在添加元素时首先会检查容量空间是否足够，如果不够则进行扩容，扩容之后将元素添加至集合中。

7 get()方法

get()方法相对简单，不再赘述。

    /**
     * 返回list中索引为index的元素
     *
     * @param  index 需要返回的元素的索引
     * @return list中索引为index的元素
     * @throws IndexOutOfBoundsException 如果索引超出size
     */
    public E get(int index) {
        // 检查是否越界
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //根据索引返回元素
        return (E) elementData[index];
    }

8 remove()方法

remove()方法的详细说明已加在源码注释中。

    /**
     * 删除list中位置为指定索引index的元素
     * 索引之后的元素向左移一位
     *
     * @param index 被删除元素的索引
     * @return 被删除的元素
     * @throws IndexOutOfBoundsException 如果参数指定索引index>=size，抛出一个越界异常
     */
    public E remove(int index) {
        //检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //结构性修改次数+1
        modCount++;
        //记录索引为inde处的元素
        E oldValue = elementData(index);

        // 删除指定元素后，需要左移的元素个数
        int numMoved = size - index - 1;
        //如果有需要左移的元素，就移动（移动后，该删除的元素就已经被覆盖了）
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
        elementData[--size] = null; // clear to let GC do its work

        //返回被删除的元素
        return oldValue;
    }

9 set()方法

    /**
     * 替换指定索引的元素
     *
     * @param 被替换元素的索引
     * @param element 即将替换到指定索引的元素
     * @return 返回被替换的元素
     * @throws IndexOutOfBoundsException 如果参数指定索引index>=size，抛出一个越界异常
     */
    public E set(int index, E element) {
        //检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
        rangeCheck(index);

        //记录被替换的元素
        E oldValue = elementData(index);
        //替换元素
        elementData[index] = element;
        //返回被替换的元素
        return oldValue;
    }

10 小结

本篇文章主要分析了ArrayList中数据的增删改查的方法，重点在于ArrarList的扩容方法。ArrayList实现相对简单，代码也不复杂，但是其中实现的各类方法需要牢记，有助于之后分析其他容器时作为比较。