最近忙于各種事情，只能陸陸續(xù)續(xù)也看了一些東西，Java的HashMap應(yīng)該算比較基礎(chǔ)的東西梅尤，也是最近在看<<Redis設(shè)計(jì)與實(shí)現(xiàn)>>展东，其中也有HashMap的數(shù)據(jù)結(jié)構(gòu)赔硫，又回去看了一下Java本身實(shí)現(xiàn)，這篇也就再記錄一下盐肃。
Java數(shù)據(jù)結(jié)構(gòu)中定義了Map接口爪膊，該接口有四個(gè)常用實(shí)現(xiàn)類：HashMap，?Hashtable砸王，LinkedHashMap和TreeMap推盛。
針對(duì)上面四個(gè)常用類簡(jiǎn)單的介紹一下：
1. Hashtable: 從下面的Java doc就可以看出，其本身是線程安全的谦铃，但是并發(fā)性不如concurrent中的ConcurrentHashMap耘成，而不需要線程安全時(shí)候，也推薦使用HashMap，故可以算是一個(gè)遺留類瘪菌，不推薦使用撒会。
2. LinkedHashMap：它是HashMap的一個(gè)子類，保存了記錄的插入順序师妙，在用Iterator遍歷LinkedHashMap時(shí)诵肛，先得到的記錄肯定是先插入的。
3. TreeMap：TreeMap實(shí)現(xiàn)SortedMap接口默穴，能夠把它保存的記錄根據(jù)鍵排序怔檩，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器蓄诽，當(dāng)用Iterator遍歷TreeMap時(shí)薛训，得到的記錄是排過序的。如果使用排序的映射若专，建議使用TreeMap许蓖。
4. HashMap：它根據(jù)鍵的hashCode值存儲(chǔ)數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值调衰，因而具有很快的訪問速度膊爪，但遍歷順序卻是不確定的。 HashMap最多只允許一條記錄的鍵為null嚎莉，允許多條記錄的值為null米酬。HashMap非線程安全，可能會(huì)導(dǎo)致數(shù)據(jù)的不一致趋箩。如果需要滿足線程安全赃额，可以使用之前提及的ConcurrentHashMap（不建議用Hashtable）。
本篇主要簡(jiǎn)單介紹的就是HashMap的實(shí)現(xiàn)叫确，也是由于HashMap是最最常用的一個(gè)跳芳，可以滿足大部分場(chǎng)景。自己工作了一年時(shí)間竹勉，基本也只用過HashMap= =
內(nèi)部結(jié)構(gòu)
HashMap內(nèi)部的數(shù)據(jù)結(jié)構(gòu)飞盆，就是最經(jīng)典的數(shù)組+鏈表實(shí)現(xiàn)的哈希桶（JDK 1.7之前)，從1.8之后次乓，鏈表節(jié)點(diǎn)數(shù)量滿足一定條件后吓歇，會(huì)自動(dòng)轉(zhuǎn)換成紅黑樹的數(shù)據(jù)結(jié)構(gòu)，進(jìn)一步提高查詢效率票腰。簡(jiǎn)單來說城看，HashMap的結(jié)構(gòu)就是一個(gè)指針數(shù)組。
圖中的黑點(diǎn)則是存放Key-Value的Node杏慰，其數(shù)據(jù)結(jié)構(gòu)如下：
其中 hash是用來定位數(shù)組索引位置测柠， next是鏈表的下一個(gè)node炼鞠。
字段
Map.put("key", "value")
在不考慮擴(kuò)容的情況下，put操作會(huì)首先計(jì)算key的hash值鹃愤，并通過取高位運(yùn)算 + 取模運(yùn)算兩步簇搅，就能計(jì)算出該key在哈希桶的位置了完域。
當(dāng)兩個(gè)key定位在了同一個(gè)位置软吐，則表示發(fā)生了Hash碰撞。因此吟税，良好的Hash算法凹耙，能夠盡量減少Hash碰撞，提高M(jìn)ap的存取效率肠仪。然而肖抱，即使很好的Hash算法，如果哈希桶的size很幸炀伞（相比于Node數(shù)量）意述，無論怎么計(jì)算，總是在這幾個(gè)位置吮蛹，也會(huì)出現(xiàn)很多碰撞荤崇。因此，解決碰撞潮针，不僅需要良好的Hash算法术荤，還需要一個(gè)良好的擴(kuò)容機(jī)制。
要討論擴(kuò)容機(jī)制每篷，就先看一下HashMap中的幾個(gè)字段(附默認(rèn)值)：
從上面幾個(gè)字段可以看出焦读，當(dāng)put操作子库，使得size > threshold時(shí)，HashMap就會(huì)發(fā)生擴(kuò)容矗晃。 并且從Java 動(dòng)doc可以看出仑嗅，Hash桶的大小一定是2的n次方。（正是這個(gè)限制喧兄，使得HashMap在擴(kuò)容和計(jì)算key位置的運(yùn)算效率提升了很多）
實(shí)現(xiàn)
Hash算法的實(shí)現(xiàn)无畔，其實(shí)只有下面三行代碼:
int hashcode = key.hashCode(); // 獲取hashcode
int hashInt = hashcode ^??(hashcode >>> 16 ); // 高位運(yùn)算
int index = hashInt & (length - 1) // 取模運(yùn)算，?lenght是數(shù)組大小
第二步通過hashCode()的高16位異或低16位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)吠冤，主要是從速度浑彰、功效、質(zhì)量來考慮的拯辙，這么做可以在數(shù)組table的length比較小的時(shí)候郭变，也能保證考慮到高低Bit都參與到Hash的計(jì)算中颜价，同時(shí)不會(huì)有太大的開銷。
第三步也是非常巧妙诉濒，因?yàn)長(zhǎng)enght是2的n次方周伦，因此length - 1 永遠(yuǎn)是n個(gè)1，其實(shí)相當(dāng)于對(duì)hashInt做了一次取模未荒，但是效率極高专挪。
下面是JDK 1.8的put代碼實(shí)現(xiàn):
line 627-628: table為空則創(chuàng)建.
line 629-630: 計(jì)算index，并且check null片排， 如果為null寨腔， 直接創(chuàng)建一個(gè)index;
line 633-635: 如果需要put的key和該位置原來的key一樣，則直接覆蓋value率寡， 否則進(jìn)行下面的追加操作
line 676-637: 紅黑樹操作迫卢，追加Node到紅黑樹
line 638-650: 鏈表操作，追加node到鏈表冶共，并且判斷是否需要轉(zhuǎn)化為紅黑樹乾蛤。
line 661-662: 判斷是否需要擴(kuò)容
擴(kuò)容機(jī)制
擴(kuò)容機(jī)制里的算法相對(duì)也比較復(fù)雜，HashMap的線程不安全性捅僵，也正是由于擴(kuò)容時(shí)家卖，鏈表操作可能導(dǎo)致的Infinite Loop引起。因此下一篇再具體舉例說明吧命咐。順便可以一起把redis的HashMap resize機(jī)制一起說一下篡九，基本都是大同小異。
總結(jié)
本篇就從源碼角度醋奠，簡(jiǎn)單講解HashMap的基本數(shù)據(jù)結(jié)構(gòu)和關(guān)鍵操做的實(shí)現(xiàn)榛臼，以及簡(jiǎn)單介紹了擴(kuò)容機(jī)制，由于JDK1.8以后的紅黑樹窜司，導(dǎo)致擴(kuò)容的代碼更加復(fù)雜沛善，但是擴(kuò)容的算法相對(duì)于1.8之前，也有了不少優(yōu)化塞祈，不過之后也不會(huì)深入算法方便金刁，主要還是會(huì)介紹擴(kuò)容的流程和原理。同事會(huì)結(jié)合redis的哈希表實(shí)現(xiàn)议薪。
