摘要：線程安全關(guān)于線程安全，我們想要知道的是在什么情況下會(huì)發(fā)生線程不安全的情況實(shí)際上，在上文分析方法時(shí)，當(dāng)?shù)娜萘砍^了時(shí)，便執(zhí)行操作，就存在線程不安全的問題。實(shí)現(xiàn)了所謂的線程安全，在很多方法上都加上了。
HashMap簡(jiǎn)介
本文針對(duì)HashMap的源碼分析基于JDK 7，JDK 8在HashMap的實(shí)現(xiàn)上有著較大幅度的改進(jìn)和優(yōu)化，這部分優(yōu)化我將另起一篇來闡述。另外，本文僅分析HashMap眾多方法中最常用的方法，其余方法有需要時(shí)再研究 。
HashMap的繼承關(guān)系如下。
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable
HashMap繼承自AbstractMap，同時(shí)實(shí)現(xiàn)了Map、Cloneable和Serializable接口。因此，HashMap可以被克隆，并支持序列化。另外，HashMap是一個(gè)非線程安全的，因此適合運(yùn)用在單線程環(huán)境下。如果是在多線程環(huán)境，可以通過Collections的靜態(tài)方法synchronizedMap獲得線程安全的HashMap，如下代碼所示。
Map map = Collections.synchronizedMap(new HashMap());
存儲(chǔ)結(jié)構(gòu)
針對(duì)每個(gè)鍵值對(duì)，HashMap使用內(nèi)部類Entry來存儲(chǔ)，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底層的存儲(chǔ)結(jié)構(gòu)是基于數(shù)組和鏈表實(shí)現(xiàn)的。對(duì)于每一個(gè)要存入HashMap的鍵值對(duì)（Key-Value Pair），通過計(jì)算Key的hash值來決定存入哪個(gè)數(shù)組單元（bucket），為了處理hash沖突，每個(gè)數(shù)組單元實(shí)際上是一條Entry單鏈表的頭結(jié)點(diǎn)，其后引申出一條單鏈表。HashMap的存儲(chǔ)結(jié)構(gòu)如下圖所示。
關(guān)鍵屬性
HashMap定義了幾個(gè)關(guān)鍵屬性，對(duì)應(yīng)的源碼如下。
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）的默認(rèn)容量，且該容量必須為2的冪，具體原因會(huì)在下文解釋。
MAXIMUM_CAPACITY代表HashMap槽（bucket）的最大容量，如果傳入的容量大于1 << 30，那么實(shí)際容量會(huì)被MAXIMUM_CAPACITY替換。
DEFAULT_LOAD_FACTOR是默認(rèn)的加載因子，用于計(jì)算HashMap擴(kuò)容的threshold，當(dāng)HashMap的實(shí)際元素容量達(dá)到總?cè)萘康?b>threshold時(shí)，對(duì)HashMap進(jìn)行擴(kuò)容。
table是存儲(chǔ)Entry的數(shù)組，每個(gè)Entry是一條單鏈表的頭結(jié)點(diǎn)。
size代表HashMap鍵值對(duì)的數(shù)量。
threshold是HashMap決定是否執(zhí)行執(zhí)行擴(kuò)容操作的閾值，threshold = capacity * load factor。
loadFactor表示HashMap實(shí)際加載因子，通過構(gòu)造方法傳入。若未指定，loadFactor等于DEFAULT_LOAD_FACTOR。
需要進(jìn)一步解釋的是loadFactor屬性，loadFactor描述了HashMap發(fā)生擴(kuò)容時(shí)的填充程度。如果loadFactor設(shè)置過大，意味著在HashMap擴(kuò)容前發(fā)生hash沖突的機(jī)會(huì)越大，因此單鏈表的長(zhǎng)度也就會(huì)越長(zhǎng)，那么在執(zhí)行查找操作時(shí)，會(huì)由于單鏈表長(zhǎng)度過長(zhǎng)導(dǎo)致查找的效率降低。如果loadFactor設(shè)置過小，那么HashMap的空間利用率會(huì)降低，導(dǎo)致HashMap在很多空間都沒有被利用的情況下便開始擴(kuò)容。
構(gòu)造方法
HashMap定義了四個(gè)構(gòu)造方法，源碼如下。
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方法體不執(zhí)行任何操作。
}
public HashMap(Map m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
當(dāng)調(diào)用HashMap默認(rèn)構(gòu)造方法時(shí)，HashMap對(duì)象的屬性均會(huì)被設(shè)置為默認(rèn)值，包括設(shè)置加載因子（DEFAULT_LOAD_FACTOR）、擴(kuò)容閾值（threshold）和table的初始大小。
如果在創(chuàng)建HashMap對(duì)象時(shí)指定了bucket容量initialCapacity，通過源碼我們可以看出在初始化對(duì)象時(shí)不一定會(huì)直接使用initialCapacity，而是選取滿足小于等于initialCapacity前提條件下最大的且是2的冪的一個(gè)值作為實(shí)際bucket的大小。
如果向構(gòu)造方法傳遞的參數(shù)是一個(gè)Map對(duì)象m，那么putAllForCreate方法會(huì)重新散列m中的每個(gè)元素，將它們存入相應(yīng)的bucket中。putAllForCreate方法及其調(diào)用的相關(guān)方法如下。
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方法遍歷每一個(gè)鍵值對(duì)e，通過putForCreat方法將e散列到對(duì)應(yīng)的bucket中。putForCreate方法調(diào)用indexFor來確定鍵值對(duì)散列的bucket的位置。indexFor通過h & (length-1)返回bucket的位置，接著遍歷對(duì)應(yīng)的單鏈表來決定是更新操作還是插入操作。
我們需要關(guān)注的地方是indexFor為什么通過計(jì)算h & (length-1)來獲得bucket的位置，而不是通過計(jì)算h % length？
實(shí)際上，在HashMap中，h & (length-1) == h % length，但是需要一個(gè)前提：length必須滿足是2的冪。這也正是在解釋DEFAULT_INITIAL_CAPACITY和HashMap構(gòu)造方法時(shí)強(qiáng)調(diào)的HashMap的bucket容量必須是2的冪。當(dāng)length是2的冪，那么length的二進(jìn)制數(shù)可以表示為1000...000，因此length - 1的二進(jìn)制數(shù)為0111...111，當(dāng)h與length - 1位與時(shí)，除了h的最高位的被修改為0，其余位均保持不變，這也正是實(shí)現(xiàn)了h % length的效果。只是相比于h % length，h & (length-1)的效率會(huì)更高。
HashMap的bucket容量必須為2的冪的另一個(gè)重要原因是一旦滿足此條件，那么length即為偶數(shù)，length - 1便為奇數(shù)，所以length - 1的最后一位必為1。因此，h & (length - 1)得到的值既可能是奇數(shù)，也可能是偶數(shù)，這確保了散列的均勻性。如果length - 1是偶數(shù)，那么h & (length - 1)得到的值必為偶數(shù)，那么HashMap的空間便浪費(fèi)了一半。
存取方法
我們分析HashMap使用頻率最高的兩個(gè)方法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元素時(shí)，先計(jì)算Key的hash值，定位到數(shù)組中對(duì)應(yīng)的bucket，然后開始遍歷Entry單鏈表，直到找到需要的元素，否則返回null。
當(dāng)我們向HashMap中put新的鍵值對(duì)時(shí)，HashMap首先檢查Key是否等于null，若為null，則執(zhí)行putForNullKey方法，putForNullKey方法對(duì)應(yīng)的源碼如下。
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，那么就將該鍵值對(duì)添加到table[0]的位置，同時(shí)，遍歷table[0]處的單鏈表并將鏈表中所有節(jié)點(diǎn)的值都覆蓋為新傳遞進(jìn)來的鍵值對(duì)的值。因此，該位置永遠(yuǎn)只有一個(gè)值。
如果Key不等于null，那么通過indexFor定位到bucket，然后遍歷單鏈表，如果存在Key相等的鍵值對(duì)，就用新值覆蓋舊值，并返回舊值。如果在單鏈表中沒有找到對(duì)應(yīng)的Key，那么調(diào)用addEntry方法創(chuàng)建新的Entry節(jié)點(diǎn)至單鏈表（作為頭節(jié)點(diǎn)）。addEntry及關(guān)聯(lián)方法源碼如下。
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);
}
}
}
當(dāng)addEntry把新增鍵值對(duì)插入單鏈表后，會(huì)判斷是否需要擴(kuò)容，即判斷當(dāng)前HashMap的元素的個(gè)數(shù)是否大于threshold。若需要擴(kuò)容，那么調(diào)用resize方法進(jìn)行2倍擴(kuò)容。resize方法會(huì)在內(nèi)部調(diào)用transfer方法，transfer方法遍歷舊數(shù)組及單鏈表，并將每個(gè)鍵值對(duì)重新散列，可以意識(shí)到，這整個(gè)rehash的開銷相當(dāng)大。
線程安全
關(guān)于線程安全，我們想要知道的是HashMap在什么情況下會(huì)發(fā)生線程不安全的情況？實(shí)際上，在上文分析put方法時(shí)，當(dāng)HashMap的容量超過了threshold時(shí)，便執(zhí)行resize操作，resize就存在線程不安全的問題。
關(guān)于resize哪兒不安全，我推薦左耳朵耗子寫的疫苗：Java HashMap的死循環(huán)，這篇文章圖文并茂的解釋了在rehash過程中出現(xiàn)線程不安全問題的根源。
HashMap VS HashTable
HashTable和HashMap底層采用相同的存儲(chǔ)結(jié)構(gòu)，在很多方法的實(shí)現(xiàn)上二者的思路基本一致。最主要的區(qū)別主要有兩點(diǎn)。
HashTable實(shí)現(xiàn)了所謂的線程安全，在HashTable很多方法上都加上了synchronized。
在HashMap的分析中，我們發(fā)現(xiàn)當(dāng)我們新增鍵值對(duì)時(shí)，HashMap是允許Key和Value均為null。但是HashTable不允許Key或Value為null，關(guān)于這一點(diǎn)我們可以通過查看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;
}
