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

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

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

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

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

List--ArrayList
ArrayList底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組實現(xiàn)，非線程安全
成員變量：

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

常用方法解析：

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

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

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

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

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

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

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

transient int size = 0;   //當(dāng)前鏈表中的元素個數(shù)
transient Node first;  //表頭節(jié)點(diǎn),Node是內(nèi)部類，之后三個屬性，E item(值)，Node next(下一個節(jié)點(diǎn)),Node prev(前一個節(jié)點(diǎn));
transient Node last;   //表尾節(jié)點(diǎn)

常用方法解析：

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

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

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

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

  public void linkFirst(E e);
  //從表頭添加節(jié)點(diǎn)
  public void linkLast(E e);
 //從表尾添加節(jié)點(diǎn)

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

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

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

  public E removeFirst();
  //刪除鏈表的頭節(jié)點(diǎn)

  public E removeLast();
  //刪除鏈表的尾節(jié)點(diǎn)

List--Vector
Vector與ArrayList類似，底層數(shù)據(jù)結(jié)構(gòu)也是數(shù)組，但是Vector是線程安全的
成員變量：

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

常用方法解析；

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

  public void add(int index,E element);
  //調(diào)用了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，是一個棧，進(jìn)棧元素添加在數(shù)組最后面，出棧將最后一個元素彈出，push()和pop()方法體內(nèi)調(diào)用的都是父類Vector的方法，所以也是線程安全的
常用方法解析：

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

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

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

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

Queue
Queue是一個接口，隊列

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

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

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

Set--SortedSet
也是一個接口

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

HashMap map;   //存放數(shù)據(jù)的容器
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;
  }
  //很簡單，就是把要插入的元素當(dāng)作HashMap的key，而HashMap的key是不能重復(fù)的，所以HashSet是不能包含重復(fù)值的

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的數(shù)據(jù)存儲結(jié)構(gòu)，是一個接口，定義了大量的接口方法

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

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

常用方法解析

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

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

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

3.final Node[] resize();
  //1.若oldCap(原來數(shù)組的大小)大于MAXIMUM_CAPACITY,也就是超過最大值，那就沒辦法了，隨你去碰撞了
  //2.否則：newCap = oldCap<<1，擴(kuò)大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，方法結(jié)束
  //2.否則：通過((n=table.length-1) & hash)獲取到該key所在數(shù)組中的索引，并將該索引處的元素賦值給p，
      若(p.hash=hash && ((k=p.key)==key || (key !=null && key.equals(k)))) = true，說明該索引所在的位置正在是要刪除的節(jié)點(diǎn)，然后將該節(jié)點(diǎn)賦值給臨時變量node
  //3.否則：遍歷以p為頭節(jié)點(diǎn)的鏈表，找到對應(yīng)的節(jié)點(diǎn)，然后賦值給臨時變量node，將node的前一個節(jié)點(diǎn)賦值給p
  //注意：node是要刪除的節(jié)點(diǎn)，p是node的前一個節(jié)點(diǎn)(如果node是鏈表的頭節(jié)點(diǎn)，那么p=null)，鏈表的具體操作可以看這個方法

Map--HashTable
HashTable也是Map的實現(xiàn)類，跟HashMap差不多，線程安全的
HashMap和HashTable的區(qū)別

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

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

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

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

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

小總結(jié)：

參考：HashMap
HashMap底層算法解析
HashMap
HashTable的區(qū)別