1苗踪、hashmap 的數(shù)據(jù)結(jié)構(gòu)
要知道 hashmap 是什么，首先要搞清楚它的數(shù)據(jù)結(jié)構(gòu)荠割，在 java 編程語(yǔ)言中，最基本的結(jié)構(gòu)就是兩種旺矾，一個(gè)是數(shù)組蔑鹦，另外一個(gè)是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本結(jié)構(gòu)來(lái)構(gòu)造的箕宙，hashmap 也不例外嚎朽。Hashmap 實(shí)際上是一個(gè)數(shù)組和鏈表的結(jié)合體（在數(shù)據(jù)結(jié)構(gòu)中，一般稱(chēng)之為 “鏈表散列 “）柬帕，請(qǐng)看下圖（橫排表示數(shù)組哟忍，縱排表示數(shù)組元素【實(shí)際上是一個(gè)鏈表】）。
從圖中我們可以看到一個(gè) hashmap 就是一個(gè)數(shù)組結(jié)構(gòu)陷寝，當(dāng)新建一個(gè) hashmap 的時(shí)候锅很，就會(huì)初始化一個(gè)數(shù)組。我們來(lái)看看 java 代碼：
/**
* The table, resized as necessary. Length MUST Always be a power of two.
* FIXME 這里需要注意這句話凤跑，至于原因后面會(huì)講到
*/
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
..........
}
上面的 Entry 就是數(shù)組中的元素爆安，它持有一個(gè)指向下一個(gè)元素的引用，這就構(gòu)成了鏈表仔引。
當(dāng)我們往 hashmap 中 put 元素的時(shí)候扔仓，先根據(jù) key 的 hash 值得到這個(gè)元素在數(shù)組中的位置（即下標(biāo)），然后就可以把這個(gè)元素放到對(duì)應(yīng)的位置中了咖耘。如果這個(gè)元素所在的位子上已經(jīng)存放有其他元素了翘簇，那么在同一個(gè)位子上的元素將以鏈表的形式存放，新加入的放在鏈頭儿倒，最先加入的放在鏈尾版保。從 hashmap 中 get 元素時(shí)，首先計(jì)算 key 的 hashcode，找到數(shù)組中對(duì)應(yīng)位置的某一元素找筝，然后通過(guò) key 的 equals 方法在對(duì)應(yīng)位置的鏈表中找到需要的元素蹈垢。從這里我們可以想象得到，如果每個(gè)位置上的鏈表只有一個(gè)元素袖裕，那么 hashmap 的 get 效率將是最高的，但是理想總是美好的溉瓶，現(xiàn)實(shí)總是有困難需要我們?nèi)タ朔宾?/p>
2、hash 算法
我們可以看到在 hashmap 中要找到某個(gè)元素堰酿，需要根據(jù) key 的 hash 值來(lái)求得對(duì)應(yīng)數(shù)組中的位置疾宏。如何計(jì)算這個(gè)位置就是 hash 算法。前面說(shuō)過(guò) hashmap 的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合触创，所以我們當(dāng)然希望這個(gè) hashmap 里面的元素位置盡量的分布均勻些坎藐，盡量使得每個(gè)位置上的元素?cái)?shù)量只有一個(gè)，那么當(dāng)我們用 hash 算法求得這個(gè)位置的時(shí)候哼绑，馬上就可以知道對(duì)應(yīng)位置的元素就是我們要的岩馍，而不用再去遍歷鏈表。
所以我們首先想到的就是把 hashcode 對(duì)數(shù)組長(zhǎng)度取模運(yùn)算抖韩，這樣一來(lái)蛀恩，元素的分布相對(duì)來(lái)說(shuō)是比較均勻的。但是茂浮，“乃唬” 運(yùn)算的消耗還是比較大的，能不能找一種更快速席揽，消耗更小的方式那顽馋？java 中時(shí)這樣做的，
static int indexFor(int h, int length) {
return h & (length-1);
}
首先算得 key 得 hashcode 值幌羞，然后跟數(shù)組的長(zhǎng)度 - 1 做一次 “與” 運(yùn)算（&）寸谜。看上去很簡(jiǎn)單新翎，其實(shí)比較有玄機(jī)程帕。比如數(shù)組的長(zhǎng)度是 2 的 4 次方，那么 hashcode 就會(huì)和 2 的 4 次方 - 1 做 “與” 運(yùn)算地啰。很多人都有這個(gè)疑問(wèn)愁拭，為什么 hashmap 的數(shù)組初始化大小都是 2 的次方大小時(shí)，hashmap 的效率最高亏吝，我以 2 的 4 次方舉例岭埠，來(lái)解釋一下為什么數(shù)組大小為 2 的冪時(shí) hashmap 訪問(wèn)的性能最高。
看下圖，左邊兩組是數(shù)組長(zhǎng)度為 16（2 的 4 次方）惜论，右邊兩組是數(shù)組長(zhǎng)度為 15许赃。兩組的 hashcode 均為 8 和 9，但是很明顯馆类，當(dāng)它們和 1110 “與” 的時(shí)候混聊，產(chǎn)生了相同的結(jié)果，也就是說(shuō)它們會(huì)定位到數(shù)組中的同一個(gè)位置上去乾巧，這就產(chǎn)生了碰撞句喜，8 和 9 會(huì)被放到同一個(gè)鏈表上，那么查詢(xún)的時(shí)候就需要遍歷這個(gè)鏈表沟于，得到 8 或者 9咳胃，這樣就降低了查詢(xún)的效率。同時(shí)旷太，我們也可以發(fā)現(xiàn)展懈，當(dāng)數(shù)組長(zhǎng)度為 15 的時(shí)候，hashcode 的值會(huì)與 14（1110）進(jìn)行 “與”供璧，那么最后一位永遠(yuǎn)是 0存崖，而 0001，0011嗜傅，0101金句，1001，1011吕嘀，0111违寞，1101 這幾個(gè)位置永遠(yuǎn)都不能存放元素了，空間浪費(fèi)相當(dāng)大偶房，更糟的是這種情況中趁曼，數(shù)組可以使用的位置比數(shù)組長(zhǎng)度小了很多，這意味著進(jìn)一步增加了碰撞的幾率棕洋，減慢了查詢(xún)的效率挡闰！
所以說(shuō)，當(dāng)數(shù)組長(zhǎng)度為 2 的 n 次冪的時(shí)候掰盘，不同的 key 算得得 index 相同的幾率較小摄悯，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說(shuō)碰撞的幾率小愧捕，相對(duì)的奢驯，查詢(xún)的時(shí)候就不用遍歷某個(gè)位置上的鏈表，這樣查詢(xún)效率也就較高了次绘。
說(shuō)到這里瘪阁，我們?cè)倩仡^看一下 hashmap 中默認(rèn)的數(shù)組大小是多少撒遣，查看源代碼可以得知是 16，為什么是 16管跺，而不是 15义黎，也不是 20 呢，看到上面 annegu 的解釋之后我們就清楚了吧豁跑，顯然是因?yàn)?16 是 2 的整數(shù)次冪的原因廉涕，16-1的二進(jìn)制是 1 1 1 1 ，能夠盡量報(bào)錯(cuò)hash值的結(jié)果艇拍，在小數(shù)據(jù)量的情況下 16 比 15 和 20 更能減少 key 之間的碰撞火的，而加快查詢(xún)的效率。
所以淑倾，在存儲(chǔ)大容量數(shù)據(jù)的時(shí)候，最好預(yù)先指定 hashmap 的 size 為 2 的整數(shù)次冪次方征椒。就算不指定的話娇哆，也會(huì)以大于且最接近指定值大小的 2 次冪來(lái)初始化的，代碼如下 (HashMap 的構(gòu)造方法中)：
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
3勃救、hashmap 的 resize
當(dāng) hashmap 中的元素越來(lái)越多的時(shí)候碍讨，碰撞的幾率也就越來(lái)越高（因?yàn)閿?shù)組的長(zhǎng)度是固定的），所以為了提高查詢(xún)的效率蒙秒，就要對(duì) hashmap 的數(shù)組進(jìn)行擴(kuò)容勃黍，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在 ArrayList 中，所以這是一個(gè)通用的操作晕讲，很多人對(duì)它的性能表示過(guò)懷疑覆获，不過(guò)想想我們的 “均攤” 原理，就釋然了瓢省，而在 hashmap 數(shù)組擴(kuò)容之后弄息，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去勤婚，這就是 resize摹量。
那么 hashmap 什么時(shí)候進(jìn)行擴(kuò)容呢？當(dāng) hashmap 中的元素個(gè)數(shù)超過(guò)數(shù)組大小 * loadFactor 時(shí)馒胆，就會(huì)進(jìn)行數(shù)組擴(kuò)容缨称，loadFactor 的默認(rèn)值為 0.75，也就是說(shuō)，默認(rèn)情況下煮嫌，數(shù)組大小為 16宇攻，那么當(dāng) hashmap 中元素個(gè)數(shù)超過(guò) 16*0.75=12 的時(shí)候，就把數(shù)組的大小擴(kuò)展為 2*16=32骂删，即擴(kuò)大一倍掌动，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作宁玫，所以如果我們已經(jīng)預(yù)知 hashmap 中元素的個(gè)數(shù)粗恢，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高 hashmap 的性能。比如說(shuō)欧瘪，我們有 1000 個(gè)元素 new HashMap (1000), 但是理論上來(lái)講 new HashMap (1024) 更合適眷射，不過(guò)上面 annegu 已經(jīng)說(shuō)過(guò)，即使是 1000佛掖，hashmap 也自動(dòng)會(huì)將其設(shè)置為 1024妖碉。 但是 new HashMap (1024) 還不是更合適的，因?yàn)?0.75*1000 < 1000, 也就是說(shuō)為了讓 0.75 * size > 1000, 我們必須這樣 new HashMap (2048) 才最合適芥被，既考慮了 & 的問(wèn)題欧宜，也避免了 resize 的問(wèn)題。
- 如果需要擴(kuò)容拴魄，調(diào)用擴(kuò)容的方法 resize ()
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//判斷是否有超出擴(kuò)容的最大值冗茸，如果達(dá)到最大值則不進(jìn)行擴(kuò)容操作
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// transfer()方法把原數(shù)組中的值放到新數(shù)組中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//設(shè)置hashmap擴(kuò)容后為新的數(shù)組引用
table = newTable;
//設(shè)置hashmap擴(kuò)容新的閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
- transfer () 在實(shí)際擴(kuò)容時(shí)候把原來(lái)數(shù)組中的元素放入新的數(shù)組中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//通過(guò)key值的hash值和新數(shù)組的大小算出在當(dāng)前數(shù)組中的存放位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
4、key 的 hashcode 與 equals 方法改寫(xiě)
在第一部分 hashmap 的數(shù)據(jù)結(jié)構(gòu)中匹中，就寫(xiě)了 get 方法的過(guò)程：首先計(jì)算 key 的 hashcode夏漱，找到數(shù)組中對(duì)應(yīng)位置的某一元素，然后通過(guò) key 的 equals 方法在對(duì)應(yīng)位置的鏈表中找到需要的元素顶捷。所以挂绰，hashcode 與 equals 方法對(duì)于找到對(duì)應(yīng)元素是兩個(gè)關(guān)鍵方法。
Hashmap 的 key 可以是任何類(lèi)型的對(duì)象服赎，例如 User 這種對(duì)象葵蒂，為了保證兩個(gè)具有相同屬性的 user 的 hashcode 相同，我們就需要改寫(xiě) hashcode 方法专肪，比方把 hashcode 值的計(jì)算與 User 對(duì)象的 id 關(guān)聯(lián)起來(lái)刹勃，那么只要 user 對(duì)象擁有相同 id，那么他們的 hashcode 也能保持一致了嚎尤，這樣就可以找到在 hashmap 數(shù)組中的位置了荔仁。如果這個(gè)位置上有多個(gè)元素，還需要用 key 的 equals 方法在對(duì)應(yīng)位置的鏈表中找到需要的元素芽死，所以只改寫(xiě)了 hashcode 方法是不夠的乏梁，equals 方法也是需要改寫(xiě)滴～當(dāng)然啦，按正常思維邏輯关贵，equals 方法一般都會(huì)根據(jù)實(shí)際的業(yè)務(wù)內(nèi)容來(lái)定義遇骑，例如根據(jù) user 對(duì)象的 id 來(lái)判斷兩個(gè) user 是否相等。
在改寫(xiě) equals 方法的時(shí)候揖曾，需要滿(mǎn)足以下三點(diǎn)：
(1) 自反性：就是說(shuō) a.equals (a) 必須為 true落萎。
(2) 對(duì)稱(chēng)性：就是說(shuō) a.equals (b)=true 的話亥啦，b.equals (a) 也必須為 true。
(3) 傳遞性：就是說(shuō) a.equals (b)=true练链，并且 b.equals (\c)=true 的話翔脱，a.equals (\c) 也必須為 true。
通過(guò)改寫(xiě) key 對(duì)象的 equals 和 hashcode 方法媒鼓，我們可以將任意的業(yè)務(wù)對(duì)象作為 map 的 key (前提是你確實(shí)有這樣的需要)届吁。
總結(jié)：
本文主要描述了 HashMap 的結(jié)構(gòu)，和 hashmap 中 hash 函數(shù)的實(shí)現(xiàn)绿鸣，以及該實(shí)現(xiàn)的特性疚沐，同時(shí)描述了 hashmap 中 resize 帶來(lái)性能消耗的根本原因，以及將普通的域模型對(duì)象作為 key 的基本要求潮模。尤其是 hash 函數(shù)的實(shí)現(xiàn)亮蛔，可以說(shuō)是整個(gè) HashMap 的精髓所在，只有真正理解了這個(gè) hash 函數(shù)擎厢，才可以說(shuō)對(duì) HashMap 有了一定的理解尔邓。
