資訊專欄INFORMATION COLUMN
摘要：判斷該首節點是否與插入的鍵值對的和一致，若一致則替換該節點的值為，否則進入下一步判斷首節點是否為樹節點，若是則調用樹節點的方法遍歷紅黑樹，否則遍歷鏈表。中的方法會在鏈表超過樹化閾值的時候，將鏈表轉化為紅黑樹。
前言
由于Java 1.7和Java 1.8的HashMap的HashMap中的put()和get()方法在實現上差異很大，所以本文將于分別分析這兩個版本的put()和get()f方法
下面將會分析這部分的源碼，如果覺得源碼分析內容太啰嗦，可以跳過源碼部分，直接看源碼下面的總結。
put()方法源碼分析HashMap的put()方法是我們最常用的方法，但是put()方法是怎么工作的呢？
Java 1.7 put()方法public V put(K key, V value) {
if (key == null)// 處理key為null的情況
return putForNullKey(value);
// 計算key的hash值
int hash = hash(key);
// 計算命中table的索引
int i = indexFor(hash, table.length);
// 遍歷命中的鏈表
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
// 存在key和hash值相同則替換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++;
// 增加新鏈表
addEntry(hash, key, value, i);
// 上一次節點不存在，返回null
return null;
}
put()方法實際上是
若key為null時，直接調用putForNullKey()方法。否則進入下一步
調用hash()方法獲取key的hash值，進入下一步
調用indexFor()計算命中的散列表table的索引
遍歷鏈表，如果鏈表不存在或鏈表不存在key和hash值相同的節點，則創建新的鏈表或尾部添加節點，否則替換對應節點的value
putForNullKey() private V putForNullKey(V value) {
// 遍歷鏈表，但是命中的散列表的索引和key的hash值為0
// 后續邏輯與`put()`類似
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;
}
putForNullKey只是將命中散列表table的索引和key的hash值都設置為0，其他邏輯與put()方法后續的邏輯一致。
indexFor()方法 /**
* 計算命中散列表的索引
*/
static int indexFor(int h, int length) {
// 等價于length%h
return h & (length-1);
}
hash()方法
/**
* hash值計算方法
*/
final int hash(Object k) {
int h = 0;
// 使用替代的hash方法
if (useAltHashing) {
if (k instanceof String) {
// 為字符串則使用特定的hash方法
return sun.misc.Hashing.stringHash32((String) k);
}
// 使用特定的hash種子計算hash值
h = hashSeed;
}
h ^= k.hashCode();
// 這部分代碼是為了減少哈希碰撞
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
addEntry()方法
void addEntry(int hash, K key, V value, int bucketIndex) {
// 判斷散列表是否需要擴容或者未初始化
if ((size >= threshold) && (null != table[bucketIndex])) {
// 散列表擴容為原來的2倍
resize(2 * table.length);
// 計算key的hash值，key為null則返回0
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 創建新的鏈表
// 如果鏈表已存在，則是將新節點插入頭部（頭插法）
createEntry(hash, key, value, bucketIndex);
}
createEntry()方法
/**
* 頭插法插入新的節點
* 不需要判斷鏈表是否存在
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Java 1.8
put()方法
/**
* HashMap的put()方法支持key/value為null
*/
public V put(K key, V value) {
//實際上是先調用HashMap的hash()方法獲取到key的hash值
//然后調用HashMap的putVal()方法
return putVal(hash(key), key, value, false, true);
}
put()方法實際上是
調用hash()方法獲取到key的hash值
調用putVal()方法存儲key-value
核心方法是putVal()方法，下面我會先分析一下hash()方法，因為這個方法涉及到hash值這個關鍵屬性的計算。
hash()方法 static final int hash(Object key) {
int h;
// key為null時，hash值為0
// key不為null時，調用key對象的hashCode()方法并通過位運算異或和無符號右移將高位分散到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash()方法指定了null的hash值為0。這樣就可以支持key為null。
(h = key.hashCode()) ^ (h >>> 16)這段代碼通過位運算異或和無符號右移將高位分散到低位，這樣做可以減少哈希碰撞的概率（這塊不是很清楚原理，是從方法注釋上了解到的）
putVal()方法 /**
* Map.put()方法的實際實現
*
* @param hash key的hash值
* @param key 鍵值對中的key
* @param value 鍵值對中的value
* @param onlyIfAbsent 如果為true，則鍵值對中的值已經存在則不修改這個值
* @param evict 如果為false，則是處于創建模式
* @return 上一次的value，如果上一次的value不存在，則為null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//tab用于暫存散列表table。p為散列表中對應索引的鏈表的頭節點的指針。n存儲tab的長度。i則為命中的散列表的索引
Node[] tab; Node p; int n, i;
//給tab和n賦值
//當tab為null或者tab的長度n為0時，觸發resize()來初始化tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//使用(n - 1) & hash（等價于hash%n）計算命中的散列表索引，同時判斷散列表對應索引的鏈表是否存在
if ((p = tab[i = (n - 1) & hash]) == null)
//散列表對應索引的鏈表不存在則創建一個新的鏈表
tab[i] = newNode(hash, key, value, null);
else {//散列表對應索引的鏈表已存在
Node e; K k;
// 判斷頭節點的hash值和key是否與入參的hash值和key一致。需要注意，null的hash值為0
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 對應的鍵值對已經存在，記錄下來
e = p;
else if (p instanceof TreeNode)//判斷對應的鏈表是否轉化為紅黑樹
//若是，則直接調用紅黑樹的putTreeVal()方法
e = ((TreeNode)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開始，所以為閾值-1
// 將鏈表轉化為紅黑樹
treeifyBin(tab, hash);
// 中斷循環
break;
}
// 判斷當前遍歷的節點的hash值和key是否與入參的hash值和key一致，即key是否已經存在
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// key已經存在，中斷循環
break;
// 記錄當前遍歷的節點
p = e;
}
}
if (e != null) { // Map中存在重復的key
V oldValue = e.value;//記錄下舊值
if (!onlyIfAbsent || oldValue == null)//判斷值存在是否可以進行修改以及舊值是否為null
e.value = value;//修改該節點的值
afterNodeAccess(e);// 鏈表節點的回調方法，此處為空方法
return oldValue;//返回舊值
}
}
// HashMap發生結構變化，變化次數累加
++modCount;
// 鍵值對個數自增，同時判斷是否達到擴容的閾值
if (++size > threshold)
resize();
// 鏈表節點的回調方法，此處為空方法
afterNodeInsertion(evict);
// 此處返回null是因為鏈表新增了節點，所以上一次的值必然為null
return null;
}
putVal()方法的關鍵點：
若table沒有初始化則調用reszie()方法初始化。
計算命中的散列表索引位置，公式為(n - 1) & hash（等價于hash%n）。其中n為散列表長度，hash為插入的鍵值對的key的哈希值。
判斷散列表對應索引中的首節點是否為null，若為null，則創建鏈表，否則進入下一步。
判斷該首節點是否與插入的鍵值對的key和hash一致，若一致則替換該節點的值為value，否則進入下一步
判斷首節點是否為樹節點，若是則調用樹節點的putTreeVal()方法遍歷紅黑樹，否則遍歷鏈表。
遍歷紅黑樹時，若存在key和hash相同的節點就替換對應節點的值value，若不存在則插入新的樹節點。
遍歷鏈表時，若存在key和hash相同的節點就替換對應節點的值為value。若找不到key和hash相同的節點，則鏈表尾部插入節點，同時進入下一步。
若當前鏈表長度大于或等于樹化閾值TREEIFY_THRESHOLD(8)時，則將鏈表轉化為紅黑樹。
get()方法源碼分析除了HashMap的put()方法外，get()方法也是一個我們常用的方法，下面開始分析其關鍵的源碼。
Java 1.7 get()方法 public V get(Object key) {
if (key == null)// key為null時特殊處理
return getForNullKey();
// 關鍵獲取key對應value的代碼
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
get()方法的關鍵點如下：
若key為null，則調用getForNullKey()方法獲取value，否則進入下一步
調用getEntry()方法獲取對應的Entry對象
對應的Entry對象為null時返回null，否則調用getValue()返回其value
getForNullKey() private V getForNullKey() {
// 命中散列表索引為0，無需計算key的hash值
// 遍歷命中的鏈表
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
getEntry()
