ArrayList源码学习

Resizable-array implementation of theListinterface. Implements * all optional list operations, and permits all elements, including *null. In addition to implementing theListinterface, * this class provides methods to manipulate the size of the array that is * used internally to store the list. (This class is roughly equivalent to *Vector, except that it is unsynchronized.) * *

可变数组实现了list接口。实现了所有list的运算操作，且允许所有类型元素，包括null。除了实现list接口之外，类提供了调整数组大小方法，用来存储list。该类与Vector基本相同，除了非线程安全。

Thesize,isEmpty,get,set, *iterator, andlistIteratoroperations run in constant * time.  Theaddoperation runs inamortized constant time, * that is, adding n elements requires O(n) time.  All of the other operations * run in linear time (roughly speaking).  The constant factor is low compared * to that for theLinkedListimplementation. * *

size  isEmpty get  set  iterator  listIteratoroperations 算法时间为常量。addoperation运行时间为一个分段常量时间，即添加N个元素需要O（n）时间，所有的其他运算方法是线性时间。常量因素要比linkedList同样方法花费的时间段。

EachArrayListinstance has acapacity.  The capacity is * the size of the array used to store the elements in the list.  It is always * at least as large as the list size.  As elements are added to an ArrayList, * its capacity grows automatically.  The details of the growth policy are not * specified beyond the fact that adding an element has constant amortized * time cost. * *

每个ArrayList对象必设定容量，容量就是存储在list中的数组大小。通常最大为list的最大。当元素添加到ArrayList，他的容量会自增长。

An application can increase the capacity of anArrayListinstance * before adding a large number of elements using theensureCapacity* operation.  This may reduce the amount of incremental reallocation. * *

Note that this implementation is not synchronized.* If multiple threads access anArrayListinstance concurrently, * and at least one of the threads modifies the list structurally, it *mustbe synchronized externally.  (A structural modification is * any operation that adds or deletes one or more elements, or explicitly * resizes the backing array; merely setting the value of an element is not * a structural modification.)  This is typically accomplished by * synchronizing on some object that naturally encapsulates the list. * * If no such object exists, the list should be "wrapped" using the * {@link Collections#synchronizedList Collections.synchronizedList} * method.  This is best done at creation time, to prevent accidental * unsynchronized access to the list:

注意，该实现类是非线程安全的。如果多线程同时访问ArrayList对象，且至少一个线程修改了list的结构，他必须在外部同步。

如果没有该类型存在，列表应该使用Collection的Collections.synchronizedList方法来包装该list。最好在创建时使用，以防止非线程安全访问。如题实例如下：

*  List list = Collections.synchronizedList(new ArrayList(...));

* *

* The iterators returned by this class's {@link #iterator() iterator} and * {@link #listIterator(int) listIterator} methods arefail-fast: * if the list is structurally modified at any time after the iterator is * created, in any way except through the iterator's own * {@link ListIterator#remove() remove} or * {@link ListIterator#add(Object) add} methods, the iterator will throw a * {@link ConcurrentModificationException}.  Thus, in the face of * concurrent modification, the iterator fails quickly and cleanly, rather * than risking arbitrary, non-deterministic behavior at an undetermined * time in the future. * *

Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification.  Fail-fast iterators * throw {@code ConcurrentModificationException} on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness:the fail-fast behavior of iterators

* should be used only to detect bugs.* *

This class is a member of the

* * Java Collections Framework. * * @author  Josh Bloch * @author  Neal Gafter * @see    Collection * @see    List * @see    LinkedList * @see    Vector * @since  1.2

默认容量大小  10 private static final int DEFAULT_CAPACITY = 10;

最大容量 ： private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

>> ：带符号右移，一般数值减半，正数，高位补零，负数，高位补一，如4>>1 向右移动一位  ：0100 -->0010 =2 

负数-4>>1 向右移动一位： 1100--->1010 = -2

初始化有多种方式：

1、指定ArrayList的大小，如 new ArrayList(12)

2、不指定大小，如new ArrayList()，默认会初始化一个空的数组。

3、使用Collection初始化， new ArrayList(new Collection());

转换为Object[]  list.toArray()，这个转换过程是线程安全的，list中数据的引用不会被关联到新的数组中，

注意：允许存入数据为null.

多处使用的系统数组复制工具System.arraycopy(srcArr,srcindex,desArr,desindex,length);

意味着：从原数组中的srcindex开始，到srcindex+length -1,复制数组数据到目的数组的，desArr开始，到desArr+length-1;

如果srcArr与desArr相同，则会将复制的数组暂存到TemArray中。

object.retainAll(new Collection());：删除除了collection中包含的数据之外的其他object中的数据。