Java集合源码学习（2）ArrayList

ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于 C语言 中的动态申请内存，动态增长内存。

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

ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。

每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。

注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

ArrayList继承AbstractList，实现了List、 RandomAccess、Cloneable、Serializable接口， 为ArrayList内部是用一个数组存储元素值，相当于一个大小可变的数组，也就是动态数组。 由于ArrayList底层是数组实现的，所以可以随机访问。

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

（1）继承和实现

继承了AbstractList，实现了List：ArrayList是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。

实现RandmoAccess接口：即提供了随机访问功能。RandmoAccess是 java 中用来被List实现，为List提供快速访问功能的在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。

实现了Cloneable接口：即覆盖了函数clone()，能被克隆。

实现java.io.Serializable接口：这意味着ArrayList支持序列化，能通过序列化去传输。

（2）线程安全

ArrayList不是线程安全的。建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。同样，HashMap也是线程不安全的，如果需要并发访问应该使用Hashtable(遗留类)或ConcurrentHashMap。

private static final int DEFAULT_CAPACITY = 10;//默认容量是10
复制代码

私有属性：

/** 
  * 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;
复制代码

elementData存储ArrayList内的元素，size表示它包含的元素的数量。

有个关键字需要解释：transient。

Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。

经常在实现了 Serializable接口的类中能看见transient关键字。这个关键字并不常见。 transient关键字的作用是：阻止实例中那些用此关键字声明的变量持久化；当对象被反序列化时（从源文件读取字节序列进行重构），这样的实例变量值不会被持久化和恢复。当某些变量不想被序列化，同是又不适合使用static关键字声明，那么此时就需要用transient关键字来声明该变量。

除了以上两个成员变量，我们还需要掌握一个变量，它是

protected transient int modCount = 0;
复制代码

这个变量主要作用是防止在进行一些操作时，改变了ArrayList的大小，那将使得结果不可预测。

构造函数：

/**无参构造：
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**有参构造
 * 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) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**参数为集合的有参构造
 * 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();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
复制代码

常用的方法

boolean add(E e) 
将指定的元素添加到此列表的尾部。

void add(int index, E element) 
将指定的元素插入此列表中的指定位置

boolean addAll(Collection<? extends E> c) 
按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。 

boolean addAll(int index, Collection<? extends E> c) 
从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。 

void clear() 
移除此列表中的所有元素。 

Object clone() 
返回此 ArrayList 实例的浅表副本。 

boolean contains(Object o) 
如果此列表中包含指定的元素，则返回 true。 

void ensureCapacity(int minCapacity) 
如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。 

E get(int index) 
返回此列表中指定位置上的元素。 

int indexOf(Object o) 
返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。 

boolean isEmpty() 
如果此列表中没有元素，则返回 true 

int lastIndexOf(Object o) 
返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。 

E remove(int index) 
移除此列表中指定位置上的元素。 

boolean remove(Object o) 
移除此列表中首次出现的指定元素（如果存在）。 

protected void removeRange(int fromIndex, int toIndex) 
移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。 

E set(int index, E element) 
用指定的元素替代此列表中指定位置上的元素。 

int size() 
返回此列表中的元素数。 

Object[] toArray() 
按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。

void trimToSize() 
将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量。
复制代码

遍历方式：

ArrayList支持3种遍历方式

1.通过迭代器遍历。即通过Iterator去遍历

2.随机访问，通过索引值去遍历，ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素

3.for循环遍历

遍历ArrayList时，使用随机访问(即通过索引序号访问)效率最高，而使用迭代器的效率相对较低。