本文分析HashMap的實(shí)現(xiàn)原理定踱。
數(shù)據(jù)結(jié)構(gòu)（散列表）
HashMap是一個(gè)散列表（也叫哈希表），用來存儲(chǔ)鍵值對(duì)(key-value)映射翩概。散列表是一種數(shù)組和鏈表的結(jié)合體汪疮，結(jié)構(gòu)圖如下：
簡(jiǎn)單來說散列表就是一個(gè)數(shù)組（上圖縱向），數(shù)組的每個(gè)元素是一個(gè)鏈表（上圖橫向）烂叔，類似二維數(shù)組谨胞。鏈表的每個(gè)節(jié)點(diǎn)就是我們存儲(chǔ)的key-value數(shù)據(jù)（源碼中將key和value封裝成Entry對(duì)象作為鏈表的節(jié)點(diǎn)）固歪。
哈希算法
對(duì)于散列表蒜鸡，不管是存值還是取值胯努，都需要通過Key來定位散列表中的一個(gè)具體的位置（即某個(gè)鏈表的某個(gè)節(jié)點(diǎn)），計(jì)算這個(gè)位置的方法就是哈希算法逢防。
大概過程是這樣的：
- 用Key的hash值對(duì)數(shù)組長(zhǎng)度做取余操作得到一個(gè)整數(shù)叶沛，這個(gè)整數(shù)作為數(shù)組中的索引得到這個(gè)索引位置的鏈表。
- 得到鏈表之后忘朝，就可以存值和取值了灰署。
如果是存值，直接把數(shù)據(jù)插入到鏈表的頭部或者尾部即可（或者已存在就替換）局嘁；
如果是取值溉箕，就遍歷鏈表，通過key的equals方法找到具體的節(jié)點(diǎn)悦昵。
例如一個(gè)key-value對(duì)要存到上圖的散列表里肴茄，假設(shè)key的哈希值是17，由圖可知（縱向）數(shù)組長(zhǎng)度是16但指，那么17對(duì)16取余結(jié)果是1寡痰，數(shù)組中索引1位置的鏈表是 1->337->353 ，所以這個(gè)key-value對(duì)存儲(chǔ)到這個(gè)鏈表里面（插到頭還是尾可能不同Java版本不一樣）棋凳。如果是取值拦坠，就遍歷這個(gè)鏈表，由于這個(gè)鏈表每個(gè)節(jié)點(diǎn)的key的哈希值都一樣剩岳，所以根據(jù)equals方法來確定具體是哪個(gè)節(jié)點(diǎn)贞滨。
通過上面的哈希算法，可以有如下結(jié)論：
- 不同的key具體相同的哈希值叫做哈希沖突拍棕，HashMap解決哈希沖突的方法是鏈表法疲迂，將具有相同哈希值的key放在同一個(gè)鏈表中，然后利用key類的equals方法來確定具體是哪個(gè)節(jié)點(diǎn)莫湘。
- Key的唯一性是通過哈希值和equals方法共同決定的尤蒿，所以想要用一個(gè)類作為HashMap的鍵，必須重寫這個(gè)類的hashCode和equals方法幅垮。同理腰池，HashSet是基于HashMap實(shí)現(xiàn)的，它沒有重復(fù)元素的特點(diǎn)是利用HashMap沒有重復(fù)鍵實(shí)現(xiàn)的忙芒。所以示弓，Set集合里面的元素類，也必須同時(shí)實(shí)現(xiàn)hashCode方法和equals方法呵萨。
- HashMap存儲(chǔ)的數(shù)據(jù)是無序的奏属。
為什么HashMap大小是2的整數(shù)次冪的時(shí)候效率最高
哈希算法主要分兩步操作：1.通過哈希值定位一個(gè)鏈表； 2.遍歷鏈表潮峦，通過equals方法找到具體節(jié)點(diǎn)囱皿。為了使哈希算法效率最高勇婴，應(yīng)該盡量讓數(shù)據(jù)在哈希表中均勻分布，因?yàn)槟菢涌梢员苊獬霈F(xiàn)過長(zhǎng)的鏈表嘱腥，也就降低了遍歷鏈表的代價(jià)耕渴。
如何保證均勻分布？前面的哈希算法說到齿兔，通過取余操作將Key的哈希值轉(zhuǎn)換成數(shù)組下標(biāo)橱脸，這樣可以認(rèn)為是均勻的。但是分苇，源碼中并沒有直接用%操作符取余添诉，而是使用了更高效的與運(yùn)算，源碼如下：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
這樣就多了一些限制医寿，因?yàn)橹挥挟?dāng)length是2的整數(shù)次冪的時(shí)候吻商，h & (length-1) = h % length才成立。當(dāng)然糟红，如果length不是2的整數(shù)次冪艾帐，h & (length-1)的結(jié)果也一定比length小，將Key轉(zhuǎn)換成數(shù)組下標(biāo)也沒什么問題盆偿，但是柒爸，這樣會(huì)導(dǎo)致元素分布不均勻嚴(yán)重影響散列表的訪問效率∈屡ぃ看下面的一個(gè)示例代碼：
解釋一下圖中的代碼捎稚，隨機(jī)生成一組Key，然后利用與運(yùn)算求橄，把key全部轉(zhuǎn)換成一個(gè)數(shù)組容量的索引今野，這樣就得到一組索引值，這組索引中不相同的值越多罐农，說明分布越均勻条霜，輸出結(jié)果的result就是 “這組索引中不相同的值的數(shù)量”。
從運(yùn)行結(jié)果來看涵亏，容量是64的時(shí)候相比于其他幾個(gè)容量大小宰睡，分布是最均勻的。容量是65的時(shí)候气筋，每次結(jié)果都是2拆内，原因很簡(jiǎn)單，當(dāng)容量是65的時(shí)候宠默，下標(biāo)=h&64麸恍，64的二進(jìn)制是1000000，很明顯搀矫，與它進(jìn)行與運(yùn)算的結(jié)果只有兩種情況抹沪，0和64刻肄，也就是說，如果HashMap大小被指定成65采够，對(duì)于任意Key肄方，只會(huì)存儲(chǔ)到散列表數(shù)組的第0個(gè)或第64個(gè)鏈表中冰垄，浪費(fèi)了63個(gè)空間蹬癌，同時(shí)也導(dǎo)致0和64兩個(gè)鏈表過長(zhǎng)，取值的時(shí)候遍歷鏈表的代價(jià)很高虹茶。容量66和67的結(jié)果是4同理逝薪。如果容量是64，那么下標(biāo)=h&63蝴罪，63的二進(jìn)制是111111董济，每一位都是1，好處就是對(duì)于任意Key要门，與63做與運(yùn)算的結(jié)果可能是1-63的任意數(shù)虏肾，很多Key的話自然就能分布均勻。
通過這個(gè)示例代碼的分析就可以找到一個(gè)規(guī)律了欢搜，容量length=2^n 是分布最均勻封豪，因?yàn)閘ength-1的二進(jìn)制每一位都是1；相反的length=2^n+1是分布最不均勻的炒瘟，因?yàn)閘ength-1的二進(jìn)制中的1數(shù)量最少吹埠。
結(jié)論：HashMap大小是2的整數(shù)次冪的時(shí)候效率最高，因?yàn)檫@個(gè)時(shí)候元素在散列表中的分布最均勻疮装。
從上面的分析來看缘琅，使用與運(yùn)算雖然效率高了，但是增加了使用限制廓推，如果用%取余的做法刷袍，那么對(duì)于任何大小的容量都能做到均勻分布，可以把圖中代碼int a = keySet[j] & (c - 1); 改成 int a = keySet[j] % c;試一下樊展。
HashMap的容量
通過上面的分析做个，容量是2的整數(shù)次冪的時(shí)候效率最高，那么很容易想到滚局，如果隨著數(shù)據(jù)量的增長(zhǎng)居暖，HashMap需要擴(kuò)容的時(shí)候是2倍擴(kuò)容，區(qū)別于ArrayList的1.5倍擴(kuò)容藤肢。
那么什么時(shí)候擴(kuò)容呢太闺？首先說明一下，我們所說的HashMap的容量是指散列表中數(shù)組的大小嘁圈，這個(gè)大小不能決定HashMap能存多少數(shù)據(jù)省骂，因?yàn)橹灰湵碜銐蜷L(zhǎng)蟀淮，存多少數(shù)據(jù)都沒問題。但是钞澳，數(shù)據(jù)量很大的時(shí)候怠惶，如果數(shù)組太小，就會(huì)導(dǎo)致鏈表很長(zhǎng)轧粟，get元素的效率就會(huì)降低策治，所以我們應(yīng)該在適當(dāng)?shù)臅r(shí)候擴(kuò)容。源碼默認(rèn)的做法是兰吟，當(dāng)數(shù)據(jù)量達(dá)到容量的75%的時(shí)候擴(kuò)容通惫，這個(gè)值稱為負(fù)載因子，75%應(yīng)該是大量實(shí)驗(yàn)后統(tǒng)計(jì)得到的最優(yōu)值混蔼，沒有特殊情況不要通過構(gòu)造方法指定為其他值履腋。
擴(kuò)容是有代價(jià)了，會(huì)導(dǎo)致所有已存的數(shù)據(jù)重新計(jì)算位置惭嚣，所以遵湖，和ArrayList一樣，當(dāng)知道大概的數(shù)據(jù)量的時(shí)候晚吞，可以指定HashMap的大小盡量避免擴(kuò)容延旧，指定大小要注意75%這個(gè)負(fù)載因子，比如數(shù)據(jù)量是63個(gè)的話载矿，HashMap的大小應(yīng)該是128而不是64垄潮。
對(duì)于容量的計(jì)算，源碼已經(jīng)封裝好了一個(gè)方法
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
此方法在HashMap的構(gòu)造方法中被調(diào)用闷盔，所以指定容量的時(shí)候無需自己計(jì)算弯洗，比如數(shù)據(jù)量是63，直接new HashMap<>(63)即可逢勾。
HashMap的遍歷
前面提到一點(diǎn)牡整，散列表中的鏈表的節(jié)點(diǎn)是Entry對(duì)象，通過Entry對(duì)象可以得到Key和Value溺拱。HashMap的遍歷方法有很多逃贝，大概可以分為3種，分別是通過map.entrySet()迫摔、map.keySet()沐扳、map.values()三種方式遍歷。比較效率的話句占，map.values()方式無法得到key沪摄，這里不考慮。比較map.entrySet()和map.keySet()的話，結(jié)合散列表的結(jié)構(gòu)特點(diǎn)杨拐，很明顯map.entrySet()直接遍歷Entry集合（所有鏈表節(jié)點(diǎn)）取出Key和Value即可（一次循環(huán)）祈餐，map.keySet()遍歷的是Key，得到Key之后在通過Key去遍歷相應(yīng)的鏈表找到具體的節(jié)點(diǎn)（多個(gè)循環(huán)）哄陶，所以前者效率高帆阳。
擴(kuò)展：LinkedHashMap和LruCatch
對(duì)于LinkedHashMap的理解，我覺得一張圖就夠了：
在散列表的基礎(chǔ)上加上了雙向循環(huán)鏈表（圖中黃色箭頭和綠色箭頭）屋吨，所以可以拆分成一個(gè)散列表和一個(gè)雙向鏈表蜒谤，雙向鏈表如下：
然后使用散列表操作數(shù)據(jù)，使用雙向循環(huán)鏈表維護(hù)順序离赫，就實(shí)現(xiàn)了LinkedHashMap芭逝。
LinkedHashMap有一個(gè)屬性可以設(shè)置兩種排序方式：
private final boolean accessOrder;
false表示插入順序塌碌，true表示最近最少使用次序渊胸，后者就是LruCatch的實(shí)現(xiàn)原理。
LinkedHashMap和LruCatch的具體實(shí)現(xiàn)細(xì)節(jié)這里就不分析了台妆。
