HashMap
HashMap是基于哈希表實作的，每一個元素是一個key-value對，其内部通過單連結清單解決沖突問題，容量不足（超過了閥值）時，同樣會自動增長。
HashMap是非線程安全的，隻是用于單線程環境下，多線程環境下可以采用concurrent并發包下的concurrentHashMap。
HashMap 實作了Serializable接口，是以它支援序列化，實作了Cloneable接口，能被克隆。
HashMap存資料的過程是：
HashMap内部維護了一個存儲資料的Entry數組，HashMap采用連結清單解決沖突，每一個Entry本質上是一個單向連結清單。當準備添加一個key-value對時，首先通過hash(key)方法計算hash值，然後通過indexFor(hash,length)求該key-value對的存儲位置，計算方法是先用hash&0x7FFFFFFF後，再對length取模，這就保證每一個key-value對都能存入HashMap中，當計算出的位置相同時，由于存入位置是一個連結清單，則把這個key-value對插傳入連結表頭。
HashMap中key和value都允許為null。key為null的鍵值對永遠都放在以table[0]為頭結點的連結清單中。
HashMap的存儲結構，如下圖所示：
HashMap共有四個構造方法。構造方法中提到了兩個很重要的參數：初始容量和加載因子。這兩個參數是影響HashMap性能的重要參數，其中容量表示哈希表中槽的數量（即哈希數組的長度），初始容量是建立哈希表時的容量（從構造函數中可以看出，如果不指明，則預設為16），加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，當哈希表中的條目數超出了加載因子與目前容量的乘積時，則要對該哈希表進行 resize 操作（即擴容）。
下面說下加載因子，如果加載因子越大，對空間的利用更充分，但是查找效率會降低（連結清單長度會越來越長）；如果加載因子太小，那麼表中的資料将過于稀疏（很多空間還沒用，就開始擴容了），對空間造成嚴重浪費。如果我們在構造方法中不指定，則系統預設加載因子為0.75，這是一個比較理想的值，一般情況下我們是無需修改的。
HashMap的初始值還要考慮加載因子:
- 哈希沖突：若幹Key的哈希值按數組大小取模後，如果落在同一個數組下标上，将組成一條Entry鍊，對Key的查找需要周遊Entry鍊上的每個元素執行equals()比較。
- 加載因子：為了降低哈希沖突的機率，預設當HashMap中的鍵值對達到數組大小的75%時，即會觸發擴容。是以，如果預估容量是100，即需要設定100/0.75＝134的數組大小。
- 空間換時間：如果希望加快Key查找的時間，還可以進一步降低加載因子，加大初始大小，以降低哈希沖突的機率。
HashMap總結
底層數組+連結清單實作，可以存儲null鍵和null值，線程不安全
初始size為16，擴容：newsize = oldsize*2，size一定為2的n次幂
擴容針對整個Map，每次擴容時，原來數組中的元素依次重新計算存放位置，并重新插入
插入元素後才判斷該不該擴容，有可能無效擴容（插入後如果擴容，如果沒有再次插入，就會産生無效擴容）
當Map中元素總數超過Entry數組的75%，觸發擴容操作，為了減少連結清單長度，元素配置設定更均勻
計算index方法：index = hash & (tab.length – 1)
HashTable
Hashtable同樣是基于哈希表實作的，同樣每個元素是一個key-value對，其内部也是通過單連結清單解決沖突問題，容量不足（超過了閥值）時，同樣會自動增長。
Hashtable也是JDK1.0引入的類，是線程安全的，能用于多線程環境中。
Hashtable同樣實作了Serializable接口，它支援序列化，實作了Cloneable接口，能被克隆
總結
底層數組+連結清單實作，無論key還是value都不能為null，線程安全，實作線程安全的方式是在修改資料時鎖住整個HashTable，效率低，ConcurrentHashMap做了相關優化
初始size為11，擴容：newsize = olesize*2+1
計算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
HashTable和HashMap差別
1.繼承的父類不同
Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類。但二者都實作了Map接口。
2.線程的安全性不同
javadoc中關于hashmap的一段描述如下：此實作不是同步的。如果多個線程同時通路一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。
Hashtable 中的方法是Synchronize的，而HashMap中的方法在預設情況下是非Synchronize的。在多線程并發的環境下，可以直接使用Hashtable，不需要自己為它的方法實作同步，但使用HashMap時就必須要自己增加同步處理。（結構上的修改是指添加或删除一個或多個映射關系的任何操作；僅改變與執行個體已經包含的鍵關聯的值不是結構上的修改。）這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在建立時完成這一操作，以防止對映射進行意外的非同步通路，如下所示：
Map m = Collections.synchronizedMap(new HashMap(…));
Hashtable 線程安全很好了解，因為它每個方法中都加入了Synchronize。這裡我們分析一下HashMap為什麼是線程不安全的：
HashMap底層是一個Entry數組，當發生hash沖突的時候，hashmap是采用連結清單的方式來解決的，在對應的數組位置存放連結清單的頭結點。對連結清單而言，新加入的節點會從頭結點加入。
我們來分析一下多線程通路：
（1）在hashmap做put操作的時候會調用下面方法：
//新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
void addEntry(int hash, K key, V value, int bucketIndex) {
// 儲存“bucketIndex”位置的值到“e”中
Entry<K,V> e = table[bucketIndex];
// 設定“bucketIndex”位置的元素為“新Entry”，
// 設定“e”為“新Entry的下一個節點”
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 若HashMap的實際大小 不小于 “門檻值”，則調整HashMap的大小
if (size++ >= threshold)
resize(2 * table.length);
}
在hashmap做put操作的時候會調用到以上的方法。現在假如A線程和B線程同時對同一個數組位置調用addEntry，兩個線程會同時得到現在的頭結點，然後A寫入新的頭結點之後，B也寫入新的頭結點，那B的寫入操作就會覆寫A的寫入操作造成A的寫入操作丢失。
（2）删除鍵值對的代碼
<span style="font-size: 18px;"> </span>// 删除“鍵為key”的元素
final Entry<K,V> removeEntryForKey(Object key) {
// 擷取哈希值。若key為null，則哈希值為0；否則調用hash()進行計算
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 删除連結清單中“鍵為key”的元素
// 本質是“删除單向連結清單中的節點”
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
當多個線程同時操作同一個數組位置的時候，也都會先取得現在狀态下該位置存儲的頭結點，然後各自去進行計算操作，之後再把結果寫會到該數組位置去，其實寫回的時候可能其他的線程已經就把這個位置給修改過了，就會覆寫其他線程的修改。
（3）addEntry中當加入新的鍵值對後鍵值對總數量超過門限值的時候會調用一個resize操作，代碼如下：
// 重新調整HashMap的大小，newCapacity是調整後的容量
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果就容量已經達到了最大值，則不能再擴容，直接傳回
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 建立一個HashMap，将“舊HashMap”的全部元素添加到“新HashMap”中，
// 然後，将“新HashMap”指派給“舊HashMap”。
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
這個操作會新生成一個新的容量的數組，然後對原數組的所有鍵值對重新進行計算和寫入新的數組，之後指向新生成的數組。
當多個線程同時檢測到總數量超過門限值的時候就會同時調用resize操作，各自生成新的數組并rehash後賦給該map底層的數組table，結果最終隻有最後一個線程生成的新數組被賦給table變量，其他線程的均會丢失。而且當某些線程已經完成指派而其他線程剛開始的時候，就會用已經被指派的table作為原始數組，這樣也會有問題。
3、是否提供contains方法
HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因為contains方法容易讓人引起誤解。
Hashtable則保留了contains，containsValue和containsKey三個方法，其中contains和containsValue功能相同。
4、key和value是否允許null值
其中key和value都是對象，并且不能包含重複key，但可以包含重複的value。
通過上面的ContainsKey方法和ContainsValue的源碼我們可以很明顯的看出：
Hashtable中，key和value都不允許出現null值。但是如果在Hashtable中有類似put(null,null)的操作，編譯同樣可以通過**，因為key和value都是Object類型**，但運作時會抛出NullPointerException異常，這是JDK的規範規定的。
HashMap中，null可以作為鍵，這樣的鍵隻有一個；可以有一個或多個鍵所對應的值為null。當get()方法傳回null值時，可能是 HashMap中沒有該鍵，也可能使該鍵所對應的值為null。是以，在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵， 而應該用containsKey()方法來判斷。
5、兩個周遊方式的内部實作上不同
Hashtable、HashMap都使用了 Iterator。而由于曆史原因，Hashtable還使用了Enumeration的方式 。
6、hash值不同
哈希值的使用不同，HashTable直接使用對象的hashCode。而HashMap重新計算hash值。
hashCode是jdk根據對象的位址或者字元串或者數字算出來的int類型的數值。
Hashtable計算hash值，直接用key的hashCode()，而HashMap重新計算了key的hash值，Hashtable在求hash值對應的位置索引時，用取模運算，而HashMap在求位置索引時，則用與運算，且這裡一般先用hash&0x7FFFFFFF後，再對length取模，&0x7FFFFFFF的目的是為了将負的hash值轉化為正值，因為hash值有可能為負數 ，而&0x7FFFFFFF後，隻有符号外改變，而後面的位都不變。
7、内部實作使用的數組初始化和擴容方式不同
HashTable在不指定容量的情況下的預設容量為11，而HashMap為16，Hashtable不要求底層數組的容量一定要為2的整數次幂，而HashMap則要求一定為2的整數次幂。
Hashtable擴容時，将容量變為原來的2倍加1，而HashMap擴容時，将容量變為原來的2倍。
Hashtable和HashMap它們兩個内部實作方式的數組的初始大小和擴容的方式。HashTable中hash數組預設大小是11，增加的方式是 old*2+1。
8、Hashtable與HashMap的疊代器不同
HashMap的疊代器（Iterator）是fail-fast疊代器，而Hashtable的enumerator疊代器不是fail-fast的。是以當有其它線程改變了HashMap的結構（增加或者移除元素），将會抛出ConcurrentModificationException，但疊代器本身的remove()方法移除元素則不會抛出ConcurrentModificationException異常。但這并不是一個一定發生的行為，要看JVM。
ConcurrentHashMap
從類圖中可以看出來在存儲結構中ConcurrentHashMap比HashMap多出了一個類Segment，而Segment是一個可重入鎖。
ConcurrentHashMap是使用了鎖分段技術來保證線程安全的。
鎖分段技術：首先将資料分成一段一段的存儲，然後給每一段資料配一把鎖，當一個線程占用鎖通路其中一個段資料的時候，其他段的資料也能被其他線程通路。
ConcurrentHashMap提供了與Hashtable和SynchronizedMap不同的鎖機制。Hashtable中采用的鎖機制是一次鎖住整個hash表，進而在同一時刻隻能由一個線程對其進行操作；而ConcurrentHashMap中則是一次鎖住一個桶。
ConcurrentHashMap預設将hash表分為16個桶，諸如get、put、remove等常用操作隻鎖住目前需要用到的桶。這樣，原來隻能一個線程進入，現在卻能同時有16個寫線程執行，并發性能的提升是顯而易見的。
ConcurrentHashMap的總結
- 底層采用分段的數組+連結清單實作，線程安全
- 通過把整個Map分為N個Segment，可以提供相同的線程安全，但是效率提升N倍，預設提升16倍。(讀操作不加鎖，由于HashEntry的value變量是 volatile的，也能保證讀取到最新的值。)
- Hashtable的synchronized是針對整張Hash表的，即每次鎖住整張表讓線程獨占，ConcurrentHashMap允許多個修改操作并發進行，其關鍵在于使用了鎖分離技術
- 有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢後，又按順序釋放所有段的鎖
- 擴容：段内擴容（段内元素超過該段對應Entry數組長度的75%觸發擴容，不會對整個Map進行擴容），插入前檢測需不需要擴容，有效避免無效擴容