集合初始化大小彙總

這裡要讨論這些常用的預設初始容量和擴容的原因是：

當底層實作涉及到擴容時，容器或重新配置設定一段更大的連續記憶體（如果是離散配置設定則不需要重新配置設定，離散配置設定都是插入新元素時動态配置設定記憶體），要将容器原來的資料全部複制到新的記憶體上，這無疑使效率大大降低。

加載因子的系數小于等于1，意指 即當 元素個數 超過 容量長度*加載因子的系數 時，進行擴容。

另外，擴容也是有預設的倍數的，不同的容器擴容情況不同。

List 元素是有序的、可重複

ArrayList、Vector預設初始容量為10

Vector：線程安全，但速度慢

底層資料結構是數組結構

加載因子為1：即當 元素個數 超過 容量長度 時，進行擴容

擴容增量：原容量的 1倍

如 Vector的容量為10，一次擴容後是容量為20

ArrayList：線程不安全，查詢速度快

底層資料結構是數組結構

擴容增量：原容量的 0.5倍+1

如 ArrayList的容量為10，一次擴容後是容量為16

Set(集) 元素無序的、不可重複。

HashSet：線程不安全，存取速度快

底層實作是一個HashMap（儲存資料），實作Set接口

預設初始容量為16（為何是16，見下方對HashMap的描述）

加載因子為0.75：即當 元素個數 超過 容量長度的0.75倍 時，進行擴容

擴容增量：原容量的 1 倍

如 HashSet的容量為16，一次擴容後是容量為32

Map是一個雙列集合

HashMap：預設初始容量為16,長度始終保持2的n次方

（為何是16：16是2^4，可以提高查詢效率，另外，32=16<<1 -->至于詳細的原因可另行分析，或分析源代碼）

加載因子為0.75：即當 元素個數 超過 容量長度的0.75倍 時，進行擴容

擴容增量：原容量的 1 倍

如 HashMap的容量為16，一次擴容後是容量為32

HashTable：預設初始容量為11

線程安全，但是速度慢，不允許key/value為null

加載因子為0.75：即當 元素個數 超過 容量長度的0.75倍 時，進行擴容

擴容增量：2*原數組長度+1

如 HashTable的容量為11，一次擴容後是容量為23

Hashtable 和 HashMap 做為 Map 的基本特性

兩者都實作了Map接口，基本特性相同

對同一個Key，隻會有一個對應的value值存在

如何算是同一個Key？ 首先，兩個key對象的hash值相同，其次，key對象的equals方法傳回真

内部資料結構

Hashtable和HashMap的内部資料結構相似

其基本内部資料結構是一個Entry數組 (transient Entry[] table)

數組元素為實作Map.Entry<K,V>接口的類，Hashtable和HashMap各自實作了自己的Entry類。

Entry包含一個Key-value對，以及一個next指針指向另一個Entry。多個Entry可以組成一個單向連結清單。

常用操作（JDK1.8中的有樹化過程，操作步驟不同）

資料插入操作： put(key,value)

根據Key的hash值計算出該Entry所應存放的位置（數組下标）

若該數組元素為空，直接放置Entry到此處

若多個不同的Key所計算得到的數組下标相同，新加入的Key-value對（Entry）會被加入到Entry單向連結清單中。Hashtable和HashMap都是将其插傳入連結表首部.

若已經有相同的Key存在于這個連結清單中，則，新的value值會取代老的value

當Map中存放的Entry數量超過其限制（ 數組長度 * 負荷因子）時，Map将自動重新調整數組大小并重新對Entry進行散列

資料查找：get(key)

根據Key的hash值計算出該Entry對所應存放的位置（數組下标）

得到該位置的第一個Entry對象，比較key和Entry.key，若hash值相同，并且equals為真，則該Entry是我們要找的Key-value對，否則繼續沿next指針構成的單向連結清單查找

資料移除：remove(key)

按照上述資料查找的方式找到key所在的Entry對象，将其移除，并保持Entry單向連結清單的連通性

Hashtable 和 HashMap 的比較

Hashtable HashMap

并發操作 使用同步機制， 沒有同步機制，需要使用者自己進行并發通路控制

實際應用程式中，僅僅是Hashtable本身的同步并不能保證程式在并發操作下的正确性，需要高層次的并發保護。

下面的代碼試圖在key所對應的value值等于x的情況下修改value為x+1

{
 value = hashTable.get(key);
   if(value.intValue()== x){
    hashTable.put(key,      
    new Integer(value.intValue()+1));
  }
}
           

如2個線程同時執行以上代碼，可能放入不是x+1，而是x+2.

資料周遊的方式 Iterator 和 Enumeration Iterator

是否支援fast-fail 用Iterator周遊，支援fast-fail 支援fast-fail

用Enumeration不支援fast-fail.

是否接受值為null的Key 或Value？ 不接受 接受

根據hash值計算數組下标的算法 當數組長度較小，并且Key的hash值低位數值分散不均勻時，不同的hash值計算得到相同下标值的幾率較高 優于hashtable，通過對Key的hash做移位運算和位的與運算，使其能更廣泛地分散到數組的不同位置

hash = key.hashCode();	hash = hash (k);
index=(hash&0x7FFFFFFF) % tab.length;	
index = indexFor(hash, table.length);
	 
	static int hash(Object x) {
	 int h = x.hashCode();
	h += ~(h << 9);
	 h ^= (h >>> 14);
	  h += (h << 4);
	 h ^= (h >>> 10);
	 return h;
	}
	static int indexFor(int h, int length) {
	return h & (length-1);
	}
           

Entry數組的長度 Ø 預設初始長度為11， Ø 預設初始長度為16，

Ø 初始化時可以指定initial capacity Ø 長度始終保持2的n次方

Ø 初始化時可以指定initial capacity，若不是2的次方，HashMap将選取第一個大于initial capacity 的2n次方值作為其初始長度

LoadFactor負荷因子 0.75

負荷超過（loadFactor * 數組長度）時，内部資料的調整方式 擴充數組：2*原數組長度+1 擴充數組： 原數組長度 * 2

兩者都會重新根據Key的hash值計算其在數組中的新位置，重新放置。算法相似，時間、空間效率相同

一般情況下，HashMap能夠比Hashtable工作的更好、更快，主要得益于它的雜湊演算法，以及沒有同步。應用程式一般在更高的層面上實 現了保護機制，而不是依賴于這些底層資料結構的同步，是以，HashMap能夠在大多應用中滿足需要。推薦使用HashMap，如果需要同步，可以使用同 步工具類将其轉換成支援同步的HashMap。

Map的效率

Map的效率與Entry數組大小及負荷因子的選取有密切關系。選取适當的數組大小有利于Key-value對的散列分布，并且，如果數組足夠 大，将有效的減少重新調整數組的次數，提高效率。較小的負荷因子将占用更多的空間，但降低沖突的可能性，進而将加快通路和更新的速度。

另外，Key的hash值本身如果能保證較好的散列性，也有益于提高Map的讀寫效率。在effective java中，對hash()的重載有好的建議。

關于如何提高Map的執行效率，可參考《Java Map 集合類簡介》http://www.oracle.com/technology/global/cn/pub/articles/maps1.html 。

辨析

“Hashtable和HashMap的差別主要是前者是同步的，後者是快速失敗機制保證不會出現多線程并發錯誤（Fast-Fail）。”，這是一個被很多文章轉載過的概念，但其描述并不準确，容易引起誤會。

實質上，Fast-fail與同步保護的是兩種不同情況下的并發，兩者不能拿來做比較。

Hashtable是同步的，在執行get,put,remove,size,clear等一次性讀寫操作時，使用了同步機制，避免了多個線程 同時讀寫Hashtable。但同步機制并不能避免在iterator或Enumeration周遊過程中其他線程對Hashtable的put、 remove、clear操作，這些寫操作都會被毫無阻攔得成功執行。

快速失敗機制主要目的在于使iterator周遊數組的線程能及時發現其他線程對Map的修改（如put、remove、clear等），因 此，fast-fail并不能保證所有情況下的多線程并發錯誤，隻能保護iterator周遊過程中的iterator.next()與寫并發.

其次，Hashtable的iterator周遊方式也是支援fast-fail的，不能說它沒有快速失敗機制。寫一個簡單的例程就可以證明這 一點，一個線程做iterator周遊，另一個線程向hashtable中put新的key和value，很容易就會觀察到fast-fail 機制報告ConcurrentModificationException

來自 http://www.cnblogs.com/xiaoming0601/p/5864022.html