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