簡書 賈小強
轉(zhuǎn)載請注明原創(chuàng)出處浦夷，謝謝辖试！
大多數(shù)人應(yīng)該會同意HashMap是現(xiàn)在面試最喜歡問的主題之一。我和同事常常進行討論劈狐，并很有幫助」扌ⅲ現(xiàn)在，我繼續(xù)和大家討論肥缔。
我假設(shè)你對HashMap的內(nèi)部工作原理感興趣莲兢，并且你已經(jīng)知道基本的HashMap使用，所以我跳過這部分续膳。但如果HashMap的概念你覺得很新改艇，那么參考官方 Java docs。
在繼續(xù)之前坟岔，我強烈建議你閱讀我以前的帖子：使用hashCode()和equals()方法 - Java
本文包括如下內(nèi)容：
- 一句話回答
- 什么是Hashing谒兄？
- 關(guān)于
Entry類 - put()方法到底干了什么
- get()方法內(nèi)部是如何工作的
- 注意事項
- [更新 ] Java8改進
一句話回答
如果有人問我“描述下HashMap怎么工作的？我會簡單地回答：“按Hash原理”社付，如此簡單而已承疲。但要詳細回答這個問題，那么你必須非常清楚地知道Hash的基本知識鸥咖，對嗎燕鸽？？
什么是Hashing
最簡單形式的散列（Hashing）是一種根據(jù)任何變量/對象對其屬性扛或，應(yīng)用任何公式/算法后分配一個獨特的數(shù)字的方法绵咱。一個真正的散列函數(shù)必須遵循以下規(guī)則：
當函數(shù)在相同或相等的對象上應(yīng)用時，哈希函數(shù)應(yīng)該每次返回相同的哈希碼。換句話說悲伶，兩個相等的對象必須一致地生成相同的哈希碼艾恼。
所有Java中的對象都從Object類繼承一個默認得hashCode()方法實現(xiàn)。這個函數(shù)通過將對象的內(nèi)部地址轉(zhuǎn)換成整數(shù)來產(chǎn)生哈希碼麸锉，從而為所有不同的對象生成不同的哈希碼钠绍。
關(guān)于Entry類
Map的定義是：“一個將key映射到value的對象”。很容易..對嗎花沉？
因此柳爽，必然在HashMap類中有一些機制存儲鍵值對〖钇ǎ回答是肯定的磷脯，HashMap有一個內(nèi)部類Entry，它看起來像這樣：
static class Entry<K ,V> implements Map.Entry<K ,V>
{
final K key;
V value;
Entry<K ,V> next;
final int hash;
...//More code goes here
}
Entry類具有key和value的映射娩脾，并作為字段存儲赵誓。key已被標記為final，另外它還有兩個別的字段：next和hash柿赊。在下面俩功，我們將努力理解為什么需要這些字段。
put()方法到底干了什么
理解put()方法的實現(xiàn)之前碰声，先需要知道Entry類型的對象存儲在一個Entry類型數(shù)組中诡蜓。HashMap類如下定義這個數(shù)組：
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
現(xiàn)在看put()方法的代碼實現(xiàn)：
/**
* Associates the specified value with the specified key in this map. If the
* map previously contained a mapping for the key, the old value is
* replaced.
*
* @param key
* key with which the specified value is to be associated
* @param value
* value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
* if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
* can also indicate that the map previously associated
* <tt>null</tt> with <tt>key</tt>.)
*/
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;
}
讓我們逐一解釋以上步驟：
- 首先，檢查key是否為null胰挑。如果key為null蔓罚，則將value存儲在table[0]。因為null的哈希碼總是0洽腺。
- 然后脚粟，通過調(diào)用key的hashCode()方法得到一個哈希碼。此哈希碼用于計算
Entry對象存儲在Entry[]數(shù)組中的索引蘸朋。JDK的設(shè)計師認為核无，可能有一些寫得不好的hashCode()函數(shù)可以返回非常高或低的哈希碼。為了解決這個問題藕坯，他們推出了另一hash()函數(shù)团南，并通過將key對象的哈希碼傳給這個hash()函數(shù)，從而在數(shù)組索引的大小范圍獲得哈希碼炼彪。 - 現(xiàn)在吐根，indexFor(hash, table.length)函數(shù)被用來計算存儲
Entry對象的準確索引位置。 - 現(xiàn)在辐马，來到for循環(huán)部分拷橘。正如我們所知道的，兩個不等的對象可以有相同的哈希碼，兩個不同的對象如何存儲在同一個數(shù)組位置（稱為桶）冗疮。
答案是LinkedList萄唇。如果您記得，Entry類有一個屬性“next”术幔。這個屬性總是指向鏈中的下一個對象另萤。這正是鏈表的行為。
因此诅挑，在發(fā)生碰撞的時候四敞，Entry對象以鏈表的形式存儲。當一個Entry對象需要存儲在特定的索引位置拔妥，HashMap檢查是否已經(jīng)有一個Entry了忿危？如果沒有存在，那么Entry對象存儲在這個位置毒嫡。
如果已經(jīng)有一個Entry對象存儲在所計算的索引位置上癌蚁，那么它的next屬性就被檢查了幻梯。如果它為null兜畸，那么當這個Entry對象成為LinkedList的下一個節(jié)點。如果下一個變量不是null碘梢，則繼續(xù)執(zhí)行該過程咬摇，直到下一個位置的值為null為止。
如果我們增加一個key和value到和之前Entry對象相同的對象呢煞躬？從邏輯上說撑螺，它會取代舊value指黎。它是怎么做的？好了，首先確定Entry對象的儲存的索引位置后边器，對在鏈表中的每個對象，調(diào)用它們的equal()方法裙秋。LinkedList上的所有這些Entry對象將有類似的哈希碼牺堰，但equals()方法將測試它們是否真的相等。如果key.equals(k)為真搅裙，則這兩個鍵被視為同一個鍵對象皱卓。這將導(dǎo)致只替換Entry對象中的value對象。
也就說hashCode()方法在名叫table的Entry數(shù)組上找位置部逮，equal()方法在桶鏈表上找位置
通過這樣娜汁，HashMap保證了所有鍵的唯一性。
get()方法內(nèi)部是如何工作的
現(xiàn)在我們知道了鍵值對(key-value pairs)怎么存儲在HashMap中的兄朋。接下來的問題是：當一個對象被傳遞給HashMap的get方法發(fā)生了什么掐禁？值對象是如何確定返回的？
答案我們已經(jīng)知道，正如在put()法中唯一鍵的確定的方式傅事，同樣的邏輯應(yīng)用于get()方法中宫盔。HashMap根據(jù)傳遞的對象作作為鍵，精確匹配享完，它只是返回存儲于當前Entry對象中的值灼芭。
如果沒有發(fā)現(xiàn)匹配，get()方法返回null般又。
讓我們看看代碼：
/**
* Returns the value to which the specified key is mapped, or {@code null}
* if this map contains no mapping for the key.
*
* <p>
* More formally, if this map contains a mapping from a key {@code k} to a
* value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* </p><p>
* A return value of {@code null} does not <i>necessarily</i> indicate that
* the map contains no mapping for the key; it's also possible that the map
* explicitly maps the key to {@code null}. The {@link #containsKey
* containsKey} operation may be used to distinguish these two cases.
*
* @see #put(Object, Object)
*/
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;
}
注意事項
- 存儲
Entry對象的數(shù)據(jù)結(jié)構(gòu)是一個名為table的Entry類型數(shù)組彼绷。 - 數(shù)組在特定位置的索引被稱為桶，因為它可以保存一個
Entry類型對象鏈表的第一個元素茴迁。 - Key對象需要hashCode()方法寄悯，用于計算
Entry對象的存放索引位置。 - Key對象的equals()法用來確保key在
Map中的唯一性堕义。 - Value對象的的hashCode()和equals()方法在
HashMap的get()和put()方法中不會被使用猜旬。 - null鍵的哈希代碼總是0，而對應(yīng)的
Entry對象總是存儲在Entry數(shù)組的零索引位置倦卖。
[更新]Java 8改進
作為JEP 180的一部分洒擦，有一個對HashMap的性能改進，假如key對象有許多碰撞怕膛，則使用平衡樹而不是鏈表來存儲Entry對象熟嫩。其主要思想是，一旦哈希桶中的項目數(shù)量超出某個閾值時褐捻，該桶將從使用鏈接切換到使用平衡樹掸茅。在hash高碰撞的情況下，這將把最壞情況下的性能從O（n）改善到O（log n）柠逞。
基本上昧狮，當一桶太大（目前：treeify_threshold = 8），HashMap用tree map動態(tài)替換它板壮。這樣就不再是O（n）逗鸣，到是更好的O（log n）。
我希望通過這篇文章我能正確地表達我的想法个束。如果您發(fā)現(xiàn)有任何差異或需要任何幫助慕购，請發(fā)表評論。
Happy Learning !!
