源码翻阅之ArrayList

源码阅读之ArrayList
常用方法
1， 其实有两个ArrayList。一个是java.util包下面的。一个java.utils.Collections这个工具类内部类。后者其实只是Collections一系列方法的返回对象.


2，ArrayList继承的接口有List，RandomAccess和Conable和serializable 。换句话说。其没有其他的集合语义。

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

3，成员变量只有elementData和size两个成员变量。觉得还是简单的。这也就意味着，elementData是全部存储对象的。没有任何的保存不再的东西的可能性.，也可以看出，ArrayList采用数组的方式存放对象。

 /**     * ArrayList底层维护的Object数组     */    private transient Object[] elementData;    /**     * 数组的长度     *     * @serial     */    private int size;

4，构造函数分两类。
一类是无参和(int), 其实就是一个初始化elementData的长度。无参的默认长度为10
另一位是（Collection）: 用了Collection.toArray进行转换。

//无参构造方法，会直接去调用有参构造方法 public ArrayList() {this(10);    }

//有参构造方法 public ArrayList(int initialCapacity) {super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);this.elementData = new Object[initialCapacity];    }

//集合构造方法  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);    }

5，trimToSize：内存紧张的时候会用到。

 public void trimToSize() {modCount++;int oldCapacity = elementData.length;if (size < oldCapacity) {            elementData = Arrays.copyOf(elementData, size);}    }

6.ensureCapacity：扩充数组长度。扩展长度是原长度old×1.5+1。

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

7，indexOf和lastIndexOf。重写了一下，直接访问数组。觉得Iterator其实性能上不好。只是语义上与Collection相对.indexOf和lastIndexOf是ArrayList中用于获取对象所在位置的方法，indexOf为从前往后找，lastIndexOf为从后往前找。

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

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

8， 重写了clone方法，其实就是数组copy加上modCount重置。

  public Object clone() {try {    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();}    }

9，toArray（T[] a）觉得实现有点怪。具体规则为。
如果a的size小于List的size，那么就返回一个新的数组。不影响a。
反之，a的size大于List。那么就是把list全部Copy到a，然后在List的size的位置，把其设为null。后面的数据不变，然后返回a。换句话说影响了a。
所以觉得，还是怎么说呢，创建一个新的a，空的a丢进去。比较保险。因为都是用了复制。就是多了一个创建的性能消耗。toArray();直接调用Arrays的拷贝方法。

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;    } public Object[] toArray() {        return Arrays.copyOf(elementData, size);    }

10，set方法的都有一个rangcheck方法。操作的是就是把删除数组索引位置的值，然后把后面的数据前移动。

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

11.add(element);方法，首先检查扩充容量，然后把e的值付给当前数据组的size位置上，size+1返回。

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

12.add(Index,element)方法，就是会使用System中copy数组的方法。
addAll(collection)只是copy了一次数组，addALL（index,collection）则copy了两次。

 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++;    } public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();        int numNew = a.length;ensureCapacity(size + numNew);  // Increments modCount        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;return numNew != 0;    }  public boolean addAll(int index, Collection<? extends E> c) {if (index > size || index < 0)    throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);Object[] a = c.toArray();int numNew = a.length;ensureCapacity(size + numNew);  // Increments modCountint 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;    }

13，remove方法，是用equal进行判断的。remove第一出线的。调用了一个fastRemove的内部方法，其省去了边界检查。其实也还是很System copy。remove（int）的实现比remove(e)多了一个数组范围检测，但少了数组元素的查找，因此性能会更好

 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 workreturn oldValue;    } 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 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    }

14.get(index)方法，在arrayList维护的数组中取出索引为index的值，前提是要保证index的值没有超过数组的最大长度。

 public E get(int index) {RangeCheck(index);return (E) elementData[index];    }

15.contains（o）判断数组中是否存在某元素。其做法为遍历整个ArrayList中已有元素，如o为null,则直接判断已有元素是否为null，如为null返回true，如果o不为null,则直接通过判断o.equals和元素是否相等，如相等返回true.

 public boolean contains(Object o) {return indexOf(o) >= 0;    }

15.size();直接返回ArrayList中维护的size成员变量。

 public int size() {return size;    }

16.isEmpty()；判断ArrayList中维护的size的值是否为0

public boolean isEmpty() {return size == 0;    }

注意要点：
1.ArrayList基于数组方式实现，无限制容量。添加元素时，就是想ArrayList维护的数组中添加元素。
2.ArrayList在执行插入时可能扩充，在删除元素时候，并不会减小数组的容量（如希望减小数组的容量可以调用ArrayLust的trimToSize（）方法，在查找元素要遍历数组时，对于非null元素采用equals的方式寻找）
3.ArrayList是非线程安全的
4.ArrayList删除元素操作时，需要将数组元素向前移动，代价比较高。
5.集合当中放置的是对象的引用，无法放置原生数据类型。我们需要使用原生数据类型的包装类。取出的时候，要进行强制类型转换将其转换成真正的类型（放置进去的类型）.

查看更多 下一篇