ArrayList源代码小记

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List 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 Vector, except that it is unsynchronized.)

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized 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 the LinkedList implementation.

Each ArrayList instance has a capacity. 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.

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must 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 Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:

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

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw aConcurrentModificationException. 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 ConcurrentModificationExceptionon 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.

上面是ArrayList的官方文档。

总结一下：

1. ArrayList能存储null

2. ArrayList和Vector大致相同，除了ArrayList不是同步的。

3. get(),set()等操作时间复杂度为O(1)

4. 其他操作：add()等时间复杂度都是粗略线性的
5. ArrayList非同步容器，如果需要使用同步ArrayList，可以使用Collections.synchronizedList`包装这个容器。使用这个包装容器最好在创建是就开始
6. ArrayList所返回的迭代器是快速失败的，在获取迭代器后，应该使用迭代器本身的方法进行remove或add
7. 迭代器的快速失败不是绝对保证，因此，编写依赖于此异常的程序以确保其正确性是错误的

Arrays.asList(xx).toArray(xxx) Bug

相关连接： Java Bug 6260652

按道理来说，如果没有指定toArray()的参数类型，那么应该返回Object[]类型。但是Arrays.asList(xxx).toArray(xxx)虽然编译时是是返回的Object[]类型，但是运行时还是返回的具体的类型，比如：

        List<String> list = Arrays.asList("1", "2", "3");
        Object[] objects= list.toArray();
        objects[1]=new Object();

就会报错。

究其原因，是因为Arrays.asList返回的ArrayList是通过泛型数组保存的数据：

 private final E[] a;

而实现toArray()方法的时候，直接返回a.clone,而他的初始化是通过直接等于传入的数组初始化：

    ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }

这样就相当于：

     Object[] a=new String[2];
      a[1]=new Object();

这样在运行时a的实际类型是String[]，传入一个Object当然不行。

其他容器没有这个bug是因为他们都是通过Object[]保存的元素。

泛型的类型比较

在使用泛型的通配符的时候，由于编译期会将通配符替换为：capture#1,这个特殊的类型并不是Object的子类，但是某些时候想想进行类型（class）比较。可以先强制类型转化，然后利用运行时类型进行比较。

   public static <T> void test(Class<? extends T[]> type) {
        System.out.println((Object) type==(Object) Object[].class);
    }

个人感觉还可以使用.isInstance方法

    public static <T> void test(Class<? extends T[]> type) {
        System.out.println(type.isInstance(new Object[0]));
    }

数组复制

数组的拷贝可以使用Arrays.cppyOf(T[],int)

第二个参数为需要生成的数组的长度，可以比原来的大，也可以比原来的小。

如果只是想复制一个一模一样的数组的话，可以使用xx.clone()方法

System.arrayCopy参数比较复杂，Arrays.cppyOf(T[],int)是对它的封装。

ArrayList

ArrayList包含两个静态字段

DEFAULTCAPACITY_EMPTY_ELEMENTDATA //用于表示无参初始化，new ArrayList() ，此时内部数组是一个大小为1的数组
EMPTY_ELEMENTDATA //用于表示使用大小为0的容器初始化

使用EMPTY_ELEMENTDATA标志来表示一个空数组，因为任何空数组都等于空数组，因此可以使用一个静态的空数组来共享表示elementData为空，可以节约内存。

使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA标志使用的无参构造函数，便于在第一次add操作的时候，使用DEFAULT_CAPACITY扩容

terimToSize()

在确定ArrayList不会插入元素后，可以使用terimToSize()方法将扩容导致多余出来的元素删除。

toArrays(T[] a)

由于泛型是通过擦除实现，因此在想要获取指定类型数组而不是Object[]的时候可以使用toArrays(T[] a)方法，此方法有两只使用方式：

String[] array=list.toArray(new String[0]);
//第二种
String[] array1=new String[list.size()];
list.toArray(array1);

第一种会自己使用Array.newInstance()创建一个合适的大小的数组，第二个是直接拷贝。

《Effective Java》第五十四条说：研究表明使用预先分配大小的方式并不比直接new String[0]快，因此非特殊情况，不必纠结到底使用哪一种。

有意思的代码

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

之前一直都说ArrayList底层是通过数组实现，因此在元素中间进行插入和删除操作的时候，需要将所删除的元素的后面的元素一个一个进行移动，性能是比较慢的。

但是可以看到add()方法的实现中，是先扩容，然后使用System.arraycopy直接整段数组复制，这比for循环数组效率要高很多

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

同样remove()方法也是，它直接将需要移除的数组整体向前移动一段，覆盖掉要移除的元素。

subList()

ArrayList#subList()返回一个包含指定范围的List，但是在ArrayList#subList()返回的是一个内部类：SubList，
说一说这个SubList

final void checkForComodification() {
  if (expectedModCount != ArrayList.this.modCount)
            throw new ConcurrentModificationException();
  }

这是里面的一个关键方法，对比外部类的modCount与实例化时候初始化的SubList对象的modCount是否相同，不同则抛出异常。

这个方法基本在SubList方法中每个Public方法都会调用。作用是如果外部类修改了元素，则这个SubList便会失效。

为什么这样呢？

看SubList源代码可以发现SubList并没有使用类似ArrayList#Object[]来保存数据成员。而是

private final int parentOffset;
private final int offset;

两个指针。每次对SubList操作其实都是通过这两个指针对外部类数据进行操作。

也就是说SubList和ArrayList是共用同一个elementData的，这样做的好处就是得到一个SubList十分高效，因为并没有进行for循环赋值，而想到得到一个独立的子ArrayList,可以如下：

     List<String> subList=new ArrayList<>(arrayList.subList(0,1));

这样得到的subList便是独立的，并且底层使用的System.arraycopy()，性能比for高效的多。

Vector

一般来说，虽然Vector线程安全，但是Vector的实现非常简单，就是在每个操作上添加锁，但是这样的实现既不安全又很慢，不安全是因为我们一般操作都需要给整个容器添加锁，比如遍历整个锁等，而慢是因为对于容器的锁只用在外面一个就能线程全权访问，为什么要每个操作等待一个锁，因此Vector的锁变成了一种负担，在需要使用线程安全的List的时候，

读多：CopyOnWriteArrayList

读写均匀/写多：Collections.synchronizedList

相关连接：[Why is Java Vector (and Stack) class considered obsolete or deprecated?]

总结

ArrayList算是比较简单的列表容器，底层使用Object数组保存元素，默认扩容大小为10，每次扩容为原来的1.5倍（oldLength + (oldLength>>1)）。里面包含了大量的数组拷贝操作，非线程安全，Arraylist使用全局静态对象标致空对象，重复利用同一个对象，节约内存，ArrayList#remove(Object o)使用了o.equals()方法，因此想要正常工作，元素需要重载equals