【转】【Java之JavaSE】研磨Java源码--集合框架之List

ArrayList

内部保存一个数组Object[] elementData，可以定义初始化容量，扩容的策略是：总是按照1.5倍扩大: newCapacity = oldCapacity + (oldCapacity >> 1)。数组的优势是：存储开销小，随机访问效率高，缺点是在数组非末尾插入或删除元素时，都需要移动后面数据。跟入remove和put(int ,object)方法，发现会使用System.arraycopy对被操作元素的后面所有元素进行移动。System.arraycopy是一个本地方法，比用Java实现拷贝要快。Arrays.copyOf对这个方法进行了一些封装。提到ArrayList不妨说一说Java的fail fast特性。在尝试进行一些不安全的操作时，Java会立刻抛出异常，例如尝试访问超过数组下标的元素，或者尝试在使用迭代器时对原集合进行修改。这个特性虽然经常会让程序crash掉，但是能让出错更容易定位问题。个人认为是比c++直接返回一个不可知的元素要好的多的。 ArrayList在涉及index的方法，都会执行rangeCheck()操作，如果index超出范围，则会抛出 IndexOutOfBoundsException。

Iterator

提到List的时候不妨一起说一下Java中的迭代器。迭代器的实现有很多，以ArrayList.Itr为例。迭代器内部保存了一个 cursor，从0开始。next()和previous()方法返回当前迭代对象，并会使迭代器移动(cursor+1或cursor-1)。

ListIterator

ListIterator继承自Iterator，额外实现了add()等方法。Iterator在内部保存了变量 expectedModCount，如果在迭代过程中改变了原集合的值，就会抛异常ConcurrentModifyException。这也是fail fast的一个特性。

Vector

线程安全的ArrayList，对add get等方法都提供了同步。扩容方式是*2。

LinkedList

保存首尾两个指针first和last，除了继承List的一些方法之外，还提供了getFirst，getLast，removeFirst，removeLast等方法。随机访问时，会根据index的值，然后选择是从表头还是表尾开始查找到相应元素。

CopyOnWriteArrayList

这里引用一下http://www.cnblogs.com/promise6522/archive/2012/03/22/2412686.html中对Copy-On-Write的解释： Copy-on-write（以下简称COW）是一种很重要的优化手段。它的核心思想是懒惰处理多个实体的资源请求，在多个实体之间共享某些资源，直到有实体需要对资源进行修改时，才真正为该实体分配私有的资源。 COW技术的一个经典应用在于Linux内核在进程fork时对进程地址空间的处理。由于fork产生的子进程需要一份和父进程内容相同但完全独立的地址空间，一种做法是将父进程的地址空间完全复制一份，另一种做法是将父进程地址空间中的页面标记为”共享的“（引用计数+1），使子进程与父进程共享地址空间，但当有一方需要对内存中某个页面进行修改时，重新分配一个新的页面（拷贝原内容），并使修改进程的虚拟地址重定向到新的页面上。咋一看，Java中的CopyOnWriteArrayList似乎就是这样一个实现：初始化时传入一个数组，在没有写操作时一直读取该数组，知道有写操作时，单独开辟一块空间进行存储。

但是分析源码后发现，其实在进行每一次修改操作时，都会重新复制一份数组。可想而知，这个开销是巨大的。那么，这样做的目的是什么呢？ This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. 就是说，在迭代CopyOnWriteArrayList时，如果修改集合元素，就会复制一份数组，而不会影响迭代内容(迭代使用修改前的 snapshot)。因此，CopyOnWriteArrayList.iterator永远不会抛出 ConcurrentModifyException。如果不想在迭代时锁住所有写操作，就可以使用CopyOnWriteArrayList。

排序

说到List，不得不提到排序的问题。java.util.Arrays.sort()有两种不同的实现： DualPivot Quicksort 和 TimSort。DualPivotQuicksort是Vladimir Iaroslavski2009年提出的一种改进的快速排序算法，它通过优化pivot的选取，达到较高的效率。而TimSort是一种优化过的归并排序算法。除了最坏时间复杂度的区别，这两种算法的最大区别是：快速排序是不稳定的，归并排序是稳定的。所以Arrays.sort在对基本类型的数组进行排序时，使用了DualPivotQuicksort，而对对象进行排序时，使用了TimSort。

实验

最后还是对各个类型的性能做一个测试吧。因为这几种类型差别很大，本次测试并不是为了比较集合的性能，而是为了说明其不同点，所以选了一个比较小的数据，这里测试add(Object)，get(int index)和remove(0)三个操作的性能。程序如下：

    int limit=100000;
    for (int j = 0; j < round; j++) {
    timerAdd.start(j);
    for (int i = 0; i < limit; i++) {
        list.add(seeds[i]);
    }
    timerAdd.end(j);
    timerGet.start(j);
    for (int i = 0; i < limit; i++) {
        list.get(i);
    }
    timerGet.end(j);
    timerRemove.start(j);
    for (int i = 0; i < limit; i++) {
        list.remove(0);
    }
    timerRemove.end(j);
    }

结果如下：可以看到，所有ArrayList-based类型对于表头的remove操作耗时很长，而LinkedList则非常快；相应的，LinkedList的随机访问效率非常差。CopyOnWriteList在修改操作时，性能急剧下降。所以请不要在需要进行多次修改操作时使用 CopyOnWriteList。

vagabond1-1983 / blog