一、ArrayList简介
ArrayList顶部有一段很长的注释,大概的介绍了ArrayList。
1.1 原文
/** * Resizable-array implementation of the <tt>List</tt> interface. Implements * all optional list operations, and permits all elements, including * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface, * 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 * <tt>Vector</tt>, except that it is unsynchronized.) * * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>, * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>, * 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 the <tt>LinkedList</tt> implementation. * * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. 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. * * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance * before adding a large number of elements using the <tt>ensureCapacity</tt> * operation. This may reduce the amount of incremental reallocation. * * <p><strong>Note that this implementation is not synchronized.</strong> * If multiple threads access an <tt>ArrayList</tt> instance concurrently, * and at least one of the threads modifies the list structurally, it * <i>must</i> be 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:<pre> * List list = Collections.synchronizedList(new ArrayList(...));</pre> * * <p><a name="fail-fast"> * The iterators returned by this class's {@link #iterator() iterator} and * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a> * 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. * * <p>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: <i>the fail-fast behavior of iterators * should be used only to detect bugs.</i> * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @author Josh Bloch * @author Neal Gafter * @see Collection * @see List * @see LinkedList * @see Vector * @since 1.2 */ public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ... }
1.2 翻译
List接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括null在内的所有元素。除了实现List接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于Vector类,除了此类是不同步的。)
size、isEmpty、get、set、iterator和listIterator操作都以固定时间运行。add操作以分摊的固定时间运行,也就是说,添加n个元素需要O(n)时间。其他所有操作都以线性时间运行(大体上讲)。与用于LinkedList实现的常数因子相比,此实现的常数因子较低。
每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。
在添加大量元素前,应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量。这可以减少递增式再分配的数量。
注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用Collections.synchronizedList方法将该列表“包装”起来。这最好在创建时完成,以防止意外对列表进行不同步的访问:
List list = Collections.synchronizedList(new ArrayList(…));
此类的iterator和listIterator方法返回的迭代器是快速失败的:在创建迭代器之后,除非通过迭代器自身的remove或add方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法:迭代器的快速失败行为应该仅用于检测bug。
此类是Java Collections Framework的成员。
1.3 一语中的
底层:ArrayList是List接口的大小可变数组的实现。
是否允许null:ArrayList允许null元素。
时间复杂度:size、isEmpty、get、set、iterator和listIterator方法都以固定时间运行,时间复杂度为O(1)。add和remove方法需要O(n)时间。与用于LinkedList实现的常数因子相比,此实现的常数因子较低。
容量:ArrayList的容量可以自动增长。
是否同步:ArrayList不是同步的。
迭代器:ArrayList的iterator和listIterator方法返回的迭代器是 fail-fast 的。
如果小伙伴们不了解"fail-fast"机制,可以参考如下文章:
深入浅出fail-fast机制
1.4 线程安全性
对ArrayList进行添加元素的操作的时候是分两个步骤进行的,即第一步先在object[size]的位置上存放需要添加的元素;第二步将size的值增加1。由于这个过程在多线程的环境下是不能保证具有原子性的,因此ArrayList在多线程的环境下是线程不安全的。
具体举例说明:在单线程运行的情况下,如果Size = 0,添加一个元素后,此元素在位置 0,而且Size=1;而如果是在多线程情况下,比如有两个线程,线程 A 先将元素存放在位置0。但是此时 CPU 调度线程A暂停,线程 B 得到运行的机会。线程B也向此ArrayList 添加元素,因为此时 Size 仍然等于 0 (注意哦,我们假设的是添加一个元素是要两个步骤哦,而线程A仅仅完成了步骤1),所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行,都增 加 Size 的值。 那好,现在我们来看看 ArrayList 的情况,元素实际上只有一个,存放在位置 0,而Size却等于 2。这就是“线程不安全”了。
如果非要在多线程的环境下使用ArrayList,就需要保证它的线程安全性,通常有两种解决办法:
第一,使用synchronized关键字;
第二,可以用Collections类中的静态方法synchronizedList();对ArrayList进行调用即可。
第三,也可以使用concurrent并发包下的CopyOnWriteArrayList类。
1.5 优劣分析
优点
ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快。
ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已。
根据下标遍历元素,效率高。
根据下标访问元素,效率高。
可以自动扩容,默认为每次扩容为原来的1.5倍。
缺点
插入和删除元素的效率不高。
根据元素下标查找元素需要遍历整个元素数组,效率不高。
线程不安全。
二、定义
我们先来看看ArrayList的定义:
public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,java.io.Serializable
从中我们可以了解到:
ArrayList:说明ArrayList支持泛型。
extends AbstractList :继承了AbstractList。AbstractList提供List接口的骨干实现,以最大限度地减少“随机访问”数据存储(如ArrayList)实现Llist所需的工作。
implements List:实现了List。实现了所有可选列表操作。
implements RandomAccess:表明ArrayList支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。
implements Cloneable:表明其可以调用clone()方法来返回实例的field-for-field拷贝。
implements java.io.Serializable:表明该类具有序列化功能。
为什么要先继承AbstractList,而让AbstractList先实现List?而不是让ArrayList直接实现List?
这里是有一个思想,接口中全都是抽象的方法,而抽象类中可以有抽象方法,还可以有具体的实现方法,正是利用了这一点,让AbstractList是实现接口中一些通用的方法,而具体的类, 如ArrayList就继承这个AbstractList类,拿到一些通用的方法,然后自己在实现一些自己特有的方法,这样一来,让代码更简洁,就继承结构最底层的类中通用的方法都抽取出来,先一起实现了,减少重复代码。所以一般看到一个类上面还有一个抽象类,应该就是这个作用。
ArrayList的父类AbstractList也实现了List接口,那为什么子类ArrayList还是去实现一遍呢?
collection 的作者Josh说他写这代码的时候觉得这个会有用处,但是其实并没什么用,但因为没什么影响,就一直留到了现在。
ArrayList的类结构图:
如何查看类的完整结构图可以参考如下文章:
三、数据结构
如图所示,ArrayList底层通过数组实现。
一般的时候,我们只需要知道ArrayList的实际大小,但是作为一个优秀的程序员,知道ArrayList数组的容量大小非常重要,如果你想知道如何获取ArrayList的容量大小,可以参考如下文章:
Java如何获取ArrayList的容量(elemenData)大小?
四、域的解读
/** * 初始化默认容量。 */ private static final int DEFAULT_CAPACITY = 10; /** * 指定该ArrayList容量为0时,返回该空数组。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 当调用无参构造方法,返回的是该数组。刚创建一个ArrayList 时,其内数据量为0。 * 它与EMPTY_ELEMENTDATA的区别就是:该数组是默认返回的,而后者是在用户指定容量为0时返回。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 保存添加到ArrayList中的元素。 * ArrayList的容量就是该数组的长度。 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。 * 被标记为transient,在对象被序列化的时候不会被序列化。 */ transient Object[] elementData; // non-private to simplify nested class access /** * ArrayList的实际大小(数组包含的元素个数)。 * @serial */ private int size;
思考:elementData被标记为transient,那么它的序列化和反序列化是如何实现的呢?
被标记为transient的属性在对象被序列化的时候不会被保存。
ArrayList自定义了它的序列化和反序列化方式。详情请查看writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。