一直以来虽然经常使用Java的集合框架，但是从来没有看过他们的源码。直到前段时间有人问我HashMap的实现原理，我当时很懵逼说不出个所以然来。最近恰好有时间，打算复习一遍集合框架，这是关于集合的第一篇博客，会有很多不足，希望各位大神能够一一指出，谢谢。
如果想看结论，请拉到尾部。

1、准备知识

1、了解数据结构的数组和链表等知识
2、了解二进制基础
3、了解Java位运算

2、ArrayList源码分析

• 日常用法

List<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);

        arrayList.remove(2);
        arrayList.add(2, 123123);

        for (Integer i:arrayList) {
            System.out.print(i+" ");
        }

• ArrayList构造方法初始化一个空数组

private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData; // non-private to simplify nested class access
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

• 调用add方法插入数据

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

  size变量是用来记录数组的元素总数。当使用add方法的时候首先调用ensureCapacityInternal方法，传入size+1进去，检查是否需要扩充elementData数组的大小。检查完毕之后再将e赋值给elementData数组 ，size再自增1。ensureCapacityInternal源码如下。

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    } 

  如果elementData数组为空，则在DEFAULT_CAPACITY和minCapacity（刚才的size+1）选取最大值，赋值给minCapacity。接着进入ensureExplicitCapacity方法，如果需要的最小容量（minCapacity）比当前数组长度还要大，则进入grow方法扩增数组。

 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);
    }

  接下来重点讲讲这个gorw方法，先通过elementData.length获取当前数组的容量大小赋值给oldCapacity。接着oldCapacity + (oldCapacity >> 1)，其中(oldCapacity >> 1)表示oldCapacity右移1位，它的值可以理解为oldCapacity除以2（至于为什么请百度二进制、移位操作等关键字）。总结起来就是在oldCapacity基础上扩增50%容量再赋值给newCapacity。最后使用Arrays工具类扩增elementData数组。

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

  整个核心就是System.arraycopy方法，将original数组从的所有数据复制到copy数组中，返回给调用方法。整个add方法添加数据流程就走完了。

• 如果是指定位置插入数据是怎样的呢？

public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        ensureCapacityInternal(size + 1); // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

  index下标表示插入位置，先检查下标是否越界，如果是则抛出异常。之后调用ensureCapacityInternal方法判断是否需要扩增数组，这个方法上面已经分析过，略。最重要的是System.arraycopy方法，为了空出index的位置，将elementData数组从index开始到（size - index）位置，都后移1位。此时数组的index位置已经空出来了，最后再将新的元素放进去，完成数据插入操作。

• 移除元素方法。在ArrayList中reomve有两种一种是根据下标移除remove(int)，另一种是根据对象移除remove(object)。由于两种方法大同小异，这里只针对下标移除来分析

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        modCount++;
        E oldValue = (E) 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;
    }

  直接看重点int numMoved = size - index - 1，因为是删除操作，size-1表示删除之后的数组元素长度，size-1-index表示删除元素之后要移动元素的总数。如果numMoved大于0，将elementData数组从index+1到numMoved的元素，往前移动1位（覆盖index位置的元素）。接着将elementData数组的最后一个元素设置为空，方便GC回收内存。

• 查找操作

public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        return (E) elementData[index];
    }

  这是一个很简单的方法，相信很多人都看得懂，但是仔细想深一层为什么数组通过一个下标就能够查找出元素？我们在实例化ArrayList的时候，elementData已经完成了初始化。此时JVM虚拟机中，Java堆中则为elementData数组对象开辟一片连续的内存空间，虚拟机栈则存储了elementData数组的引用声明，并且引用指向了Java堆的数组首地址。因此在内存中可以通过：首地址+（元素存储单元×数组下标）=元素地址，快速的寻找对应下标的元素值。

3、Vector源码分析

• 日常用法

        final CountDownLatch countDownLatch = new CountDownLatch(2);
        final List<Integer> vector = new Vector<>();
        Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 50; i < 100; i++) {
                    vector.add(i);
                }
                countDownLatch.countDown();
            }
        });
        Thread thread2 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 50; i++) {
                    vector.add(i);
                }
                countDownLatch.countDown();
            }
        });
        thread1.start();
        thread2.start();

        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        for (Integer k : vector) {
            System.out.println(k);
        }
        System.out.println("总数" + vector.size());

  虽然Vector和ArrayList有很多相似的地方，但是两者之间也有比较明显的差异第一个差异就是Vector是线程安全而ArrayList不是。第二个就是Vector能够自定义数组增量。下面挑出部分和ArrayList不相同的源码分析。

• Vector实例化

public Vector() {
        this(10);
    }
public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

  这三个构造方法无论你选择哪一个实例化，最终会走到Vector(int initialCapacity, int capacityIncrement)方法，初始化一个长度为initialCapacity的object数组和capacityIncrement。其中capacityIncrement是一个很重要的变量它后期决定了elementData数组扩增容量。

• 调用add方法插入数据。比起ArrayList，Vector许多对外公开的方法都加上了synchronized关键字声明，这就是Vector为什么是线程安全的原因。

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
}
private void ensureCapacityHelper(int minCapacity) {
        // 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 + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
}

  Vector与ArrayList比较明显不同就是grow方法数组容量的扩增算法，oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity)。
　　如果是通过new Vector()实例化对象，此时capacityIncrement变量的值就会默认为0，那每次容量就只是扩增一倍（100%）。
　　如果是通过Vector(int initialCapacity, int capacityIncrement)实例化Vector，只要你传入的capacityIncrement不小于0，那么数组的容量就能按照你设置的值来扩增。其它代码部分与ArrayList差不多。

4、LinkedList源码分析

• 日常用法

List<Integer> linkedList = new LinkedList<>();

        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);

        linkedList.remove(2);
        linkedList.add(2, 123123);

        for (Integer i:linkedList) {
            System.out.print(i+" ");
        }

• 构造方法

transient Node<E> first;
transient Node<E> last;
public LinkedList() { 
}

  LinkedList的构造方法是一个空方法，此时指针变量first和last的初始值都为null。

• 链表节点静态类

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

  明显看出这是一个双向链表节点，item是用来存放节点值，next是尾指针指向下一个节点，prev是头指针指向前一个节点。

• 插入数据

public boolean add(E e) {
　　　linkLast(e);
   　　　return true; 
}
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

  初次调用add方法时，如果此时链表没有节点，last指针必定为空的，因此指针l也为空，接着通过new Node<>(l, e, null)创造第一个节点，让指针last、first都指向这个节点。此时整个链表只有一个节点。
　　当再次调用add方法时，l指向lsat指向的节点（也就是第一个节点）。再通过new Node<>(l, e, null)创造第二个节点（传入l已经有值了，此时Node里面的prev指针指向了l）。last重新指向第二个节点newNode。因为l不为空，则使l的尾指针next指向newNode，完成两个节点互相关联。后续只要往链表添加数据，就会按此步骤逐个的添加节点完成双向绑定，形成一个双向链表。

• 根据下标插入数据

public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

  先是使用checkPositionIndex检查index下标是否越界。有的话则抛出异常。没有继续往下走，如果插入下标恰好位于数组的末尾，直接通过linkLast方法将节点插入到链表末尾。如果不是，先用node方法寻找链表中index位置的节点。再通过linkBefore方法将节点插入到链表中。咋们先看看node方法的源码

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

  这个node方法第一眼看上去有点懵逼，细看之后知道了大概思路。(size >> 1)这个前面就说过，简单来说就是size除以2的值。接着判断index下标是在整个链表前半段还是后半段。
　　如果是前半段，x指向链表的头指针first，从头部遍历循环到index的位置，返回index的节点。
　　如果是后半段，x指向链表的尾指针last， 从尾部遍历循环到index的位置，返回index的节点。

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

  如果succ是链表的头结点（第一个节点），pred=null（succ是头结点，没有前驱节点）,然后通过new Node<>(pred, e, succ)创建一个新节点（这个新节点的头指针指向pred，刚才说过pred=null，尾指针指向succ）。接着succ的头指针指向新节点newNode。最后由于pred为空null，直接让first指针重新指向newNode，此时newNode变成了头结点。
　　如果succ是链表的非头结点，pred指针指向succ的前驱节点。然后通过new Node<>(pred, e, succ)创建一个新节点（这个新节点的头指针指向pred，尾指针指向succ）。接着让succ节点的头指针指向新节点newNode。最后由于pred不为空，让pred的尾指针指向newNode。newNode就和其它节点完成双向关联，形成一个双向链表。

• 根据下标移除数据

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
}
E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

  remove方法中根据下标通过node方法找到对应的node节点，进入unlink方法进行删除操作。Node<E> x表示将要删除的节点，next指针指向x的后继节点。prev指针指向x的前驱节点。接下来要分三种情况来删除节点。
　　第一种情况，x是头结点。判断prev指针为空，first指向next(也就是第二个节点)。此时next不为空，next节点的prev指针指向prev（prev是一个空值）。最后x节点尾指针切断与后节点的关联（x.next=null）。
　　第二种情况，x是尾结点。判断prev指针不为空，prev节点的next指针指向next（next是一个空值），x节点prev指针切断与前节点的关联（x.prev=null）。此时next为空，让last指针重新指向prev（也就是倒数第二个节点）。
　　第三种情况，x是中间节点。判读那prev不为空，prev的尾指针next指向next后继节点，x切断与前驱节点的关联（x.prev=null）。判断next不为空，next的头指针prev指向prev前驱节点，x切断与后继节点的关联（x.next = null）。

• 查找数据

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

  一个简单的方法，检查下标是否越界，接着进入node方法（node的源码上面已经分析过）遍历链表，返回找到的节点的值。

5、总结

  从使用方法的角度分析。ArrayList属于非线程安全，而Vector则属于线程安全。如果是开发中没有线程同步的需求，推荐优先使用ArrayList。因此其内部没有synchronized，执行效率会比Vector快很多。
　　从数据结构的角度分析。ArrayList是一个数组结构（Vector同理），数组在内存中是一片连续存在的片段，在查找元素的时候数组能够很方便的通过内存计算直接找到对应的元素内存。但是它也有很大的缺点。我们假设需要往数组插入或删除数据的位置为i，数组元素长度为n，则需要搬运数据n-i次才能完成插入、删除操作，导致其效率不如LinkedList。
　　LinkedList的底层是一个双向链表结构，在进行查找操作的时候需要花费非常非常多的时间来遍历整个链表（哪怕只遍历一半），这就是LinkedList在查找效率不如ArrayList快的原因。但是由于其链表结构的特殊性，在插入、删除数据的时候，只需要修改链表节点的前后指针就可以完成操作，其的效率远远高于ArrayList。

6、参考资料（自备梯子）

https://developer.android.com/reference/java/util/ArrayList
https://developer.android.com/reference/java/util/Vector
https://developer.android.com/reference/java/util/LinkedList