ArrayList

ArrayList是常用的List之一。
本文通过源码，一起学习ArrayList。

• ArrayList定义

ArrayList继承AbstractList，实现List、RandomAccess、Cloneable和Serializable接口，默认数组elementData大小为10。
ArrayList通过维护一个elementData数组对外提供服务。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
}

• ArrayList常规操作

ArrayList提供add、get、set、remove、clear、addAll、indexOf、sort等方法。

• ArrayList注意点

1. add方法会根据实际大小调整elementData数组大小

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

调用add方法时，会调用ensureCapacityInternal方法，ensureCapacityInternal方法最后会调用ensureExplicitCapacity方法。可以看到，ensureExplicitCapacity会比较minCapacity是否大于elementData.length，如果大于，将grow成更大容量的elementData。

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

2. ArrayList非线程安全
   例如：add方法，整个操作并不会进行lock操作，并发下，N次size++值并不是实际想要的。

public class ArrayListTest {
    private static ArrayList<String> arrayList = new ArrayList();
    private static int test = 0;

    public static void main(String[] args) {
        ExecutorService executorService = Executors.newFixedThreadPool(100);
        Collection<Callable<String>> jobs = new ArrayList();
        for (int i = 0;i < 100000;i++) {
            Callable job = new Callable() {
                @Override
                public String call() throws Exception {
                    test++;
                    arrayList.add("test1");
                    return "ok";
                }
            };
            jobs.add(job);
        }
        try {
            executorService.invokeAll(jobs);
            System.out.println(test);
            System.out.println(arrayList.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

执行结果

99776
99701

其实每次结果可能是不一样的，执行100000次test++，test并不等于100000，执行100000次arrayList.add("test1")，arrayList.size()并不等于100000。
说明ArrayList的add方法并不线程安全。

3. remove、addAll等，会调用System.arraycopy方法。
   System.arraycopy是个native方法，JDK native源码查看。
4. indexOf方法是线性查找元素

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

• ArrayList实现RandomAccess接口的作用

工具类java.util.Collections中，对实现RandomAccess接口的类，采用不同的查找算法。

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

可以看到，对于实现RandomAccess接口的类，将调用Collections.indexedBinarySearch方法。
关于Collections介绍//TODO