JAVA之ArrayListt源码解读

ArrayList是基于数组实现的，是一个动态数组，其容量能自动增

public class ArrayList<E>

        extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 

 ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类

 

底层使用Object数组保存元素，可以是字符串基本类型，Map对象，其他对象

 /**

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

 

 

   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() {

       //默认容量是10

this(10);

    }

 

 

/**

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

            //为何不用移位表示，据说移位速度快，

　　　//位运算的汇编指令比乘法的汇编指令少，而每个汇编指令消耗的时间是一样的

          //位运算cpu 直接支持的，效率最高

 

       if (newCapacity < minCapacity)

newCapacity = minCapacity;

            // minCapacity is usually close to size, so this is a win:

            elementData = Arrays.copyOf(elementData, newCapacity);

}

    }

从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。

 

 

  /**

     * 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];

    }

 

 

/**

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

elementData[index] = element;

return oldValue;

    }

 

 

/**

     * 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) {

ensureCapacity(size + 1);  // Increments modCount!!

elementData[size++] = e;

return true;

    }

 

 

/**

     * 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!!

        //从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。

        //arraycopy(被复制的数组, 从第几个元素开始复制, 要复制到的数组, 从第几个元素开始粘贴, 一共需要复制的元素个数)

        //即在数组elementData从index位置开始，复制到index+1位置,共复制size-index个元素

System.arraycopy(elementData, index, elementData, index + 1,

size - index);

elementData[index] = element;

size++;

    }

 

 

 /**

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

        //将原数组最后一个位置置为null,交给GC处理

elementData[--size] = null; // Let gc do its work

 

return oldValue;

    }

 

 

/**

     * 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

    }

 

 /**

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

    }

 

 

 /**

     * Save the state of the <tt>ArrayList</tt> instance to a stream (that

     * is, serialize it).

     *

     * @serialData The length of the array backing the <tt>ArrayList</tt>

     *             instance is emitted (int), followed by all of its elements

     *             (each an <tt>Object</tt>) in the proper order.

     */

    private void writeObject(java.io.ObjectOutputStream s)

        throws java.io.IOException{

       //将ArrayList的“容量，所有的元素值”都写入到输出流中 

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

        }

 

    }

 

    /**

     * 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 {

         //先将ArrayList的“大小”读出，然后将“所有的元素值”读出

// Read in size, and any hidden stuff

s.defaultReadObject();

 

        // Read in array length and allocate array

        int arrayLength = s.readInt();

        Object[] a = elementData = new Object[arrayLength];

 

// Read in all elements in the proper order.

for (int i=0; i<size; i++)

            a[i] = s.readObject();

    }

 

 

 

/**

     * 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) {

       //正向查找，返回ArrayList中元素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;

    }

 

    /**

     * 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) {

    //逆向查找，返回返回ArrayList中元素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;

    }