自己动手写写：ArrayList源码浅析

了解你所使用的东西，最直接有效的方式莫过于源码切入的方式！

 

最近会写一个源码分析的系列文章！这篇文章先从最常用的例子ArrayList下手剖析！

 

一. ArrayList

 

下面是ArrayList的类结构

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

 

1. 两个重要的成员变量

 

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private transient Object[] elementData;

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

我们知道ArrayList的内部真实的存储结构是数组，正是此elmentDate; size很明显就是ArrayList的长度（这可不是数组的长度）。

 

2. 三个构造函数

 

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param   initialCapacity   the initial capacity of the list
     * @exception 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];
    }

   initialCapacity是初始化数组长度的参数。

 

 

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

 默认初始化数组的长度为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);
    }

 上面这个构造函数也没啥好说的，使用另外一个Collection初始化，就是将数据c的内容copy到elementData中。

 

3. 几个重要的方法

 

    /**
     * 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)
    {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        
        ensureCapacity(size + 1); // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

这个add方法的作用就是将此element插入到数组下表为index下，如果超出当前size会报错的。

其中ensureCapacity(size + 1); 的作用是什么呢？我们来看一下这个方法的内容！

 

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

 没错，这个方法就是扩充elementData数组的长度所用。新增一条数据后，如果发现当前elementData数组的长度不够时，会扩充elementData数组，扩充后的elementData数组的长度是原elementData的长度*3/2 + 1后的长度。ps:为啥扩充了一半左右，还不清楚。

 

 看得出来，ArrayList的内存就是维护了一个数组，通过不断的新建长度更长的数组并复制数据来完成的！这也就决定了ArrayList的插入速度在需要扩容的时候会比较慢，但是索引查询的数组是相当的快！ps:扩建数组的代价相对而言还是较大的，对于能够预估容量的情况下可以直接初始化一定容量的数组。

 

    /**
     * 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 (E)elementData[index];
    }

   根据索引获得对象，没啥好说的！其中RangeCheck(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 = (E)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后面的所有对象向前移动一位，并将elementData[--size] = null; // Let gc do its work

其中modCount参数是父类AbstractList中定义的，详情如下：

 

/**                                                                       
 * The number of times this list has been <i>structurally modified</i>.   
 * Structural modifications are those that change the size of the         
 * list, or otherwise perturb it in such a fashion that iterations in     
 * progress may yield incorrect results.                                  
 *                                                                        
 * <p>This field is used by the iterator and list iterator implementation 
 * returned by the {@code iterator} and {@code listIterator} methods.     
 * If the value of this field changes unexpectedly, the iterator (or list 
 * iterator) will throw a {@code ConcurrentModificationException} in      
 * response to the {@code next}, {@code remove}, {@code previous},        
 * {@code set} or {@code add} operations.  This provides                  
 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in   
 * the face of concurrent modification during iteration.                  
 *                                                                        
 * <p><b>Use of this field by subclasses is optional.</b> If a subclass   
 * wishes to provide fail-fast iterators (and list iterators), then it    
 * merely has to increment this field in its {@code add(int, E)} and      
 * {@code remove(int)} methods (and any other methods that it overrides   
 * that result in structural modifications to the list).  A single call to
 * {@code add(int, E)} or {@code remove(int)} must add no more than       
 * one to this field, or the iterators (and list iterators) will throw    
 * bogus {@code ConcurrentModificationExceptions}.  If an implementation  
 * does not wish to provide fail-fast iterators, this field may be        
 * ignored.                                                               
 */                                                                       
protected transient int modCount = 0;                                     

 这里注释也说明的很清楚了，modCount的含义就modify count（list的修改次数），这是一个可选的参数，子类完全可以不操作这个成员变量，但是如果你想提供一个 fail-fast iterators，你就需要在每次修改时modCount++。

 

 

    /**
     * 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;
    }

查找容器内是否包含o对象并返回第一次找到的索引。这个也没啥好的办法呀，直接遍历一遍呗！ 

 

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

 返回数组形式的数据，也没啥好的。

 

/**
     * Returns an array containing all of the elements in this list in proper
     * sequence (from first to last element); the runtime type of the returned
     * array is that of the specified array.  If the list fits in the
     * specified array, it is returned therein.  Otherwise, a new array is
     * allocated with the runtime type of the specified array and the size of
     * this list.
     *
     * <p>If the list fits in the specified array with room to spare
     * (i.e., the array has more elements than the list), the element in
     * the array immediately following the end of the collection is set to
     * <tt>null</tt>.  (This is useful in determining the length of the
     * list <i>only</i> if the caller knows that the list does not contain
     * any null elements.)
     *
     * @param a the array into which the elements of the list are to
     *          be stored, if it is big enough; otherwise, a new array of the
     *          same runtime type is allocated for this purpose.
     * @return an array containing the elements of the list
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this list
     * @throws NullPointerException if the specified array is null
     */
    public <T> T[] toArray(T[] a)
    {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[])Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

 这个方法也是返回数组形式的数据，如果a.length < size 则按照a的运行时类型新建一个的数组，并把elementData的数组全部copy进去返回此数组，否则将elementData的数组copy进数组里面，并且将其他索引处置null.

 

当然还有一些其他的方法，这里就不再分析了，看看都懂得！下个章节介绍LinkedList的内容！

 

ps:以上是基于1.6版本的类库源码分析!

评论

6 楼 chenjingbo 2011-08-04  

    我也说说我知道的吧
    我们普通说的JDK其实是包括三个部分的,1 Java虚拟机,2 Java API类库,3Java程序设计语言.我们一般会将Java API类库中的J2SE API子集 + Java虚拟机 为JRE. 我想你们这边说的应该就是JavaAPI类库了.
    Sun HotSpot VM 是它是Sun JDK和OpenJDK中所带的虚拟机，也是目前使用范围最广的Java虚拟机。这个只是Java虚拟机的一个实现而已,除了hot spot以外其他还有BEA JRockit / IBM J9 VM , Apache Harmony / Google Android Dalvik VM 等等.都是虚拟机的实现.他们都是按照虚拟机规范来实现的.
    需要注意的是,考虑到让其他的语言实现到Java虚拟机上运行的可能,所以在发布Java规范的时候特意分成两个部分发,第一个是Java虚拟机规范,第二个是Java语言规范.正因为这两个的分离,才让后面好多新型的语言被创造出来并运行在Java虚拟机上.比如 Groovy,JRuby等等.
    哈哈,随便说说,欢迎指正..

5 楼 magicgrass 2011-08-03  

boy00fly 写道

jilen 写道

Hotspot一般指虚拟机。类库通常不这么叫得吧？？？？还是我又二了

嗯，指正得对，谢谢，我的措词上欠妥当 。
那应该叫什么合适呢？ 1.6版本的类库？

hotspot是实现虚拟机的技术之一，sun的jvm后期版本采用hotspot。

引用

那应该叫什么合适呢？ 1.6版本的类库？

说成java 新版本库中的一个类，，，如有不妥请指正

4 楼 boy00fly 2011-08-03  

左手边 写道

这不是源码么

  这是源码啊，没说不是啊！

3 楼 boy00fly 2011-08-03  

jilen 写道

Hotspot一般指虚拟机。类库通常不这么叫得吧？？？？还是我又二了

嗯，指正得对，谢谢，我的措词上欠妥当 。
那应该叫什么合适呢？ 1.6版本的类库？

2 楼 左手边 2011-08-03  

这不是源码么

1 楼 jilen 2011-08-02  

Hotspot一般指虚拟机。类库通常不这么叫得吧？？？？还是我又二了