前面我們已經分析了ArrayList和LinkedList這兩個集合
我們知道ArrayList是基于數組實作的，LinkedList是基于連結清單實作的。
它們各自有自己的優劣勢，例如ArrayList在定位查找元素時會優于LinkedList，而LinkedList在添加删除元素時會優于ArrayList。
而本篇介紹的HashMap綜合了二者的優勢，它的底層是基于哈希表實作的（數組+連結清單），如果不考慮哈希沖突的話，HashMap在增删改查操作上的時間複雜度都能夠達到驚人的O(1)。
我們先看看它所基于的哈希表的結構。
從上圖中可以看到，哈希表是由數組和連結清單共同構成的一種結構
當然上圖是一個不好的示例，一個好的哈希函數應該要盡量平均元素在數組中的分布，減少哈希沖突進而減小連結清單的長度。
連結清單的長度越長，意味着在查找時需要周遊的結點越多，哈希表的性能也就越差。
接下來我們來看下HashMap的部分成員變量。
//預設初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//預設最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//預設加載因子, 指哈希表可以達到多滿的尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空的哈希表
static final Entry<?,?>[] EMPTY_TABLE = {};
//實際使用的哈希表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//HashMap大小, 即HashMap存儲的鍵值對數量
transient int size;
//鍵值對的門檻值, 用于判斷是否需要擴增哈希表容量
int threshold;
//加載因子
final float loadFactor;
//修改次數, 用于fail-fast機制
transient int modCount;
//使用替代哈希的預設閥值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//随機的哈希種子, 有助于減少哈希碰撞的次數
transient int hashSeed = 0;
由成員變量中看到，HashMap預設的初始容量為16，預設的加載因子是0.75。而threshold是集合能夠存儲的鍵值對的閥值，預設是初始容量*加載因子，也就是16*0.75=12，當鍵值對要超過閥值時，意味着這時候的哈希表已處于飽和狀态，再繼續添加元素就會增加哈希沖突，進而使HashMap的性能下降。
這時會觸發自動擴容機制，以保證HashMap的性能。
我們還可以看到哈希表其實就是一個Entry數組，數組存放的每個Entry都是單向連結清單的頭結點。
這個Entry是HashMap的靜态内部類，來看看Entry的成員變量。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //鍵
V value; //值
Entry<K,V> next; //下一個Entry的引用
int hash; //哈希碼
... //省略下面代碼
}
一個Entry執行個體就是一個鍵值對，裡面包含了key和value，同時每個Entry執行個體還有一個指向下一個Entry執行個體的引用。
為了避免重複計算，每個Entry執行個體還存放了對應的Hash碼。
可以說Entry數組就是HashMap的核心，所有的操作都是針對這個數組來完成的。
由于HashMap源碼比較長，不可能面面俱到的介紹它的所有方法，是以我們隻抓住重點來進行介紹。
接下來我們将以問題為導向，針對下面幾個問題深入探究HashMap的内部機制。
1. HashMap在構造時做了哪些操作？
//構造器, 傳入初始化容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
}
//如果初始化容量大于最大容量, 就把它設為最大容量
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
//如果加載因子小于0或者加載因子不是浮點數, 則抛出異常
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
}
//設定加載因子
this.loadFactor = loadFactor;
//門檻值為初始化容量
threshold = initialCapacity;
init();
}
void init() {}
所有的構造器都會調用到這個構造器，在這個構造器中我們看到除了對參數做一些校驗之外，它就做了兩件事，設定加載因子為傳入的加載因子，設定閥值為傳入的初始化大小。而init方法是空的，啥也沒做。
注意，這時候并沒有根據傳入的初始化大小去建立一個Entry數組哦。
那在什麼時候再去建立數組呢？繼續往下看。
2. HashMap添加鍵值對時會進行什麼操作？
//放置key-value鍵值對到HashMap中
public V put(K key, V value) {
//如果哈希表沒有初始化就進行初始化
if (table == EMPTY_TABLE) {
//初始化哈希表
inflateTable(threshold);
}
if (key == null) {
return putForNullKey(value);
}
//計算key的hash碼
int hash = hash(key);
//根據hash碼定位在哈希表的位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果對應的key已經存在, 就替換它的value值, 并傳回原先的value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//如果沒有對應的key就添加Entry到HashMap中
addEntry(hash, key, value, i);
//添加成功傳回null
return null;
}
看到，在添加鍵值對時會先檢查哈希表是否是個空表，如果是空表就進行初始化。之後再進行後續操作，調用哈希函數計算傳入的key的Hash碼。根據hash碼定位到Entry數組的指定槽位，然後對該槽位的單向連結清單進行周遊，如果傳入的已經存在了就進行替換操作，否則就建立一個Entry添加到哈希表中。
3. 哈希表是怎樣初始化的？
//初始化哈希表, 會對哈希表容量進行膨脹, 因為有可能傳入的容量不是2的幂
private void inflateTable(int toSize) {
//哈希表容量必須是2的次幂
int capacity = roundUpToPowerOf2(toSize);
//設定閥值, 這裡一般是取capacity*loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//建立指定容量的哈希表
table = new Entry[capacity];
//初始化哈希種子
initHashSeedAsNeeded(capacity);
}
上面我們知道，在構造HashMap時不會建立Entry數組，而是在put操作時檢查目前哈希表是否是個空表，如果是空表就調用inflateTable方法進行初始化。上面貼出了這個方法的代碼，可以看到方法内部會重新計算Entry數組的容量，因為在構造HashMap時傳入的初始化大小可能不是2的幂，是以要将這個數轉換成2的幂再去根據新的容量建立Entry數組。初始化哈希表時再次重新設定閥值，閥值一般是capacity*loadFactor。此外，在初始化哈希表時還會去初始化哈希種子(hashSeed)，這個hashSeed用于優化哈希函數，預設為0是不使用替代雜湊演算法，但是也可以自己去設定hashSeed的值，以達到優化效果。具體下面會講到。
4. HashMap在什麼時候判斷是否要擴容，以及它是怎樣擴容的？
//添加Entry方法, 先判斷是否要擴容
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果HashMap的大小大于閥值并且哈希表對應槽位的值不為空
if ((size >= threshold) && (null != table[bucketIndex])) {
//因為HashMap的大小大于閥值, 表明即将發生哈希沖突, 是以進行擴容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//在這裡表明HashMap的大小沒有超過閥值, 是以不需要擴容
createEntry(hash, key, value, bucketIndex);
}
//對哈希表進行擴容
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, initHashSeedAsNeeded(newCapacity));
//将目前哈希表設定為新的哈希表
table = newTable;
//更新哈希表門檻值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
在調用put方法添加一個鍵值對時，如果集合中沒有存在的key就去調用addEntry方法建立一個Entry。看到上面貼出的addEntry代碼，在建立一個Entry之前會先判斷目前集合元素的大小是否超過了閥值，如果超過了閥值就調用resize進行擴容。傳入的新的容量是原來哈希表的兩倍，在resize方法内部會建立一個容量為原先的2倍的Entry數組。然後将舊的哈希表裡面的元素全部遷移到新的哈希表，其中可能會進行再哈希，根據initHashSeedAsNeeded方法計算的值來确定是否進行再哈希。完成哈希表的遷移之後，将目前哈希表替換為新的，最後再根據新的哈希表容量來重新計算HashMap的閥值。
5. 為什麼Entry數組的大小必須為2的幂？
//傳回哈希碼對應的數組下标
static int indexFor(int h, int length) {
return h & (length-1);
}
indexFor方法是根據hash碼來計算出在數組中對應的下标。我們可以看到在這個方法内部使用了與(&)操作符。與操作是對兩個操作數進行位運算，如果對應的兩個位都為1，結果才為1，否則為0。與操作經常會用于去除操作數的高位值，例如：01011010 & 00001111 = 00001010。我們繼續回到代碼中，看看h&(length-1)做了些什麼。
已知傳入的length是Entry數組的長度，我們知道數組下标是從0開始計算的，是以數組的最大下标為length-1。如果length為2的幂，那麼length-1的二進制位後面都為1。這時h&(length-1)的作用就是去掉了h的高位值，隻留下h的低位值來作為數組的下标。由此可以看到Entry數組的大小規定為2的幂就是為了能夠使用這個算法來确定數組的下标。
6. 哈希函數是怎樣計算Hash碼的？
//生成hash碼的函數
final int hash(Object k) {
int h = hashSeed;
//key是String類型的就使用另外的雜湊演算法
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
//擾動函數
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
hash方法的最後兩行是真正計算hash值的算法，計算hash碼的算法被稱為擾動函數，所謂的擾動函數就是把所有東西雜糅到一起，可以看到這裡使用了四個向右移位運算。目的就是将h的高位值與低位值混合一下，以此增加低位值的随機性。在上面我們知道定位數組的下标是根據hash碼的低位值來确定的。key的hash碼是通過hashCode方法來生成的，而一個糟糕的hashCode方法生成的hash碼的低位值可能會有很大的重複。為了使得hash碼在數組上映射的比較均勻，擾動函數就派上用場了，把高位值的特性糅合進低位值，增加低位值的随機性，進而使散列分布的更加松散，以此提高性能。下圖舉了個例子幫助了解。
7. 替代哈希是怎麼回事？
我們看到hash方法中首先會将hashSeed指派給h。這個hashSeed就是哈希種子，它是一個随機的值，作用就是幫助優化哈希函數。hashSeed預設是0，也就是預設不使用替代雜湊演算法。那麼什麼時候使用hashSeed呢？首先需要設定開啟替代哈希，在系統屬性中設定jdk.map.althashing.threshold的值，在系統屬性中這個值預設是-1，當它是-1的時候使用替代哈希的閥值為Integer.MAX_VALUE。這也意味着可能你永遠也不會使用替代哈希了。當然你可以把這個閥值設小一點，這樣當集合元素達到閥值後就會生成一個随機的hashSeed。以此增加hash函數的随機性。為什麼要使用替代哈希呢？當集合元素達到你設定的閥值之後，意味着哈希表已經比較飽和了，出現哈希沖突的可能性就會大大增加，這時對再添加進來的元素使用更加随機的散列函數能夠使後面添加進來的元素更加随機的分布在散清單中。
注：以上分析全部基于JDK1.7，不同版本之間會有較大的改動，讀者需要注意。
原文位址：https://mp.weixin.qq.com/s/0MQJ7sHQXS_nrmXm0odQNg