ArrayList实现原理以及其在jdk1.6和jdk1.7的实现区别

ArrayList基本上是我们在java编程中用得最多的集合类了，是一个动态的数组，在我们用ArrayList的时候发现其非常方面，功能也很强大，但是其这强大的功能是底层是怎么实现的呢？因为现在jdk已经从1.6到1.7，再到现在的1.8版本了，ArrayList在jdk版本升高的同时，会有什么异同呢？带着这些疑问，去探讨ArrayList的源码。

 

首先，ArrayList的继承和实现了的类和接口

 

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

 

 

可以看到ArrayList<E>是支持泛型的，所以ArrayList可以构造成任何类型的动态数组。

同时它也继承了AbstractList抽象类，抽象类实现了很多默认的方法，但是还有一些方法还是抽象方法。

实现了通用的List列表接口，这里面定义了List列表的基础方法。

同时实现了RandomAccess，Cloneable，Serializable接口，这三个接口都是空接口，里面没有任何方法声明。

 

RandomAccess是一个标记接口，其主要就是提供给List接口用的，用来表明其支持快速随机访问。因为这个接口是没有任何实现的，实现了这个接口的类，就表明这个类支持快速访问，就相当于实现了Serializable就等于支持序列化和反序列化，这是个标准。

 

Cloneable接口，表明这个是可以进行浅拷贝的，是可以调用Object.clone()返回该对象的浅拷贝。

什么是浅拷贝呢？

举个例子：

假设x是一个飞空对象，应该有：

(x.clone()!=x )==true,也就是说它们不是同一个对象。

(x.clone().getClass()==x.getClass())==true,也就是它们是同一个类型的class，

(x.equals(x.clone()))==true,也就是，逻辑上和内容上，它们应该是相同的。

实现了Cloneable的类应该要满足上面的几个情况。

 

Serializable接口是我们经常遇到的接口，表明该类支持序列化和反序列化操作。

 

所以ArrayList继承这三个没有任何方法定义的接口只是为了表明这个类是支持随机快速访问的，可以支持浅拷贝的，可以被序列化和反序列化的。

 

都说ArrayList是动态数组，那么它里面存储数据的数据结构是什么呢？

 

private transient Object[] elementData;

 

 

上面这个对象数组就是其存储元素的数据结构，前面有一个java关键字transient，这个关键字是去序列化的意思，即，在这个类序列化后保存到磁盘或者输出到输出流的时候，这个对象数组是不被保存或者输出的。

 

这里又有疑问了，这个数组不是存储我们保存的数据的吗？为什么要去序列化呢？那么如果去掉序列化之后，我们保存的元素从哪里来呢？

 

这就跟这个ArrayList的特性有关，我们知道ArrayList的容量，也就是这个数组的容量，一般都是预留一些容量，等到容量不够时再拓展，那么就会出现容量还有冗余的情况，如果这时候进行序列化，整个数组都会被序列化，连后面没有意义空元素的也被序列化。这些是不应该被存储的。所以java的设计者，就为这个类提供了一个writeObject方法，在实现了Serializable接口的类，如果这个类提供了writeObject方法，那么在进行序列化的时候就会通过writeObject方法进行序列化，所以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 array length
        s.writeInt(elementData.length);

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

    }

 

 

如果想了解更多有关java序列化的知识，请擢：http://zhh9106.iteye.com/blog/2152397

 

下面，看看ArrayList的构造方法：

 

/**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this(10);
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

 

 

ArrayList提供了三个构造方法，第一个是由调用者传入指定List的大小来创建elementData数组。第二个是默认的构造方法，默认数组容量是10。第三个是根据传入的一个集合，将集合转化成数组，然后赋给elementData。

 

再看ArrayList里面我们常用的方法，逐个分析;

isEmpty()

 

/**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
    }

 

 

判断size是否为0,，为0则返回true。

 

indexOf(Object o)

 

/**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

 

根据传入的Object，返回其在数组中的下班位置，若不存在则返回-1

 

contains(Object o)

 

/**
     * Returns <tt>true</tt> if this list contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this list contains
     * at least one element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return <tt>true</tt> if this list contains the specified element
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

 

调用indexOf()方法返回的位置与0比较，若大于等于0，则证明这个元素是存在，若不存在indeOf()会返回-1，则返回true。

 

lastIndexOf()

 

/**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

 

根据方法名，可以知道，其返回指定元素最后一次出现的数组下标，若找不到此元素，则返回-1

 

clone()

 

/**
     * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this <tt>ArrayList</tt> instance
     */
    public Object clone() {
        try {
            @SuppressWarnings("unchecked")
                ArrayList<E> v = (ArrayList<E>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

 

上面提到，ArrayList实现了Cloneable接口，支持返回浅拷贝，这里是重写了Object类的clone方法，返回的是一个副本（对象实例不同，内容相同，因为对象实例都不同，所以modCount也设为0）

 

toArray()

 

/**
     * Returns an array containing all of the elements in this list
     * in proper sequence (from first to last element).
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this list in
     *         proper sequence
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

 将ArrayList以数组形式返回。

 

 

get(int index)

 

 /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

 

代码很简单，首先调用rangeCheck()检查index是否越界，再返回指定位置元素。

 

set(int index,E element)

 

/**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

 检查index是否越界，将数组下标为index的内容更新为element，并返回旧的元素值。

 

 

remove(int index)

 

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    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; // Let gc do its work

        return oldValue;
    } 

 

根据传入的index，然后利用System.arraycopy()方法将index后面的元素从index位置开始进行覆盖，这里需要注意的是，index+1到size位置的元素，覆盖掉index到size位置的元素，所以最后的两个元素肯定相同，即重复了，所以最后一步会有elementData[--size] = null;将最后一个元素置为null。最后返回删除元素的值。

 

remove(Object o)与fastRemove(int index),这两个方法时一起使用的

 

/**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If the list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    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 remove method that skips bounds checking and does not
     * return the value removed.
     */
    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; // Let gc do its work
    }

 

 

这个是根据传入的元素来移除，首先找到要删除元素的位置，然后调用fastRemove()方法进行移除，这里大家会有疑问，既然找到index，为什么不用上门那个移除方法处理呢？非要写个fastRemove()，看代码就知道，fastRemove跳过了index越界处理，并且不用返回要删除的元素值。

 

clear()

 

/**
     * Removes all of the elements from this list.  The list will
     * be empty after this call returns.
     */
    public void clear() {
        modCount++;

        // Let gc do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

 clear方法并不是把整个数组都删除，因为毕竟已经申请了内存，这样删了，很可惜，因为可能以后还用得着，这就免去了再次去申请内存的麻烦。这里的clear只是把每个元素的都置为null，并把size设为0.

 

add(E element)

 /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

 首先要检查一下是否超出了容量，如果超出了，进行扩容，然后往原数组最后一个元素后面插入指定元素。

 

add(int index,E element)

/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    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++;
    }

 根据指定位置，插入指定元素，先进行越界检查，再进行容量检查，然后将从index开始的元素到最后的元素，从index+1位置开始往后复制，然后将指定元素插入到index位置，然后将容量size增加1

 

addAll(Collection<? extends E> c)

/**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    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;
    }

 在数组后面插入一个指定集合里面的所有元素，首先将集合转化为数组，然后进行容量检查，将目标数组元素拷贝到elementData上。这里有一点需要注意，如果传入的集合为null，那么结果会返回FALSE。

 

addAll(int index, Collection<? extends E> c)

 /**
     * Inserts all of the elements in the specified collection into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order that they are returned by the
     * specified collection's iterator.
     *
     * @param index index at which to insert the first element from the
     *              specified collection
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified collection is null
     */
    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;
    }

 将集合元素根据指定的位置开始插入，这个方法跟上面方法的区别是，要插入到指定位置，那么从源码可以看到，首先其会从原数组index开始到最后的元素，从index+numNew开始往后复制，目的是空出numNew个位置来存储目标集合的元素。然后再讲目标数组从index位置开始依次插入到原数组。

 

从上面的插入的几个方法会发现一个共同点，就是每次插入前都会进行容量检查，检查是否超出了容量，如果超出了，则进行扩容。那看看，它是如果进行扩容的？而这里也是jdk1.6和jdk1.7的实现区别

ensureCapacityInternal(int minCapacity)

private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

 根据传入的最小需要容量minCapacity来和数组的容量长度对比，若minCapactity大于或等于数组容量，则需要进行扩容，调用grow()

 

grow()

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
    }

 首先得到数组的旧容量，然后进行oldCapacity + (oldCapacity >> 1)，将oldCapacity 右移一位，其效果相当于oldCapacity /2，我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，接着，再检查新容量是否超出了ArrayList所定义的最大容量，若超出了，则调用hugeCapacity()来比较minCapacity和MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为ArrayList定义的最大容量，否则，新容量大小则为minCapacity。还有一点需要注意的是，容量拓展，是创建一个新的数组，然后将旧数组上的数组copy到新数组，这是一个很大的消耗，所以在我们使用ArrayList时，最好能预计数据的大小，在第一次创建时就申请够内存。

 

下面附上hugeCapacity()代码：

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

 

以上就是ArrayList常用的且比较重要的方法源码实现原理，上面我们提到jdk1.6和jdk1.7在ArrayList上的实现区别就在于数组的容量扩展，以上代码都是jdk1.7的，下面来看看jdk1.6的容量扩展的实现：

/**
 2      * Increases the capacity of this <tt>ArrayList</tt> instance, if
 3      * necessary, to ensure that it can hold at least the number of elements
 4      * specified by the minimum capacity argument.
 5      *
 6      * @param   minCapacity   the desired minimum capacity
 7      */
 8     public void ensureCapacity(int minCapacity) {
 9     modCount++;
10     int oldCapacity = elementData.length;
11     if (minCapacity > oldCapacity) {
12         Object oldData[] = elementData;
13         int newCapacity = (oldCapacity * 3)/2 + 1;
14             if (newCapacity < minCapacity)
15         newCapacity = minCapacity;
16             // minCapacity is usually close to size, so this is a win:
17             elementData = Arrays.copyOf(elementData, newCapacity);
18     }
19     }

从代码上，我们可以看出区别：

第一：在容量进行扩展的时候，其实例如整除运算将容量扩展为原来的1.5倍加1，而jdk1.7是利用位运算，从效率上，jdk1.7就要快于jdk1.6。

第二：在算出newCapacity时，其没有和ArrayList所定义的MAX_ARRAY_SIZE作比较，为什么没有进行比较呢，原因是jdk1.6没有定义这个MAX_ARRAY_SIZE最大容量，也就是说，其没有最大容量限制的，但是jdk1.7做了一个改进，进行了容量限制。

 

这个容量扩展很经常在面试的时候会问到，有些面试官会问的很细，就问你这个容量扩展在jdk1.6和jdk1.7上的实现区别，所以这里就稍微提了一下，我暂时只发现这两个不同，如果大家还知道其他方面的区别，请分享分享...

 

大概就这么多了。

 

本博客有参考：http://blog.csdn.net/jzhf2012/article/details/8540410

                         http://zhangshixi.iteye.com/blog/674856