摘要：是非，而是，這意味著是線程安全的，多個線程可以共享一個而如果沒有正確的同步的話，多個線程是不能共享的。另一個區別是的迭代器是迭代器，而的迭代器不

這里只解析一些常用的、比較重要的一些集合類，并且作者水平有限，有些地方可能解析不到位或者解析錯誤，還望各位讀者指出錯誤。

Collection
     List
          ArrayList
          LinkedList
          Vector
               Stack
     Queue
          Deque
               LinkedList
     Set
          SortedSet
          HashSet
          TreeSet
Map
     HashMap
     HashTable
     TreeMap
     WeakHashMap

Java集合的一個大體框架，針對常用的方法來對集合類進行解析(JDK1.8)

List
List就是一個接口，繼承了接口Iterator，是為了獲得迭代器(Iterator)，用于遍歷集合中的數據
定義了一些集合常用的方法add(0)、remove()等等

List--ArrayList
ArrayList底層數據結構是數組實現，非線程安全
成員變量：

transient Object[] elementData;  //這就是ArrayList類中存放數據的數組
private int size;  //記錄的是當前在數組中可插入的索引值，表示的是當前數組的元素個數，并不表示當前數組的實際大小

常用方法解析：

1.construct
  public ArrayList();     //沒有指定大小的集合,elementData = {}，在第一次執行add()方法的時候，就會設置數組的大小為10(DEFAULT_CAPACITY)
  public ArrayList(Collection c);  //參數一個集合，然后將參數復制到elementData上
  public ArrayList(int initialCapacity);  //參數集合大小，創建對象的時候就將數組的大小通過參數傳進來，創建數組：elementData = new Object[initialCapacity];

2.add
  public boolean add(E e);  
  //添加element之前，先調用ensureCapacityInternal(size+1)，比較數組空間大小和當前的索引值，如果當前要插入的索引值大于數組的大小，就要執行grow(minCapacity)方法，
  //就是加大數組空間grow(minCapacity)是這樣實現的，將得到oldCapacity=elementData.length，然后newCapacity=oldCapacity+(oldCapacity>>1)，也就是在原來數組空間的大小之上再   
  //加上原來的一半，具體還是得看代碼   

  public void add(int index,E element);
  //在指定的索引出插入值，首先要判斷索引是否越界，條件是(index>size || index<0)，符合任意條件，就拋出索引越界異常，因為這里是跟size比較，size是當前要插入到數組中的索引值，并非
  //數組的實際大小，這么做是為了防止這個浪費空間，如果size=10，index=100(假如數組實際大小超過100)，那這樣就會導致index為10~99之間的空間浪費了

  public boolean addAll(Collection c);
  public void addAll(int index,Collection c);
  //這兩個方法與上面類似，不再贅述

3.remove
  public E remove(inde index);
  //index >= size，拋出數組索引越界異常
  //否則：E oldValue=elementData[index],將該索引位置后面的元素（直到index=size-1）都往前移動，并且elementData[--size]=null,然后返回oldValue
  
  public boolean remove(Object o);
  //首先遍歷elementData，判斷o是否在elementData中，沒有則返回false
  //否則：記錄當前的index，然后調用fastRemove()方法

  private void fastRemove(int index);
  //這個跟remove(index)方法有些類似，也是將當前索引位置后面的元素往前移動，并且elementData[--size]=null;

List--LinkedList
LinkedList，顧名思義，其實就是一個雙向鏈表，這也表明了LinkedList可以存儲無數個元素，只要空間允許（因為地址不連續，只要有空間，就可以用來開辟節點，然后連上鏈表），非線程安全，非線程安全
成員變量：

transient int size = 0;   //當前鏈表中的元素個數
transient Node first;  //表頭節點,Node是內部類，之后三個屬性，E item(值)，Node next(下一個節點),Node prev(前一個節點);
transient Node last;   //表尾節點

常用方法解析：

1.construct
  public LinkedList();    //空實現
  public LinkedList(Collection c);  //執行上面的空方法，然后addAll(c),將c添加到鏈表中

2.add
  public boolean add(E e);
  //直接調用linkLast(e) 方法，然后返回true
  //看一下linkLast(E e)方法，這個方法實現的就是在雙向鏈表的表尾添加一個元素，這個具體可以去搜索一下雙向鏈表

  public void add(int index,E e);
  //首先判斷index是否越界，判斷標準就是index>=0 && index<=size
  //如果index=size，相當于在表尾添加節點，直接調用linkLast(e);
  //否則：調用linkBefore(e,node(index))函數,node(index)函數的作用是為了獲取到當前所在索引的節點，因為鏈表每個節點的地址不是連續的，所以無法使用索引，這里的index只是標識了在這個
  //鏈表中的第幾個
  //再看一下linkBefore(e,nodex(index))函數，通過node(index)獲取當前索引的節點，接下來要新增的節點就處在當前節點的前面，具體實現搜索雙向鏈表插入節點

  public boolean addAll(Collection c);
  public void addAll(int index,Collection c);
  //類似

  public void linkFirst(E e);
  //從表頭添加節點
  public void linkLast(E e);
 //從表尾添加節點

3.remove
  public E remove();
  //調用removeFirst();

  public E remove(int index);
  //判斷index的合法性
  //定位到index所在的節點，然后刪除該節點

  public boolean remove(Object o);
  //判斷o是否在鏈表中，如在鏈表中，即可刪除

  public E removeFirst();
  //刪除鏈表的頭節點

  public E removeLast();
  //刪除鏈表的尾節點

List--Vector
Vector與ArrayList類似，底層數據結構也是數組，但是Vector是線程安全的
成員變量：

protected Object[] elementData;   //存放數據的數組  //被protectd修飾的成員變量，子類可以使用，例如Stack
protected int elementCount;       //數組中的實際元素個數
protected int capacityIncrement;  //數組容量的每次增量大小

常用方法解析；

1.construct
  public Vector();   --> 調用this(10);
  public Vector(int initialCapacity);  --> 調用this(initialCapacity,0)，數組容量的增量沒有指定的話，就為0，在每次給數組重新設置容量的時候，容量為原來的2倍
  public Vector(int initialCapacity,int capacityIncrement);  每次給數組重設容量的時候，新容量=舊容量+增量
  public Vector(Collection c);   //將集合c中的數據復制到elementData
  
2.add
  //與ArrayList除了線程安全，其余大同小異
  public synchronized boolean add(E e);

  public void add(int index,E element);
  //調用了synchronized void insertElement(E obj,int index)

  public synchronized void addElement(E obj);

3.remove
  public synchronized void removeElementAt(inde index);
  public synchronized boolean removeElement(Object obj);
  public synchronized E remove(int index);

List--Vector--Stack
Stack繼承自Vector，是一個棧，進棧元素添加在數組最后面，出棧將最后一個元素彈出，push()和pop()方法體內調用的都是父類Vector的方法，所以也是線程安全的
常用方法解析：

1.construct
  public Stack();  //空方法實現

2.public E push(E item); 
  //實際上調用的是父類的addElement(E e)方法，并返回item

  public synchronized E pop();
  //調用peek()方法獲取棧頂元素，然后調用父類的removeElement(int index)方法刪除棧頂元素，并返回棧頂元素

  public synchronized E peek();
  //返回棧頂元素

Queue
Queue是一個接口，隊列

Queue--Deque
Deque也是一個接口，繼承了Queue接口，并定義相當多的方法

Queue--Deque--LinkedList
LinkedList實現了Deque接口，非線程安全，要創建一個隊列，就讓一個Queue引用指向LinkedList對象，隊列的特點就是先進先出，跟排隊買東西時一樣的，
LinkedList在上面已經說過了，不再贅述

Set
Set是一個不包含重復元素的Collection接口，Set最多只能有一個null元素

Set--SortedSet
也是一個接口

Set--HashSet
底層數據結構居然是用HashMap實現的，也就造成了元素是無序的，也就無法通過索引來獲取值，不包含重復數據，非線程安全
每次調用add(E e)方法的時候，都是直接把參數e當作數據容器map的key(從這可以看出來為什么HashSet不能包含重復值了)，PRESENT當作value
并且要遍歷HashSet只能通過獲取迭代器來講HashSet中的元素迭代出來
成員變量：

HashMap map;   //存放數據的容器
private static final Object PRESENT = new Object();   //就是為了填充map的value的那個位置，沒有其他任何作用

常用方法解析：

1.construct
  public HashSet(){
     map = new HashMap<>();  }   //hashmap沒有指定容量 
  public HashSet(int initialCapacity){
     map = new HashMap<>(initialCapacity);  }   //指定初始化容量
  public HashSet(int initialCapacity,float loadFactor){
     map = new HashMap<>(initialCapacity,loadFactor);  }   //指定初始化容量，并
  public HashSet(int initialCapacity,float loadFactor,boolean dummy){
     map = new LinkedHashMap<>(initialCapacity,loadFactor);  }
  public HashSet(Collection c){
     map = new HashMap<>(Math.max((int)(c.size()/.75f)+1,16));  }

2.add
  public boolean add(E e){
     return map.put(e,PRESENT) == null;
  }
  //很簡單，就是把要插入的元素當作HashMap的key，而HashMap的key是不能重復的，所以HashSet是不能包含重復值的

3.remove
  public boolean remove(Object o){
     return map.remove(o) == PRESENT;
  }

4.iterator
  public Iterator iterator(){
     return map.keySet.iterator();
  }
  //通過迭代器遍歷HashSet中的元素

Map
Map是一個Key-Value的數據存儲結構，是一個接口，定義了大量的接口方法

Map--HashMap
HashMap是Map的實現類，可以看到HashMap的底層也是使用數組實現的，但不同的是，數組的每個元素又是一個鏈表的頭節點，所以HashMap的底層數據結構是數組+單向鏈表(如果鏈表的節點數量過多，則使用紅黑樹)來實現的，非線程安全
成員變量：

transient int size;   //當前數組中的元素個數   (transient關鍵字)
transient Node[] table;  //存放數據的容器，是一個散列表(數組+單向鏈表)，數組中的每個元素都是一個鏈表的頭節點，
transient Set> entrySet;  //
final float loadFactor;  //負載因子，定義為：散列表的實際數目/散列表的容量，如果size > loadFactor*capacity，那就需要擴容了，默認是0.75，
                         //負載因子衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是O(n),
                         //因此，如果負載因子越大，對空間的利用率很高，然后后果就是查找效率的降低，集中表現就是對鏈表的迭代遍歷會變慢；如果負載因子太小，那么散列表的數據過于稀疏，對空間造成
                         //嚴重浪費
transient int modCount;  //修改次數，由于HashMap是非線程安全的，所以如果在使用迭代器的過程中，如果有其他線程修改了map，那么將拋出ConcurrentModificationException，
                         //這就是所謂的fail-fast策略，這一實現就是在內部類迭代器中添加成員變量expectedModCount來記錄當前的modCount，然后再迭代的過程中判斷modCount和expectedModCount    
                         //是否相等，不相等就表明有其他線程修改了該map

常用方法解析

1.construct
public HashMap();  //構建一個初始容量為16，負載因子為0.75的HashMap
public HashMap(int initialCapacity);  //構建一個初始容量為initialCapacity，負載因子為0.75的HashMap
public HashMap(int innitialCapacity,floadloadFactor);  //指定初始容量和負載因子創建一個HashMap

2.put
  public V put(K key,V value){
    return putVal(hash(key),key,value,false,true);  //調用putVal方法
  }

  public V putVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict);
  //1.若table是否為空或者長度為0，則調用resize()方法，則給數組(table)重設大小
  //2.否則獲取table的長度n，并(n-1)&hash獲得該元素在table中的索引，并獲取當前索引位置的元素p，若該元素為空，則直接將新元素放在table上
      并且如果(++size > threshold) = true，那么調用resize()方法，重置數組大小，并返回null(因為該索引處沒有節點，所以為null)，方法結束
  //3.否則的話，若(p.hash == hash && ((k=p.key)==key || (key!=null && key.equals(k))))，這個判斷語句是在判斷原索引上的key和要插入的key是否是同一個key，
      如果是的話，則賦值為臨時變量e
  //4.否則說明要遍歷以p為鏈表頭節點的鏈表，遍歷過程中每個節點的key都要判斷和新增的key是否一樣，若一樣，賦值給臨時變量e
  //5.否則，將當前的key和value構造成一個Node對象，然后從這個鏈表的頭節點前插入
  //6.注意還沒結束，e!=null為true(e相當于是舊值)，則返回e.value
  //7.否則 如果(++size > threshold) = true，那么調用resize()方法，重置數組大小，并返回null(因為該索引處沒有節點，所以為null)，方法結束
  //注意：1)這里獲取key所在table中的索引值算法，請看這個：http://pengranxiang.iteye.com/blog/543893
          2)如果鏈表過長，會將鏈表轉換成紅黑樹

3.final Node[] resize();
  //1.若oldCap(原來數組的大小)大于MAXIMUM_CAPACITY,也就是超過最大值，那就沒辦法了，隨你去碰撞了
  //2.否則：newCap = oldCap<<1，擴大2倍

4.remove
  public V remove(Object key){
     Node e;
     reutrn (e = removeNode(hash(key),key,null,false,true)) == null ? null : e.value;
  }

  final Node removeNode(int hash,Object key,Object value,boolean matchValue,movable);
  //1.若table==null || table.length<=0，則直接返回null，方法結束
  //2.否則：通過((n=table.length-1) & hash)獲取到該key所在數組中的索引，并將該索引處的元素賦值給p，
      若(p.hash=hash && ((k=p.key)==key || (key !=null && key.equals(k)))) = true，說明該索引所在的位置正在是要刪除的節點，然后將該節點賦值給臨時變量node
  //3.否則：遍歷以p為頭節點的鏈表，找到對應的節點，然后賦值給臨時變量node，將node的前一個節點賦值給p
  //注意：node是要刪除的節點，p是node的前一個節點(如果node是鏈表的頭節點，那么p=null)，鏈表的具體操作可以看這個方法

Map--HashTable
HashTable也是Map的實現類，跟HashMap差不多，線程安全的
HashMap和HashTable的區別

1.HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)。

2.HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMap的。Java 5提供了
  ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。

3.另一個區別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結構（增加或者移除元素），將會拋出
  ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這并不是一個一定發生的行為，要看JVM。這條同樣也是Enumeration和
  Iterator的區別。

4.由于Hashtable是線程安全的也是synchronized，所以在單線程環境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過Hashtable。

5.HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

小總結：

參考：HashMap
HashMap底層算法解析
HashMap
HashTable的區別