摘要：線程安全關于線程安全，我們想要知道的是在什么情況下會發生線程不安全的情況實際上，在上文分析方法時，當的容量超過了時，便執行操作，就存在線程不安全的問題。實現了所謂的線程安全，在很多方法上都加上了。
HashMap簡介
本文針對HashMap的源碼分析基于JDK 7，JDK 8在HashMap的實現上有著較大幅度的改進和優化，這部分優化我將另起一篇來闡述。另外，本文僅分析HashMap眾多方法中最常用的方法，其余方法有需要時再研究 。
HashMap的繼承關系如下。
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable
HashMap繼承自AbstractMap，同時實現了Map、Cloneable和Serializable接口。因此，HashMap可以被克隆，并支持序列化。另外，HashMap是一個非線程安全的，因此適合運用在單線程環境下。如果是在多線程環境，可以通過Collections的靜態方法synchronizedMap獲得線程安全的HashMap，如下代碼所示。
Map map = Collections.synchronizedMap(new HashMap());
存儲結構
針對每個鍵值對，HashMap使用內部類Entry來存儲，Entry核心代碼如下。
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
final int hash;
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
}
從整體上看，HashMap底層的存儲結構是基于數組和鏈表實現的。對于每一個要存入HashMap的鍵值對（Key-Value Pair），通過計算Key的hash值來決定存入哪個數組單元（bucket），為了處理hash沖突，每個數組單元實際上是一條Entry單鏈表的頭結點，其后引申出一條單鏈表。HashMap的存儲結構如下圖所示。
關鍵屬性
HashMap定義了幾個關鍵屬性，對應的源碼如下。
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
DEFAULT_INITIAL_CAPACITY代表HashMap槽（bucket）的默認容量，且該容量必須為2的冪，具體原因會在下文解釋。
MAXIMUM_CAPACITY代表HashMap槽（bucket）的最大容量，如果傳入的容量大于1 << 30，那么實際容量會被MAXIMUM_CAPACITY替換。
DEFAULT_LOAD_FACTOR是默認的加載因子，用于計算HashMap擴容的threshold，當HashMap的實際元素容量達到總容量的threshold時，對HashMap進行擴容。
table是存儲Entry的數組，每個Entry是一條單鏈表的頭結點。
size代表HashMap鍵值對的數量。
threshold是HashMap決定是否執行執行擴容操作的閾值，threshold = capacity * load factor。
loadFactor表示HashMap實際加載因子，通過構造方法傳入。若未指定，loadFactor等于DEFAULT_LOAD_FACTOR。
需要進一步解釋的是loadFactor屬性，loadFactor描述了HashMap發生擴容時的填充程度。如果loadFactor設置過大，意味著在HashMap擴容前發生hash沖突的機會越大，因此單鏈表的長度也就會越長，那么在執行查找操作時，會由于單鏈表長度過長導致查找的效率降低。如果loadFactor設置過小，那么HashMap的空間利用率會降低，導致HashMap在很多空間都沒有被利用的情況下便開始擴容。
構造方法
HashMap定義了四個構造方法，源碼如下。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init(); // 在源碼中，init方法體不執行任何操作。
}
public HashMap(Map m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
當調用HashMap默認構造方法時，HashMap對象的屬性均會被設置為默認值，包括設置加載因子（DEFAULT_LOAD_FACTOR）、擴容閾值（threshold）和table的初始大小。
如果在創建HashMap對象時指定了bucket容量initialCapacity，通過源碼我們可以看出在初始化對象時不一定會直接使用initialCapacity，而是選取滿足小于等于initialCapacity前提條件下最大的且是2的冪的一個值作為實際bucket的大小。
如果向構造方法傳遞的參數是一個Map對象m，那么putAllForCreate方法會重新散列m中的每個元素，將它們存入相應的bucket中。putAllForCreate方法及其調用的相關方法如下。
private void putForCreate(K key, V value) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
createEntry(hash, key, value, i);
}
private void putAllForCreate(Map m) {
for (Map.Entry e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
static int indexFor(int h, int length) {
return h & (length-1);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
putAllForCreate方法遍歷每一個鍵值對e，通過putForCreat方法將e散列到對應的bucket中。putForCreate方法調用indexFor來確定鍵值對散列的bucket的位置。indexFor通過h & (length-1)返回bucket的位置，接著遍歷對應的單鏈表來決定是更新操作還是插入操作。
我們需要關注的地方是indexFor為什么通過計算h & (length-1)來獲得bucket的位置，而不是通過計算h % length？
實際上，在HashMap中，h & (length-1) == h % length，但是需要一個前提：length必須滿足是2的冪。這也正是在解釋DEFAULT_INITIAL_CAPACITY和HashMap構造方法時強調的HashMap的bucket容量必須是2的冪。當length是2的冪，那么length的二進制數可以表示為1000...000，因此length - 1的二進制數為0111...111，當h與length - 1位與時，除了h的最高位的被修改為0，其余位均保持不變，這也正是實現了h % length的效果。只是相比于h % length，h & (length-1)的效率會更高。
HashMap的bucket容量必須為2的冪的另一個重要原因是一旦滿足此條件，那么length即為偶數，length - 1便為奇數，所以length - 1的最后一位必為1。因此，h & (length - 1)得到的值既可能是奇數，也可能是偶數，這確保了散列的均勻性。如果length - 1是偶數，那么h & (length - 1)得到的值必為偶數，那么HashMap的空間便浪費了一半。
存取方法
我們分析HashMap使用頻率最高的兩個方法get方法和put方法，源碼如下。
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
從HashMap獲取get元素時，先計算Key的hash值，定位到數組中對應的bucket，然后開始遍歷Entry單鏈表，直到找到需要的元素，否則返回null。
當我們向HashMap中put新的鍵值對時，HashMap首先檢查Key是否等于null，若為null，則執行putForNullKey方法，putForNullKey方法對應的源碼如下。
private V putForNullKey(V value) {
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); // 不做任何操作
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
如果Key等于null，那么就將該鍵值對添加到table[0]的位置，同時，遍歷table[0]處的單鏈表并將鏈表中所有節點的值都覆蓋為新傳遞進來的鍵值對的值。因此，該位置永遠只有一個值。
如果Key不等于null，那么通過indexFor定位到bucket，然后遍歷單鏈表，如果存在Key相等的鍵值對，就用新值覆蓋舊值，并返回舊值。如果在單鏈表中沒有找到對應的Key，那么調用addEntry方法創建新的Entry節點至單鏈表（作為頭節點）。addEntry及關聯方法源碼如下。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
當addEntry把新增鍵值對插入單鏈表后，會判斷是否需要擴容，即判斷當前HashMap的元素的個數是否大于threshold。若需要擴容，那么調用resize方法進行2倍擴容。resize方法會在內部調用transfer方法，transfer方法遍歷舊數組及單鏈表，并將每個鍵值對重新散列，可以意識到，這整個rehash的開銷相當大。
線程安全
關于線程安全，我們想要知道的是HashMap在什么情況下會發生線程不安全的情況？實際上，在上文分析put方法時，當HashMap的容量超過了threshold時，便執行resize操作，resize就存在線程不安全的問題。
關于resize哪兒不安全，我推薦左耳朵耗子寫的疫苗：Java HashMap的死循環，這篇文章圖文并茂的解釋了在rehash過程中出現線程不安全問題的根源。
HashMap VS HashTable
HashTable和HashMap底層采用相同的存儲結構，在很多方法的實現上二者的思路基本一致。最主要的區別主要有兩點。
HashTable實現了所謂的線程安全，在HashTable很多方法上都加上了synchronized。
在HashMap的分析中，我們發現當我們新增鍵值對時，HashMap是允許Key和Value均為null。但是HashTable不允許Key或Value為null，關于這一點我們可以通過查看HashTable源碼得知。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) { // 若value為空則拋出NullPointerException。
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode(); // 若key為空則拋出NullPointerException。
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry entry = (Entry)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
