【JAVA秒会技术之秒杀面试官】秒杀Java面试官——集合篇（一）

秒杀Java面试官——集合篇（一）

一、集合的大体架构图

希望大家能牢牢记住下面这张框架图，一旦面试官让你“说说集合吧”，希望大家能立马给他画出来，边画边逐一介绍每个集合的特点，以及彼此的差异。重点是要从底层源代码的角度来给面试官分析。

一说到底层代码，可能很多人就头疼了，总认为知道和不知道对开发根本没多大实用价值，会应用就行了。这个观点，我暂不做评论。但是大家很庆幸的是，看到了本篇博客，博主将会带大家，来分析一些在面试中一定会用到的集合底层实现原理。

二、List

1.ArrayList和Vector的区别

第一句话：ArrayList和Vector底层都是数组实现的，初始容量都为10；在ArrayList的底层，是通过定义一个DEFAULT_CAPACITY的常量来指定的，而Vector的底层，是直接在空参构造中，通过写死了一个this(10)来指定的；

   （PS:标黑色的部分，估计学过Java的人都会说，人云亦云，但是你要是在面试中，说出了后面标红的部分，虽然意思一样，但是，你这样一讲，绝对瞬间提升了一个档次，立马就能够脱颖而出。后面的解析同理：黑色是众人皆知的常识，红色字体才是精髓）

ArrayList源码片段：

    /**
     * Default initial capacity.默认初始容量
     */
private static final int DEFAULT_CAPACITY = 10;=

Vector源码片段：

   /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.空参构造,其内部数据数组的大小为10，并且它的标准容量增量为零
     */
    public Vector() {
        this(10);
    }

   第二句话：Vector大部分方法的底层实现,都加了 synchronized关键字，所以Vector是线程同步的，而 ArrayList不是；

Vector源码片段：

   /**
     * Returns the number of components in this vector.
     */
    public synchronized int size() {
        return elementCount;
    }
    /**
     * Tests if this vector has no components.
     */
    public synchronized boolean isEmpty() {
        return elementCount == 0;
    }

ArrayList源码片段：

    /**
     * jdk1.6中：int newCapacity = (oldCapacity * 3)/2 + 1;
     */
    public void ensureCapacity(int minCapacity) {
     modCount++;
     int oldCapacity = elementData.length;
     if (minCapacity >oldCapacity) {
         Object oldData[] = elementData;
         int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity <minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
     }
    }

    /**
     * jdk1.7之后：int newCapacity = oldCapacity + (oldCapacity >> 1);
     */
    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);
    }

    /**
     * Vector中int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
     */  
    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);
    }

第一句话：ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构，它继承于AbstractSequentialList的双向链表，由于AbstractSequentialList 实现了get(i)、set()、add() 和 remove()这些骨干性函数，这也降低了List接口的复杂程度。

LinkedList源码片段：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

第二句话：ArrayList与LinkedList都是不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程从结构上修改了该列表，则它必须保持外部同步。同步的方法就是使用Collections.synchronizedList(Collection<T> c)来“包装”该列表。

static <T> Collection<T>  synchronizedCollection(Collection<T> c) 
返回指定 collection 支持的同步（线程安全的）

第三句话：对于随机访问get和set，ArrayList绝对优于LinkedList，因为从源码可以看出，ArrayList想要get(int index)元素时，直接返回index位置上的元素；而LinkedList需要通过for循环进行查找，虽然LinkedList已经在查找方法上做了优化，比如index < size / 2，则从左边开始查找，反之从右边开始查找，但是还是比ArrayList（随机查找）要慢。

ArrayList源码片段：

    public E get(int index) {
        rangeCheck(index); 
        checkForComodification();
        return ArrayList.this.elementData(offset +index); //直接返回索引
    }

LinkedList源码片段：

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item; //get()方法会调用node()方法，
}
//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;
        }
}

具体情况，可参看如下测试数据（数据来源于网络）：

#在index=1000出插入结果：
  array time:4
  linked time:240
  array insert time:20
  linked insert time:18
#在index=5000处插入结果： 
  array time:4
  linked time:229
  array insert time:13
  linked insert time:90
#在index=9000处插入结果：
  array time:4
  linked time:237
  array insert time:7
  linked insert time:92