鑒于篇幅，本篇主要分析JDK1.7源碼，關于JDK1.8部分的源碼分析放入下篇文章
Java源碼分析——HashMap(JDK1.8）
HashMap在JDK1.7與JDK1.8中有較大的差别，下文就先以JDK1.7為例剖析源碼，然後再與JDK1.8比較二者之間的差别。
首先看與HashMap有直接關系的類與接口：
HashMap 是基于哈希表的 Map 接口的實作，以 Key-Value 的形式存在，即存儲的對象是 Entry (同時包含了 Key 和 Value) 。在HashMap中，其會根據hash算法來計算key-value的存儲位置并進行快速存取。特别地，HashMap最多隻允許一條Entry的鍵為Null(多條會覆寫)，但允許多條Entry的值為Null。對于Cloneable接口就不再贅述；而Serializable接口則表明HashMap類可被序列化。
一、HashMap資料結構
衆所周知，數組的特點是尋址容易，插入和删除困難；而連結清單的特點是尋址困難，插入和删除容易。而HashMap的插入删除以及尋址都可以在常數複雜度内解決，這是因為HashMap采用了拉鍊法，即它的内部實作是一個連結清單數組。
以下是HashMap的部分字段，其中HashMap.Node[ ]即是我們剛才所說的連結清單數組中的數組，然後我們繼續往下看
我們可以發現内部類Node内有hash哈希值，key、value鍵值對，以及指向Node下一個節點的指針next，是以就知道每個table數組中的每個元素Node都是一個連結清單的頭節點，這也就是我們剛剛說的連結清單數組。
另外，有幾點要提的是table[ ]數組的長度一定為2的n次方，具體原因下文會詳細闡述。
二、HashMap()構造函數
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于 0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//初始容量不能超過 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負載因子不能小于 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// HashMap 的容量必須是2的幂次方，超過 initialCapacity 的最小 2^n
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
//負載因子
this.loadFactor = loadFactor;
//設定HashMap的容量極限，當HashMap的容量達到該極限時就會進行自動擴容操作
threshold = (int)(capacity * loadFactor);
// HashMap的底層實作仍是數組，隻是數組的每一項都是一條鍊
table = new Entry[capacity];
init();
}
public HashMap(Map<? extends K, ? extends V> m) {
// 初始容量不小于 16
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
在這裡，我們提到了兩個非常重要的參數：初始容量和負載因子，這兩個參數是影響HashMap性能的重要參數。其中，容量表示哈希表中桶的數量 (table 數組的大小)，初始容量是建立哈希表時桶的數量；而負載因子則是table數組中已存在的資料與整個table數組長度的比值，它衡量的是一個散清單的空間的使用程度，負載因子越大表示散清單的裝填程度越高，反之愈小。
三、HashMap存取鍵值對
1、HashMap 的存儲
public V put(K key, V value) {
//當key為null時，調用putForNullKey方法，并将該鍵值對儲存到table的第一個位置
if (key == null)
return putForNullKey(value);
//根據key的hashCode計算hash值
int hash = hash(key.hashCode());
//計算該鍵值對在數組中的存儲位置（哪個桶）
int i = indexFor(hash, table.length);
//在table的第i個桶上進行疊代，尋找 key 儲存的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鍊上是否存在hash值相同且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++; //修改次數增加1，快速失敗機制
//原HashMap中無該映射，将該添加至該鍊的鍊頭
addEntry(hash, key, value, i);
return null;
}
首先，判斷key是否為null，若為null，則直接調用putForNullKey()方法；若不為空，則先計算key的hash值，然後根據hash值搜尋在table數組中的索引位置，如果table數組在該位置處有元素，則查找是否存在相同的key，若存在則覆寫原來key的value，否則将該元素儲存在鍊頭。此外，若table在該處沒有元素，則直接儲存。
private V putForNullKey(V value) {
// 若key==null，則将其放入table的第一個桶，即 table[0]
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
// 若已經存在key為null的鍵，則替換其值，并傳回舊值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++; // 快速失敗
addEntry(0, null, value, 0); // 否則，将其添加到 table[0] 的桶中
return null;
}
HashMap 中可以儲存鍵為NULL的鍵值對，且該鍵值對是唯一的。若再次向其中添加鍵為NULL的鍵值對，将覆寫其原值。此外，如果HashMap中存在鍵為NULL的鍵值對，那麼一定在第一個桶中。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
這裡的哈希方法我們不必深究，隻需要知道key通過哈希方法得到的值盡可能分布得均勻，即遇到兩個不同key的hash相等的可能性很小。
static int indexFor(int h, int length) {
return h & (length-1); // 作用等價于取模運算，但這種方式效率更高
}
這裡我們來解釋為什麼table[ ]數組的長度必須為2的n次方。因為對于2、4、8、16、32…2^n這樣的數組，它們的二進制-1的值一定是1、11、111、1111…這樣之後，它們再與一個數執行與操作，那麼得到的值一定是hash與length的模(即hash除以length的餘數)，這樣我們就能保證通過每個鍵值對的哈希值，而把這些鍵值對均勻地放入長度為 2^n的數組。
void addEntry(int hash, K key, V value, int bucketIndex) {
//擷取bucketIndex處的連結清單
Entry<K,V> e = table[bucketIndex];
//将新建立的 Entry 鍊入 bucketIndex處的連結清單的表頭
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//若HashMap中元素的個數超過極限值 threshold，則容量擴大兩倍
if (size++ >= threshold)
resize(2 * table.length);
}
通過上述源碼我們可以清楚地了解到 鍊的産生時機。HashMap 總是将新的Entry對象添加到bucketIndex處，若bucketIndex處已經有了Entry對象，那麼新添加的Entry對象将指向原有的Entry對象，并形成一條新的以它為鍊頭的Entry鍊；但是，若bucketIndex處原先沒有Entry對象，那麼新添加的Entry對象将指向 null，也就生成了一條長度為 1 的全新的Entry鍊了。HashMap 永遠都是在連結清單的表頭添加新元素。此外，若HashMap中元素的個數超過極限值 threshold，其将進行擴容操作，一般情況下，容量将擴大至原來的兩倍，即保證length為2的n次方。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 若 oldCapacity 已達到最大值，直接将 threshold 設為 Integer.MAX_VALUE
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return; // 直接傳回
}
// 否則，建立一個更大的數組
Entry[] newTable = new Entry[newCapacity];
//将每條Entry重新哈希到新的數組中
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor); // 重新設定 threshold
}
随着HashMap中元素的數量越來越多，發生碰撞的機率将越來越大，所産生的子鍊長度就會越來越長，這樣勢必會影響HashMap的存取速度。為了保證HashMap的效率，系統必須要在某個臨界點進行擴容處理，該臨界點就是HashMap中元素的數量在數值上等于threshold（table數組長度*加載因子）。但是，不得不說，擴容是一個非常耗時的過程，因為它需要重新計算這些元素在新table數組中的位置并進行複制處理。
void transfer(Entry[] newTable) {
// 将原數組 table 賦給數組 src
Entry[] src = table;
int newCapacity = newTable.length;
// 将數組 src 中的每條鍊重新添加到 newTable 中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null; // src 回收
// 将每條鍊的每個元素依次添加到 newTable 中相應的桶中
do {
Entry<K,V> next = e.next;
// e.hash指的是 hash(key.hashCode())的傳回值;
// 計算在newTable中的位置，注意原來在同一條子鍊上的元素可能被配置設定到不同的子鍊
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
特别需要注意的是，在重哈希的過程中，原屬于一個桶中的Entry對象可能被分到不同的桶，因為HashMap 的容量發生了變化，那麼 h&(length - 1) 的值也會發生相應的變化。
2、HashMap 的讀取
public V get(Object key) {
// 若為null，調用getForNullKey方法傳回相對應的value
if (key == null)
// 從table的第一個桶中尋找 key 為 null 的映射；若不存在，直接傳回null
return getForNullKey();
// 根據該 key 的 hashCode 值計算它的 hash 碼
int hash = hash(key.hashCode());
// 找出 table 數組中對應的桶
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//若搜尋的key與查找的key相同，則傳回相對應的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
因為整個HashMap内層是一個數組，是以通過在、可以在O(1)時間複雜度内查詢到對應的key。另外如果發生哈希碰撞，則會在對應的數組位置處周遊相應的連結清單，是以整個HashMap的尋址可以在O(1+a)的時間複雜度内解決。(a為連結清單的長度)
private V getForNullKey() {
// 鍵為NULL的鍵值對若存在，則必定在第一個桶中
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
// 鍵為NULL的鍵值對若不存在，則直接傳回 null
return null;
}
是以，調用HashMap的get(Object key)方法後，若傳回值是 NULL，則存在如下兩種可能：
(1) 該 key 對應的值就是 null;
(2) HashMap 中不存在該 key。
四、JDK1.8新特性
1、HashMap屬性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 預設的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 預設的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 當桶(bucket)上的結點數大于這個值時會轉成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 當桶(bucket)上的結點數小于這個值時樹轉連結清單
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中結構轉化為紅黑樹對應的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存儲元素的數組，總是2的幂次倍
transient Node<k,v>[] table;
// 存放具體元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的個數，注意這個不等于數組的長度。
transient int size;
// 每次擴容和更改map結構的計數器
transient int modCount;
// 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
int threshold;
// 填充因子
final float loadFactor;
}
2、HashMap()構造函數
putMapEntries()方法與JDK1.7中不同，是将m的所有元素存入本HashMap執行個體中。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 判斷table是否已經初始化
if (table == null) { // pre-size
// 未初始化，s為m的實際元素個數
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 計算得到的t大于門檻值，則初始化門檻值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 已初始化，并且m元素個數大于門檻值，進行擴容處理
else if (s > threshold)
resize();
// 将m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
關于resize()擴容方法在後續詳細分析。
2、hash算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先擷取對象的hashCode()值，然後将hashCode值右移16位，然後将右移後的值與原來的hashCode做異或運算。
因為h是key的hashCode值，是以h的高16位也是有值的，是以在hash方法中将key的hashCode右移16位在與自身異或，使得高位也可以參與hash，更大程度上減少了碰撞率。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
HashMap.Node[] tab;
int n;
if ((tab = this.table) == null || (n = tab.length) == 0)
n = (tab = this.resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//擷取位置
tab[i] = newNode(hash, key, value, null);
...
}
在putVal源碼中，我們通過(n-1)&hash擷取該對象的鍵在hashmap中的位置。其中n表示的是hash桶數組的長度，并且該長度為2的n次方，這樣(n-1)&hash就等價于hash%n。
3、HashMap存儲
public V put(K key, V value) {
return this.putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟①：tab為空則建立
// table未初始化或者長度為0，進行擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟②：計算index，并對null做處理
// (n - 1) & hash 确定元素存放在哪個桶中，桶為空，新生成結點放入桶中(此時，這個結點是放在數組中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已經存在元素
else {
Node<K,V> e; K k;
// 步驟③：節點key存在，直接覆寫value
// 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一個元素指派給e，用e來記錄
e = p;
// 步驟④：判斷該鍊為紅黑樹
// hash值不相等，即key不相等；為紅黑樹結點
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步驟⑤：該鍊為連結清單
// 為連結清單結點
else {
// 在連結清單最末插入結點
for (int binCount = 0; ; ++binCount) {
// 到達連結清單的尾部
if ((e = p.next) == null) {
// 在尾部插入新結點
p.next = newNode(hash, key, value, null);
// 結點數量達到門檻值，轉化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循環
break;
}
// 判斷連結清單中結點的key值與插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環
break;
// 用于周遊桶中的連結清單，與前面的e = p.next組合，可以周遊連結清單
p = e;
}
}
// 表示在桶中找到key值、hash值與插入元素相等的結點
if (e != null) {
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent為false或者舊值為null
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值
e.value = value;
// 通路後回調
afterNodeAccess(e);
// 傳回舊值
return oldValue;
}
}
// 結構性修改
++modCount;
// 步驟⑥：超過最大容量 就擴容
// 實際大小大于門檻值則擴容
if (++size > threshold)
resize();
// 插入後回調
afterNodeInsertion(evict);
return null;
}
putVal方法執行過程如下：
①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；
②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接建立節點添加，轉向⑥，如果table[i]不為空，轉向③；
③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆寫value，否則轉向④，這裡的相同指的是hashCode以及equals；
④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；
⑤.周遊table[i]，判斷連結清單長度是否大于8，大于8的話把連結清單轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行連結清單的插入操作；周遊過程中若發現key已經存在直接覆寫value即可；
⑥.插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。
從源碼中可知，JDK1.8中出現哈希碰撞插入資料是在連結清單尾部，這與JDK1.7中是不同的。
4、HashMap讀取
public V get(Object key) {
Node<k,v> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table已經初始化，長度大于0，根據hash尋找table中的項也不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 桶中第一項(數組元素)相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中不止一個結點
if ((e = first.next) != null) {
// 為紅黑樹結點
if (first instanceof TreeNode)
// 在紅黑樹中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 否則，在連結清單中查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
鑒于篇幅，JDK1.8中HashMap的resize()擴容方法、轉化為紅黑樹方法等将在下篇中繼續分析。