一、導(dǎo)入語
HashMap是我們最常見也是最長使用的數(shù)據(jù)結(jié)構(gòu)之一，它的功能強(qiáng)大、用處廣泛。而且也是面試常見的考查知識點。常見問題可能有HashMap存儲結(jié)構(gòu)是什么樣的？HashMap如何放入鍵值對、如何獲取鍵值對應(yīng)的值以及如何刪除一個鍵值對。今天我們就來看看HashMap底層的實現(xiàn)原理。下面我們就開始進(jìn)入正題，分析一下hashmap源碼的實現(xiàn)原理。
創(chuàng)新互聯(lián)公司是一家專業(yè)從事成都網(wǎng)站設(shè)計、
網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計的品牌網(wǎng)絡(luò)公司。如今是成都地區(qū)具影響力的網(wǎng)站設(shè)計公司,作為專業(yè)的成都網(wǎng)站建設(shè)公司,
創(chuàng)新互聯(lián)公司依托強(qiáng)大的技術(shù)實力、以及多年的網(wǎng)站運營經(jīng)驗,為您提供專業(yè)的成都網(wǎng)站建設(shè)、營銷型網(wǎng)站建設(shè)及網(wǎng)站設(shè)計開發(fā)服務(wù)！
二、HashMap構(gòu)造方法以及存儲結(jié)構(gòu)
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY]; init();
}HashMap的構(gòu)造方法有好幾個，在這里我們就不一一介紹，只說一下我們最常見的HashMap無參構(gòu)造方法。上面的構(gòu)造方法中，有幾個變量需要我們這里說明一下：
loadFactor:加載因子，默認(rèn)值為0.75；
threshold:threshold是一個閾值，初始值為默認(rèn)為16*0.75。當(dāng)hashmap中存放鍵值對數(shù)量大于該值時，表示hashmap容量大小需要擴(kuò)充，一般容量會翻倍。
table:table其實是一個Entry類型的數(shù)組，在hashmap中我們利用數(shù)組和鏈表來解決hash沖突，這里的table數(shù)組用于存放沖突鏈表的頭結(jié)點。
另外在HahsMap中，我們通過數(shù)組加鏈表的方式來存儲Entry節(jié)點（Entry數(shù)據(jù)結(jié)構(gòu)用于存儲鍵值對）。這里所謂的數(shù)組即是上面提到的table，它是一個Entry數(shù)組，table對象中節(jié)點初始化值均為null，當(dāng)我們新插入的節(jié)點第一次散列到該位置時，會將節(jié)點插入到table中對應(yīng)位置。如果后續(xù)存在散列位置相同的節(jié)點，會以鏈表的方式解決hash沖突。示意圖如下：
三、put()方法解析
put方法是我們最常用方法，我們利用該方法將鍵值對放入HashMap集合中，那么HashMap到底是什么樣的結(jié)構(gòu)，put()方法又做了什么呢？我們下面就來看看put()方法的具體實現(xiàn)。
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) {
Object k; 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); return null;
}private V putForNullKey(V value) { 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;
}if (key == null) return putForNullKey(value);
如果當(dāng)前傳入的key值為null，執(zhí)行putForNullKey()方法;當(dāng)key值為null時，hash值為0，將其保存到以table[0]為開頭的鏈表中去。遍歷鏈表，如果存在某節(jié)點的key值為null，則用新value直接將其替換。如果未找到key值為null的節(jié)點，調(diào)用addEntry()方法插入一個key為null的新節(jié)點。addEntry方法我們會在后文中介紹。
int hash = hash(key.hashCode());int i = indexFor(hash, table.length);
為什么這里還要對key的hashCode值再調(diào)用一次哈希算法呢？簡單來說就是為了讓傳遞進(jìn)來的key散落位置可以更加均勻，具體原因就不在本文中介紹了，網(wǎng)上有很多資料可供借鑒。
接著調(diào)用indexFor方法計算當(dāng)前key值散落在table中的位置，其實就是key%table.length
for (Entry e = table[i]; e != null; e = e.next) {
Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); return oldValue;
}
}
遍歷以table[i]為頭結(jié)點的鏈表，查找是否已經(jīng)有相同的key值的節(jié)點存在于鏈表中。判斷條件為if (e.hash == hash && ((k = e.key) == key || key.equals(k)))。這個判斷條件十分重要，我們來仔細(xì)分析下。首先是e.hash == hash：之前我們已經(jīng)計算出了當(dāng)前待處理節(jié)點的hash值，并保存在變量hash中，在此我們需要比較當(dāng)前鏈表遍歷節(jié)點key的hash值(e.hash)和hash是否相等。如果我們?nèi)タ匆幌耡ddEntry()方法我們會發(fā)現(xiàn)，Entry節(jié)點的存儲位置實際上是由key的hash值來決定的。如果key的hash相同，那么他們的存儲位置也相同。(k = e.key) == key || key.equals(k))。先簡單的說一下”==”和”equals”的意義，”==”是引用一致性判斷，而equals是內(nèi)容一致性判斷。這里的意思也就是說如果兩個key對象指向的是同一個對象，或者他們就是同一個對象，則返回true。總結(jié)一下，如果hash值相同，則key值相同或是同一個對象的引用，則表示hashmap中存在以key為鍵值的Entry節(jié)點。
如果判斷if (e.hash == hash && ((k = e.key) == key || key.equals(k)))判斷條件返回為true，則用新值替換老值。
如果沒有找到相同的key值，則調(diào)用addEntry()方法新增一個指定key和value的Entry節(jié)點。
四、addEntry()方法解析
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length);
}接下來繼續(xù)看addEntry()方法，假設(shè)當(dāng)前節(jié)點為插入到table[bucketIndex]位置的第一個節(jié)點
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
在Entry類的構(gòu)造方法中有這樣一句代碼:
next = e;
即當(dāng)前新建的entry節(jié)點將指向Entry構(gòu)造方法傳遞過來的Entry節(jié)點e，此時e保存的值為頭結(jié)點的值，也就是null。該節(jié)點創(chuàng)建完之后，又被賦值給table[bucketIndex]，相當(dāng)于鏈表的頭結(jié)點了保存了最新插入的節(jié)點。如下圖所示我們在table[i]位置插入了Entry
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
此時table[buckertIndex]中存放的節(jié)點為
新建一個Entry節(jié)點,key=”key2”,value=”value2”，同時該entry節(jié)點next值指向
另外在addEntry方法中有如下兩句代碼
if (size++ >= threshold) resize(2 * table.length);
size的值為當(dāng)前hashMap中存儲的節(jié)點個數(shù)，threshold是一個閾值。如果hashMap中存儲的節(jié)點個數(shù)大于等于threshold，表示我們需要對當(dāng)前hashMap進(jìn)行擴(kuò)容了。每一次擴(kuò)充容量為之前容量的2倍。我們來看一下resize()方法。
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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { Entry e = src[j]; if (e != null) {
src[j] = null; do { Entry next = e.next; int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}關(guān)鍵代碼是這一段
Entry[] newTable = new Entry[newCapacity];transfer(newTable);
table = newTable;
如果resize()之前Entry數(shù)組的大小為A,那么newTable數(shù)組的大小為2A
transfer(newTable)方法用于將原先entry[]數(shù)組中的節(jié)點轉(zhuǎn)移到newTable數(shù)組中，下面我們來看下transfer()方法具體干了什么。
將原來的table數(shù)組賦值給src數(shù)組
獲取newTable數(shù)組的長度，這里為table數(shù)組長度的2倍
循環(huán)遍歷src數(shù)組，執(zhí)行下面的操作
a. 取src[j]節(jié)點的值賦值給e
b. 如果e節(jié)點不為null，將src[j]的值置為null
我們來舉兩個簡單的例子說明一下tranfer到底干了什么：
當(dāng)src[j]不為空時，比方說src[j]中保存的Entry節(jié)點key=”key2”,value=”value2”，src[j]指向的下一個節(jié)點key=”key1”,value=”value1”，如下圖所示：
最開始的時候newTable[]中并沒有存放任何Entry節(jié)點，只是單純的進(jìn)行了初始化。結(jié)合上面代碼，我們可以看到此時e = entry2節(jié)點，next節(jié)點值為entry1
利用indexFor重新計算出e節(jié)點的散列位置。e節(jié)點的next指向被初始化后的newTable[i]節(jié)點，同時newTabel[i]的值也被賦值為e節(jié)點
最后執(zhí)行e = next;此時e等于entry1
形成節(jié)點的示意圖如下：
接著執(zhí)行
next = e.next，此時e的next節(jié)點為null，next =null；
利用indexFor計算出新的散列位置，比如說新的散列位置為j，此時以newTable[j]為頭節(jié)點的鏈表中已經(jīng)存在了兩個節(jié)點。如下圖所示：
我們將待處理的節(jié)點entry節(jié)點插入后會變成什么樣呢？
簡單的來說resize方法就是去逐個遍歷table[i]后面的Entry節(jié)點鏈表，利用indexFor方法重新結(jié)算節(jié)點的散落位置，并將其插入到以newTable[]為頭結(jié)點的鏈表中去。
五、get()方法解析
說完了put我們再來看一下get方法
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value;
} return null;
}private V getForNullKey() { for (Entry e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value;
} return null;
}理解了put方法時如何往hashmap中放入鍵值對的，那么get()方法也就很好理解了。我們來具體看看get()方法的實現(xiàn)。
如果key值為null，執(zhí)行g(shù)etForNullKey()方法。當(dāng)key值為null時，新的鍵值對會放到table[0]處，所以我們先去遍歷table[0]位置的節(jié)點鏈表，查看是否有key值為null的節(jié)點。如果有的話，直接返回value。如果找不到key為null的節(jié)點，返回null。
如果key值不為null，利用indexFor方法找到當(dāng)前key所處的table[i]位置，遍歷table[i]位置的節(jié)點鏈表。根據(jù)e.hash == hash && ((k = e.key) == key || key.equals(k))來判斷是否有相同key值的節(jié)點。如果當(dāng)前位置鏈表中存在key值相同的Entry節(jié)點，返回Entry節(jié)點保存的value。如果找不到key值匹配的Entry節(jié)點，返回null。
六、remove()方法解析
public V remove(Object key) {
Entry e = removeEntryForKey(key); return (e == null ? null : e.value);
}final Entry removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length);
Entry prev = table[i];
Entry e = prev; while (e != null) {
Entry next = e.next;
Object k; if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--; if (prev == e)
table[i] = next; else
prev.next = next;
e.recordRemoval(this); return e;
}
prev = e;
e = next;
} return e;
}別看remove方法這么長，其實它的邏輯很簡單
通過hash()和IndexFor()方法找到當(dāng)前Entry節(jié)點的散列位置i，prev節(jié)點為當(dāng)前節(jié)點的上一個節(jié)點（初始值為table[i]節(jié)點），e節(jié)點表示當(dāng)前節(jié)點。
比較待刪除節(jié)點的key值和當(dāng)前節(jié)點的key值是否相符。如果找不到相符的節(jié)點，返回null；
如果有相符的節(jié)點，且為頭結(jié)點，e節(jié)點的下一個節(jié)點將被賦值給table[i]；
如果有相匹配的節(jié)點，并且不為頭結(jié)點，則prev節(jié)點不再指向e，而是指向e.next，也即是prev.next = e.next;相當(dāng)于一個斷鏈操作；
七、HashMap遍歷
如果讓你寫一個hashmap的遍歷代碼，估計大部分人寫出下面這段代碼?？墒荋ashMap的遍歷過程到底是怎么樣的，為什么我們每次取值的時候都使用iter.next()來取值的呢？下面我們就來看看HashMap的遍歷實現(xiàn)。
Itreator iter = map.entrySet().itreator(); while(iter.hashNext()){
Map.entry entry = (Map.entry) iter.next();
}HashMap類中有一個私有類EntrySet，它繼承自AbstractSet類。EntrySet類中有一個iterator()方法，也就是我們上面在遍歷hashMap所調(diào)用的iterator()方法，它會返回一個Iterator對象。
我們來看看iterator方法：
public Iterator> iterator() { return newEntryIterator();
}
iterator()方法中調(diào)用了newEntryIterator()方法，接著進(jìn)入newEntryIterator()方法看看。
Iterator> newEntryIterator() { return new EntryIterator();
}
newEntryIterator方法又創(chuàng)建了一個EntryIterator對象并返回。這個EntryIterator很關(guān)鍵，我們來具體看看這個類。
private final class EntryIterator extends HashIterator> { public Map.Entry next() { return nextEntry();
}
}
EntryIterator類繼承自HashItertor類，而且HashIterator類只有一個方法next()。既然EntryIterator繼承自HashIterator類，那么EntryIterator到底繼承了父類的哪些對象，默認(rèn)實現(xiàn)了父類的哪些方法呢？我們再看看HashIterator類。
private abstract class HashIterator implements Iterator {
Entry next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry current; // current entry
HashIterator() {
expectedModCount = modCount; if (size > 0) { // advance to first entry
Entry[] t = table; while (index < t.length && (next = t[index++]) == null)
;
}
}
}
HashIterator類中有四個屬性，它們的用處代碼注釋已經(jīng)簡單明了的介紹了。值得注意的是HashIterator()提供了一個無參的構(gòu)造方法，然而他并沒有對所有的屬性進(jìn)行初始化，在這里我們需要明確的是index的值將會被賦為0。同時后面還有一大段，它干了什么呢？
首先是Entry[] t = table；將當(dāng)前存儲頭結(jié)點的Entry[]數(shù)組table賦值給t；
接著執(zhí)行一個while循環(huán)
while (index < t.length && (next = t[index++]) == null)
當(dāng)index大于table的長度，或者當(dāng)前t[index]位置保存的節(jié)點不為空時，將會結(jié)束while循環(huán)。也就是說該循環(huán)目的是為了找出table[]數(shù)組中第一個存儲了Entry對象的位置，并用index變量記錄該位置。
我們再總結(jié)一下！當(dāng)Itreator iter = map.entrySet().itreator();這句代碼結(jié)束之后，我們獲得了一個Iterator對象，這個對象保存了當(dāng)前hashMap的modCount值，index用于標(biāo)識table[]數(shù)組中第一個不為null的位置，同時next的初始值也等同于table[index]的值。
while(iter.hashNext())
當(dāng)前對象實際上為HashIterator對象，HashIterator對象的hasNext()方法十分的簡單
public final boolean hasNext() { return next != null;
}Map.entry entry = (Map.entry) iter.next();
再梳理一下邏輯，EntryIterator 有一個方法next
public Map.Entry next() { return nextEntry();
}final Entry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException();
Entry e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) {
Entry[] t = table; while (index < t.length && (next = t[index++]) == null)
;
}
current = e; return e;
}
如果modCount值不等于expectedModCount，表示在當(dāng)前遍歷過程中，HashMap可能被其他線程修改過，我們需要拋出ConcurrentModificationException異常，這也就是我們常說fast-fail。同時新建一個Entry節(jié)點e，賦值為next(第一次進(jìn)來是next指向的就是table[]數(shù)組中第一個不為null的頭結(jié)點)。
如果說當(dāng)前節(jié)點的下一個節(jié)點為null，相當(dāng)于遍歷到了當(dāng)前table[i]所指向鏈表的最后一個節(jié)點。此時我們應(yīng)當(dāng)去尋找table數(shù)組中下一個頭結(jié)點不為null的位置。
執(zhí)行while (index < t.length && (next = t[index++]) == null) 找到下一個不為null的頭結(jié)點，并保存到next節(jié)點中。
返回當(dāng)前節(jié)點e
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
名稱欄目：HashMap源碼閱讀與解析-創(chuàng)新互聯(lián)
標(biāo)題來源：
http://weahome.cn/article/dghiio.html
重慶分公司
重慶分公司
