前言
HashMap在開發(fā)中使用非常廣泛盖腕，也是Java面試中必不可少的部分勺鸦。所以適當(dāng)?shù)牧私釮ashMap原理對我們很有幫助并巍。
首先分析下面HashMap的結(jié)構(gòu)圖：
HashMap結(jié)構(gòu)
從上圖我們可以看到：HashMap是由數(shù)組和單向鏈表組成的，左邊是一個Entry<K,V>[] table數(shù)組换途。右邊是一個單向鏈表懊渡，每一個節(jié)點是Entry<K,V>。對于不了解單向鏈表的可以參考我上篇文《Java實現(xiàn)單向鏈表功能》军拟。下面我們開始分析HashMap的源碼剃执，后續(xù)對比一下JDK1.8和JDK1.7的區(qū)別。
問題
在分析源碼之前懈息，我們先提出這幾個問題：
- 數(shù)組怎么跟鏈表結(jié)合的肾档？
- 哈希沖突是什么？
- HashMap的擴容是什么辫继？
- 門限值怒见，負載因子，容量和元素數(shù)量究竟有什么關(guān)系姑宽？
- 負載因子為什么是0.75遣耍，能否修改？
下面我們先從JDK1.7開始分析源碼炮车，并解決上面的幾個問題舵变。
源碼分析（JDK1.7）
首先看看HashMap幾個關(guān)鍵的成員變量：
//默認HashMap容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//默認負載因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final Entry<?,?>[] EMPTY_TABLE = {};
//首先創(chuàng)建一個table數(shù)組
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//門限值
int threshold;
//負載因子，默認是0.75
final float loadFactor;
構(gòu)造函數(shù)
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
我們平常使用無參的構(gòu)造方法示血，那么默認負載因子就是0.75棋傍，默認容量就是16
put方法
public V put(K key, V value) {
//如果table數(shù)組為空，那么初始化數(shù)組难审。
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//hashcode再次處理
int hash = hash(key);
//與運算瘫拣，判斷當(dāng)前插入的元素應(yīng)該放在哪一個table[i]中
//有可以說成放在第幾個桶中（bucket）
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//for循環(huán)遍歷當(dāng)前桶的鏈表，如果存在相同的key告喊，則替換當(dāng)前值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//如果HashMap不存在該元素麸拄，則新增一個
addEntry(hash, key, value, i);
return null;
}
- 先看for循環(huán)部分的代碼:
Entry<K,V> e = table[i]; e != null; e = e.next
結(jié)合注釋我們明白到，要輪詢單向鏈表黔姜，必需從鏈表的頭部開始拢切，那么得出 table[i] 就是我們第i個鏈表的頭部head。
- 第1點結(jié)論我們還可以通過addEntry方法驗證秆吵，看代碼：
void addEntry(int hash, K key, V value, int bucketIndex) {
//擴容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//創(chuàng)建一個新元素
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//將key淮椰，value傳入創(chuàng)建一個新的Entry，并賦值table[i],
table[bucketIndex] = new Entry<>(hash, key, value, e);
//HashMap包含的元素加1
size++;
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
//創(chuàng)建一個新Entry，并把新創(chuàng)見的next指向傳入的 Entry<K,V> n
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
addEntry擴容部分先不用看主穗，主要看createEntry方法泻拦。
實際上createEntry的工作就是：
- 把新put進來的entry賦值給table[i]。
- 把當(dāng)前的table[i].next指向以前的table[i]忽媒。跟上篇文章《Java實現(xiàn)單向鏈表功能》add方法類似争拐。
那么我們就可以解決提出的問題：
1.數(shù)組怎么跟鏈表結(jié)合的？
數(shù)組table[i]存儲我們每一條鏈表的頭部head晦雨，而head連接后面新put進來的Entry架曹。
2.哈希沖突是什么？
h哈希沖突簡單來說執(zhí)行put方法之后算出的 i 是相等的闹瞧，相當(dāng)于放在同個table[i],也就是同一條鏈表上绑雄。
擴容resize方法
在addEntry方法我們曾經(jīng)見過resize方法，下面看一下resize邏輯
void resize(int newCapacity) {
------------省略部分代碼---------
//創(chuàng)建一個新的table數(shù)組, table的長度為newCapacity
Entry[] newTable = new Entry[newCapacity];
//newTable 賦值操作
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//把操作完成的的newTable 賦值給table
table = newTable;
//門限值賦值等于當(dāng)前的容量乘以負載因子夹抗。
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for,while循環(huán)绳慎，遍歷所有HashMap所有的元素
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
//是否重新hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//取出所有的并且計算i，用來判斷放在哪一條鏈表上
int i = indexFor(e.hash, newCapacity);
//把屬于該鏈表上的Entry重新串起來
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
結(jié)合上面的代碼以及注釋得出擴容過程：
- 創(chuàng)建一個新數(shù)組newTable漠烧，長度為newCapacity杏愤。不知道大家還有沒有印象，在addEntry方法中的擴容邏輯 resize(2 * table.length)已脓，那么說明HashMap每一次擴容都是以前的2倍珊楼。
- 取出HashMap所有的Entry，重新計算 i 值度液，并且將第 i 條鏈表上的所有Entry重新串起來厕宗。賦值給新創(chuàng)建的newTable 。
- 把操作完成的newTable 重新賦值table上堕担。
- 重新計算門限值已慢。
那么我們就可以解決提出的問題：
1.HashMap的擴容是什么？
擴容：增加HashMap容量霹购，相當(dāng)于增加table數(shù)組的length佑惠，容納更多新put的Entry。
2.門限值齐疙，負載因子膜楷，容量和元素數(shù)量究竟有什么關(guān)系？
1)門限值 = 負載因子*容量贞奋。
2)那么與元素數(shù)量有什么關(guān)系呢赌厅？在addEntry方法曾經(jīng)看到
if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); --------省略----------- }那么也就是說當(dāng)HashMap的size超過門限值的時候，HashMap就會擴容轿塔，一次擴容2倍特愿。
JDK1.7大概就分析到這里仲墨。
JDK1.8的主要變化
JDK1.8比JDK1.7改動了很多，特別性能上優(yōu)化洽议，但HashMap主體結(jié)構(gòu)還是一樣的宗收。下面主要對比一下put方法的邏輯。截取關(guān)鍵的部分代碼分析亚兄。
public V put(K key, V value) {
return 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;
-----------------------省略---------------------------
//首先計算屬于i值，判斷屬于那一條鏈表尊浓，
//當(dāng)該條鏈表為空時直接賦值當(dāng)前的Entry县耽。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
-----------------------省略---------------------------
//把新put進來的元素添加鏈表上强重，相當(dāng)于我們JDK1.7的createEntry方法。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//當(dāng)一條鏈表的Entry的數(shù)量大于TREEIFY_THRESHOLD - 1進行樹化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
p = e;
}
}
-----------------------省略---------------------------
}
++modCount;
//當(dāng)size大于門限值執(zhí)行resize擴容膳叨。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
從代碼可以看出JDK1.8和JDK1.7邏輯大體相同，值得注意一下的是“樹化”痘系，請看下圖：
樹化
樹化簡單來說就是將以前的鏈表形式改成紅黑樹結(jié)構(gòu)菲嘴，那我們?yōu)槭裁匆某蛇@種結(jié)構(gòu)？
在元素put過程中汰翠，如果發(fā)成哈希沖突龄坪，則算出來的 i 會相等，存放在一個桶中組成一個鏈表复唤。我們都知道鏈表查詢線性的健田，再put過程中都會遍歷某個桶整個鏈表，會嚴重影響存儲性能佛纫。有關(guān)紅黑樹的就不展開了妓局，有興趣的可以查閱相關(guān)資料。
我們剩下最后一個問題
負載因子為什么是0.75呈宇，能否修改好爬？
1. 輪詢長鏈表是耗費性能。HashMap理想狀態(tài)是每一個桶的元素都是相近的甥啄，也就是 0 - i 的鏈表長度都是相近的存炮，性能是最好的。但是現(xiàn)實中并不是型豁，極端時候會遇到某個桶的鏈表有N個數(shù)據(jù)僵蛛，另外一個桶則沒有數(shù)據(jù)，因為存數(shù)據(jù)是隨機的迎变，那么就不能保證 i 值能均勻分布充尉。
2.負載因子默認0.75是sun公司經(jīng)過無數(shù)測試總結(jié)出來的，也就是說等于0.75的時候發(fā)生哈希碰撞衣形，性能最好的驼侠。那0.75能否修改姿鸿？可以的。但是不推薦修改倒源。
3.有些人會有疑問苛预，例如我已經(jīng)開辟了16個桶，為什么不存16個元素再重新resize（負載因子等于1）笋熬，這不是浪費空間嗎热某？這個問題答案是：因為哈希碰撞都是隨機的，就算放置第15,16個元素胳螟，元素也不一定分在了15,16桶上昔馋，那么其他桶的鏈表就會變長了，影響性能糖耸。那我16個桶只放8個元素就擴容了（負載因子等于0.5）秘遏？這樣的話就會很浪費內(nèi)存空間了。0.75其實就是一個折中的數(shù)值吧嘉竟。
