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