java設(shè)計(jì)了一套集合（也叫容器）類庫，來支持最常用的數(shù)據(jù)結(jié)構(gòu)，Java集合類庫采用接口與實(shí)現(xiàn)分離的原則。下面主要梳理集合接口，集合類（包括集合抽象類和具體實(shí)現(xiàn)類）。

1 Java集合接口

Java的集合接口關(guān)系圖如下：

Java集合類接口圖.png

集合有兩個(gè)基本接口Collection和Map
（1） Collection接口的源碼如下：

public interface Collection<E> extends Iterable<E> {
    // Query Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    //返回迭代器對(duì)象，用來訪問集合中的元素
    Iterator<E> iterator();
    //返回集合的對(duì)象數(shù)組
    Object[] toArray();
    //添加元素
    boolean add(E e);
    //移除元素
    boolean remove(Object o);
    //判斷傳入集合是否被包含
    boolean containsAll(Collection<?> c);
    //與傳入集合求交集
    boolean retainAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
}

（2）Map用來存放鍵值對(duì)，Map接口源碼如下：

public interface Map<K,V> {
    // Query Operations
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    //獲取對(duì)應(yīng)k的值，如果沒有這個(gè)值，則返回null,K可以為null
    V get(Object key);
    // Modification Operations
    //插入k和v,此處可以插入k為null的鍵值對(duì)，但是v不能為null
    V put(K key, V value);
    V remove(Object key);

    // Bulk Operations

    void putAll(Map<? extends K, ? extends V> m);
  
    void clear();

    // Views
    /*--注意從下面三個(gè)返回的集中，可以刪除元素，與此同時(shí)也刪除了Map中的元素，但是不能添加元素---***/
    
    //返回Map中所有K的Set集
    Set<K> keySet();
    //返回Map中所有V的Collection集合
    Collection<V> values();
    //整個(gè)鍵值對(duì)作為一個(gè)Set集返回
    Set<Map.Entry<K, V>> entrySet();
   
        interface Entry<K,V> {
            K getKey();
            V getValue();
            V setValue(V value);
            boolean equals(Object o);
            int hashCode();
        }
    // Comparison and hashing

    boolean equals(Object o);
    int hashCode();
}

注意，在Java中訪問集合中某個(gè)位置元素，要使用迭代器（Iterator）。
（3）Iterator接口的源碼如下：

public interface Iterator<E> {
//返回將要訪問的下一個(gè)對(duì)象，如果已經(jīng)是集合的最后一個(gè)元素，將拋出NoSuchElementException錯(cuò)誤
E next();
//由于上面方法拋出錯(cuò)誤，因此在訪問集合元素之前，先判斷是否有下一個(gè)元素
boolean hasNext();
//移除元素之前，要先使用next方法定位到改元素；
void remove();
}

List是一個(gè)順序排列集合接口，List在特定位置添加元素的方法有兩種，一種是整數(shù)索引，一種是列表迭代器。
（4）List接口的源碼如下：

public interface List<E> extends Collection<E> {
    // Query Operations
    //繼承Collection方法，參考Collection源碼分析
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    ........
    
    // Positional Access Operations
    //獲取給定位置的元素
    E get(int index);
    //用新元素取代給定位置元素，返回原來的元素
    E set(int index, E element);
    //通過整數(shù)索引，在給定位置添加元素
    void add(int index, E element);
    //移除給定位置的元素
    E remove(int index);
    // Search Operations
    //返回與給定元素相等的元素在列表中第一次出現(xiàn)的位置，如果沒有返回-1
    int indexOf(Object o);
    //返回與給定元素相等的元素在列表中最后一次出現(xiàn)的位置，如果沒有放回-1
    int lastIndexOf(Object o);
    
    // List Iterators
    //返回一個(gè)列表迭代器
    ListIterator<E> listIterator();
    //返回一個(gè)列表迭代器，第一次調(diào)用next后，返回的給定索引的元素
    ListIterator<E> listIterator(int index);

    // View
    //返回List的某個(gè)范圍內(nèi)的子集合
    List<E> subList(int fromIndex, int toIndex);
}

由于Collection有的子集合（如Set）是無序的，所以Iterator接口中無add方法，但是對(duì)于List子集合需要使用迭代器添加指定位置的元素，因此ListIterator繼承Iterator，提供了add方法。
（5）ListIterator接口源碼如下：

public interface ListIterator<E> extends Iterator<E> {
    // Query Operations
    //繼承Iterator方法，參考Iterator源碼分析
    boolean hasNext();
    E next();
    //反向迭代列表時(shí)，判斷是否有元素
    boolean hasPrevious();
    //返回前一個(gè)對(duì)象，如果已經(jīng)是集合的第一個(gè)元素，將拋出NoSuchElementException錯(cuò)誤
    E previous();
    //返回下一次調(diào)用next方法后，元素的索引
    int nextIndex();
     //返回下一次調(diào)用previous方法后，元素的索引
    int previousIndex();
    // Modification Operations
    void remove();
    void set(E e);
    void add(E e);
}

Set接口和Collection接口的方法一樣，這里Java為什么要定義一個(gè)新的接口？是為了從概念上區(qū)分集合與集，方面擴(kuò)展。
SortedSet和SortedMap接口，顧名思義給開發(fā)者暴露了排序的方法，并可以返回某個(gè)范圍內(nèi)的子集
（6）SortedSet的源碼如下：

public interface SortedSet<E> extends Set<E> {
    //用于排序的方法，參考后續(xù)章節(jié)具體實(shí)現(xiàn)類
    Comparator<? super E> comparator();
    //下面三個(gè)方法，返回給定范圍內(nèi)的子SortedSet集
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    
    E first();
    E last();
}

（7）SortedMap的源碼如下：

public interface SortedMap<K,V> extends Map<K,V> {
    //用于排序的方法，參考后續(xù)章節(jié)具體實(shí)現(xiàn)類
    Comparator<? super K> comparator();
    //下面三個(gè)方法，返回給定范圍內(nèi)的子SortedMap
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);

    //下面三個(gè)方法和Map接口中方法一樣，參考Map接口源碼
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

Java SE6引入了NavigableSet和NavigableMap接口，用來在有序集和Map中查找遍歷方法
（8）NavigableSet源碼如下：

public interface NavigableSet<E> extends SortedSet<E> {

    E lower(E e);
    E floor(E e);
    .......

    //下面三個(gè)方法主要返回給定范圍內(nèi)的子NavigableSet,boolean 標(biāo)志是否包括邊界值
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);

    NavigableSet<E> headSet(E toElement, boolean inclusive);
    NavigableSet<E> tailSet(E fromElement, boolean inclusive);
    //下面三個(gè)方法和SortedSet接口中方法一樣，參考SortedSet接口源碼
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
}

（9）NavigableMap源碼如下：

public interface NavigableMap<K,V> extends SortedMap<K,V> {

    Map.Entry<K,V> lowerEntry(K key);
    K lowerKey(K key);
    Map.Entry<K,V> floorEntry(K key);
    K floorKey(K key)
    Map.Entry<K,V> ceilingEntry(K key);
    ........
    
    //下面三個(gè)方法，返回給定范圍內(nèi)的鍵的NavigableMap，boolean 表示是否包括邊界
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);
    NavigableMap<K,V> headMap(K toKey, boolean inclusive);
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

    //下面三個(gè)方法，與SortedMap方法一樣，參考SortedMap源碼
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
}

隊(duì)列是在尾部添加一個(gè)元素，在頭部刪除一個(gè)元素。雙端隊(duì)列是在頭部和尾部都可以刪除元素
（10）Queue的源碼如下：

public interface Queue<E> extends Collection<E> {

    //當(dāng)執(zhí)行add往隊(duì)列中添加元素時(shí)，如果隊(duì)列沒有滿，則往隊(duì)列尾部添加元素并返回true，否則add方法拋出異常，offer方法返回false
    boolean add(E e);
    boolean offer(E e);
    
    //當(dāng)執(zhí)行remove移除隊(duì)列中頭部元素時(shí)，如果隊(duì)列不空，則移除頭部元素并返回true，否則remove方法拋出異常，poll方法返回false
    E remove();
    E poll();
    
    //當(dāng)執(zhí)行element查看隊(duì)列中頭部元素時(shí)，如果隊(duì)列不空，則返回隊(duì)列中的頭部元素，否則element方法拋出異常，peek方法返回null
    E element();
    E peek();
}

（11）Deque（雙端隊(duì)列接口）源碼如下：

public interface Deque<E> extends Queue<E> {
    //當(dāng)給定的對(duì)象添加到雙端隊(duì)列的頭部和尾部時(shí)，如果隊(duì)列滿了，則前兩個(gè)方法拋出異常，后兩個(gè)方法返回false
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);

    //當(dāng)刪除雙端隊(duì)列頭部和尾部元素時(shí)，如果隊(duì)列為空，則前兩個(gè)方法拋出異常，后兩個(gè)方法返回null
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();

    //當(dāng)查詢雙端隊(duì)列頭部和尾部元素時(shí)，如果隊(duì)列為空，則前兩個(gè)方法拋出異常，后兩個(gè)方法返回null
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();

    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***

    //參考Queue 中的add、offer方法說明
    boolean add(E e);
    boolean offer(E e);
    //參考Queue 中的remove、poll方法說明
    E remove();
    E poll();
    //參考Queue 中的element、peek方法說明
    E element();
    E peek();

    // *** Stack methods ***
    void push(E e);
    E pop();

    // *** Collection methods ***
    //參考Collection 中的方法說明
    boolean remove(Object o);
    boolean contains(Object o);
    public int size();
    Iterator<E> iterator();
    Iterator<E> descendingIterator();
}

RandomAccess接口用于監(jiān)測List隨機(jī)訪問的效率，該接口沒有方法，ArrayList繼承了該接口。
（12）RandomAccess源碼：

public interface RandomAccess {

}

2. Java集合類

前面的Java集合接口中有大量的方法，這些方法主要通過抽象類和具體類實(shí)現(xiàn)。其中抽象類主要實(shí)現(xiàn)接口中一部分通用的方法，具體類針對(duì)具體的類型實(shí)現(xiàn)具體的方法。
下面是Java集合類圖：

java集合類圖.png

2.1 Java集合抽象類

對(duì)于公用的方法可在集合抽象類實(shí)現(xiàn)，一些具體的方法可抽象化在繼承的有具體特征的子類中實(shí)現(xiàn)。集合抽象類主要有AbstractCollection、AbstractMap
AbstractList、AbstractSet、AbstractQueue、AbstractSequentialList
這里以AbstractCollection源碼為例分析一下：
AbstractCollection的源碼如下：

public abstract class AbstractCollection<E> implements Collection<E> {

    protected AbstractCollection() {
    }

    // Query Operations
    //Collection接口中方法，可根據(jù)不同的集合，具體實(shí)現(xiàn)。
    //迭代器方法和集合大小方法抽象。
    public abstract Iterator<E> iterator();
    public abstract int size();
    
    //下面所有的方法都在抽象類中實(shí)現(xiàn)
    public boolean isEmpty() {
        return size() == 0;
    }
    
    //用迭代器，訪問逐次訪問集合中的元素，判斷是否包含給定的對(duì)象
    public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }

    //逐次訪問集合中的元素，轉(zhuǎn)換集合中對(duì)象為數(shù)組
    public Object[] toArray() {
       //根據(jù)集合大小定義數(shù)組
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) 
               // fewer elements than expected
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    public <T> T[] toArray(T[] a) {
        // Estimate size of array; be prepared to see more or fewer elements
        int size = size();
        T[] r = a.length >= size ? a :
                  (T[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);
        Iterator<E> it = iterator();

        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // fewer elements than expected
                if (a != r)
                    return Arrays.copyOf(r, i);
                r[i] = null; // null-terminate
                return r;
            }
            r[i] = (T)it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    //Integer.MAX_VALUE是int整形的最大取值2的31次方-1，這個(gè)常量用來控制集合的最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
        int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = cap + (cap >> 1) + 1;
                // overflow-conscious code
                if (newCap - MAX_ARRAY_SIZE > 0)
                    newCap = hugeCapacity(cap + 1);
                r = Arrays.copyOf(r, newCap);
            }
            r[i++] = (T)it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

    //返回集合的最大容量值
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError
                ("Required array size too large");
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    // 添加對(duì)象方法實(shí)現(xiàn)
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }
    //移除對(duì)象方法實(shí)現(xiàn)
    public boolean remove(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext()) {
                if (it.next()==null) {
                    it.remove();
                    return true;
                }
            }
        } else {
            while (it.hasNext()) {
                if (o.equals(it.next())) {
                    it.remove();
                    return true;
                }
            }
        }
        return false;
    }

    //批量操作方法實(shí)現(xiàn)
    //判斷傳入集合是否被包含方法實(shí)現(xiàn)
    public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }
    //添加傳入集合方法實(shí)現(xiàn)
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }
    //移除傳入集合方法實(shí)現(xiàn)
    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }
    //實(shí)現(xiàn)與傳入集合求交集方法
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

    //對(duì)象轉(zhuǎn)換為字符串
    public String toString() {
        Iterator<E> it = iterator();
        //如果集合中對(duì)象為null，返回"[]"
        if (! it.hasNext())
            return "[]";
        //拼接字符串
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }
}

2.2 Java集合具體實(shí)現(xiàn)類

我們項(xiàng)目中經(jīng)常使用的具體類（Java集合類圖中具體類）主要有LinkedList、ArrayList、HashSet、TreeSet、PriorityQueue、Array、Deque、HashMap、TreeMap，這些類的源碼解析，見后續(xù)章節(jié)的分析；
下面是Java集合具體類的主要特征，如下表：

具體集合類特征.png