?????? 最近一直特別忙,好不容易閑下來(lái)了秧荆。準(zhǔn)備把HashMap的知識(shí)總結(jié)一下该镣，很久以前看過(guò)HashMap源碼祠墅。一直想把集合類的知識(shí)都總結(jié)一下侮穿，加深自己的基礎(chǔ)。我覺(jué)的java的集合類特別重要毁嗦，能夠深刻理解和應(yīng)用這些集合類能夠讓自己寫的程序上一步臺(tái)階亲茅。

??????? 本文主要根據(jù)自己學(xué)習(xí)與使用HashMap來(lái)解析HashMap的源碼，深入到HashMap的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)狗准，增強(qiáng)自己的基礎(chǔ)知識(shí)克锣。同時(shí)會(huì)借鑒網(wǎng)上的相關(guān)資料，深入理解HashMap.

HashMap的內(nèi)部存儲(chǔ)結(jié)構(gòu)

??????? 一提到HashMap我們就知道鍵值對(duì)腔长，即一個(gè)鍵對(duì)應(yīng)一個(gè)值袭祟。可能我們經(jīng)常會(huì)使用HashMap,但是并不關(guān)注里面的內(nèi)部實(shí)現(xiàn)捞附。今天我們就來(lái)學(xué)習(xí)一下HashMap的內(nèi)部實(shí)現(xiàn)巾乳。

???????? HashMap是一種以鍵值對(duì)存儲(chǔ)數(shù)據(jù)的容器，每個(gè)對(duì)象在java中都會(huì)有一個(gè)hashCode,HashMap正是借每個(gè)對(duì)象的HashCode來(lái)組織鍵值對(duì)的存儲(chǔ)鸟召，因?yàn)镠ashCode的特性胆绊，使得HashMap以非常快速和高效地地根據(jù)鍵值key進(jìn)行數(shù)據(jù)的存取欧募。鍵值對(duì)的具體實(shí)現(xiàn)在HashMap內(nèi)部會(huì)封裝成一個(gè)Entry[] table压状，Entry[] table是鍵值對(duì)的表現(xiàn)形式。下圖為HashMap的存儲(chǔ)結(jié)構(gòu)槽片。HashMap中Value可以相同何缓，但是鍵不可以相同.

?????? 上圖可以看出來(lái)HashMap是數(shù)組＋鏈表的存儲(chǔ)結(jié)構(gòu)肢础，數(shù)組的每一個(gè)元素是一個(gè)鏈表的表頭还栓。這樣的結(jié)構(gòu)能夠綜合2個(gè)經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)碌廓，數(shù)組查找、遍歷快剩盒，鏈表增加谷婆、刪除快。

HashMap的屬性

?????? static final int DEFAULT_INITIAL_CAPACITY = 16;//默認(rèn)初始化加載容量辽聊，即table數(shù)組的長(zhǎng)度纪挎。

?????? static final int MAXIMUM_CAPACITY = 1 << 30;//最大的容量。1左移30位跟匆，2的30次方：1073741824

?????? static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認(rèn)加載因子為0.75

?????? transient Entry[] table;//table數(shù)組异袄，上圖的黃色部分。Entry為藍(lán)色部分

?????? transient int size;//HashMap存儲(chǔ)元素的數(shù)量玛臂。

?????? int threshold;//閥值? table的長(zhǎng)度*加載因子（默認(rèn)wei0.75）

?????? final float loadFactor;//加載因子

?????? transient volatile int modCount;//修改次數(shù)

?????? 注：如果用transient聲明一個(gè)實(shí)例變量烤蜕，當(dāng)對(duì)象存儲(chǔ)時(shí)，它的值不需要維持迹冤。換句話來(lái)說(shuō)就? 是讽营，用transient關(guān)鍵字標(biāo)記的成員變量不參與序列化過(guò)程。

????????????? volatile為同步變量泡徙，保證每次都讀取的值是最新的橱鹏。

HashMap的構(gòu)造方法

??????? public HashMap() {//最常用的改造方法

????????????? this.loadFactor = DEFAULT_LOAD_FACTOR;//默認(rèn)加載因子，0.75

????????????? threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//閥值??? 默認(rèn)的容量*加載英子堪藐。12

????????????? table = new Entry[DEFAULT_INITIAL_CAPACITY];//table數(shù)組的默認(rèn)為16莉兰，容量為16，切記容量不等于HashMap存儲(chǔ)的元素?cái)?shù)量礁竞，容易混淆贮勃。

????????????? init();//初始化方法，里面是個(gè)空

????????? }

??????? 默認(rèn)的構(gòu)造方法開(kāi)辟16個(gè)大小的空間苏章。還有另外一個(gè)構(gòu)造方法我們使用的比較少寂嘉，當(dāng)你覺(jué)的默認(rèn)的HashMap的存儲(chǔ)空間浪費(fèi)時(shí)（容量達(dá)到3/4時(shí)HashMap就會(huì)調(diào)用resize擴(kuò)大為原來(lái)的2倍），可以使用下面一個(gè)枫绅。

?????? public HashMap(int initialCapacity, float loadFactor) {//初始化容量泉孩，加載因子

?????????????? if (initialCapacity < 0)//容量不能小于0

????????????????????? throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);

????????????? if (initialCapacity > MAXIMUM_CAPACITY)//大于允許最大的容量時(shí)，設(shè)置未最大值

????????????????????? initialCapacity = MAXIMUM_CAPACITY;

???????????? if (loadFactor <= 0 || Float.isNaN(loadFactor))//加載因子小于大于0或者不是數(shù)字的時(shí)候并淋，報(bào)非法加載因子異常

???????????? throw new IllegalArgumentException("Illegal load factor: " +

???????????? loadFactor);

???????????? // Find a power of 2 >= initialCapacity

??????????? int capacity = 1;

??????????? while (capacity < initialCapacity)//實(shí)際的開(kāi)辟的空間要大于傳入的第一個(gè)參數(shù)的值寓搬。

??????????? capacity <<= 1;//這是一個(gè)重點(diǎn)，capacity才是容量县耽。

??????????? this.loadFactor = loadFactor;//加載因子設(shè)置為傳入的值

??????????? threshold = (int)(capacity * loadFactor);//閾值

?????????? table = new Entry[capacity];//數(shù)組

?????????? init();

??????? }

???????? 此外還有2個(gè)構(gòu)造方法基本上很少用到句喷，感興趣的可以自己看看镣典。HashMap最重要的方法是put和get方法，下面我們重點(diǎn)看看這2個(gè)方法唾琼。

HashMap的put方法分析

???????? public V put(K key, V value) {//很熟悉的方法

????????????? if (key == null)//如果key==null兄春，直接設(shè)置空的

???????????????????? return putForNullKey(value);

????????????? int hash = hash(key.hashCode());//獲得hash值

????????????? int i = indexFor(hash, table.length);//根據(jù)hash值找到此鍵值對(duì)應(yīng)該放在數(shù)組的第幾個(gè)位置。

????????????? for (Entry e = table[i]; e != null; e = e.next) {//拿到放置該鍵值對(duì)的鏈表锡溯，

???????????????????? Object k;

????????????? if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//如果原來(lái)的存在赶舆，直接替換值

????????????????????? V oldValue = e.value;

????????????????????? e.value = value;

????????????????????? e.recordAccess(this);

????????????????????? return oldValue;

????????????????? }

?????????? }

?????????? modCount++;

?????????? addEntry(hash, key, value, i);//不存在就新增

????????? return null;

???? }

????????? put方法會(huì)先判斷鍵是不是空，如果為空就調(diào)putForNullKey方法祭饭。方法如下：

????????? private V putForNullKey(V value) {

??????????????? for (Entry e = table[0]; e != null; e = e.next) {//獲得第一個(gè)鏈表芜茵，遍歷查找是否原來(lái)就存儲(chǔ)為null的鍵值對(duì)

???????????????? if (e.key == null) {//如果存在

?????????????????????? V oldValue = e.value;//記錄下老的值

?????????????????????? e.value = value;//把新值設(shè)置進(jìn)去

?????????????????????? e.recordAccess(this);

?????????????????????? return oldValue;//返回老值

?????????????????? }

?????????????? }

???????????????? modCount++;

??????????????? addEntry(0, null, value, 0);//Key?為null,則將Entry放置到第一桶table[0]中

??????????????? return null;

???????? }

????????? 計(jì)算Hash值的方法如下：

?????????? static int hash(int h) {//根據(jù)特定的hashcode?重新計(jì)算hash值

????????????????????? h ^= (h >>> 20) ^ (h >>> 12);

?????????????????????? return h ^ (h >>> 7) ^ (h >>> 4);

????????????? }

??????????? static int indexFor(int h, int length) {//匹配到具體的桶當(dāng)中，

?????????????????????? return h & (length-1);//相當(dāng)于int i = hash %Entry[].length;得到i后倡蝙，就是在Entry數(shù)組中的位置

???????????? }

?????? 整個(gè)put方法的流程如下：

??????? 首先判斷鍵是否為空九串，如果為空在判斷是否已經(jīng)存在鍵為空的鍵值對(duì)，存在就更新值寺鸥，不存在就新增猪钮；

??????? 如果鍵不為空，則獲取這個(gè)Key的hashcode值析既，根據(jù)此值確定鍵值對(duì)的存儲(chǔ)位置躬贡；遍歷所在桶中的Entry鏈表，查找其中是否已經(jīng)有了以Key值為Key存儲(chǔ)的Entry對(duì)象眼坏，若已存在拂玻，定位到對(duì)應(yīng)的Entry,其中的Value值更新為新的Value值；返回舊值宰译；若不存在檐蚜，則根據(jù)鍵值對(duì) 創(chuàng)建一個(gè)新的Entry對(duì)象，然后添加到這個(gè)桶的Entry鏈表的頭部沿侈。當(dāng)前的HashMap的大小(即Entry節(jié)點(diǎn)的數(shù)目)是否超過(guò)了閥值闯第，若超過(guò)了閥值(threshold)，則增大HashMap的容量(即Entry[] table 的大小)缀拭，并且重新組織內(nèi)部各個(gè)Entry排列咳短。

HashMap的get方法分析

???????? public V get(Object key) {

????????????? if (key == null)//如果鍵等于null，調(diào)用getForNullKey

???????????????????? return getForNullKey();

???????????? int hash = hash(key.hashCode());//獲得hash值蛛淋，

???????????? for (Entry e = table[indexFor(hash, table.length)];

??????????????????? e != null;

???????????? e = e.next) {//indexfor計(jì)算存儲(chǔ)位置咙好，根據(jù)位置遍歷鏈表

??????????????????? Object k;

??????????? if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

??????????????????? return e.value;//拿到對(duì)應(yīng)的值

???????????? }

?????????????????? return null;

?????? }

???????? 如果鍵等于null，調(diào)用getForNullKey

???????? private V getForNullKey() {

???????????????? for (Entry e = table[0]; e != null; e = e.next) {//鍵為null的鍵值對(duì)存儲(chǔ)在數(shù)組的第一個(gè)元素褐荷，

???????????????? if (e.key == null)//如果存在則返回值

???????????????????????? return e.value;

??????????? }

??????????????????????? return null;//不存在返回null

}

?????? get方法比較簡(jiǎn)單勾效，比較容易理解。主要流程如下：

??????? 首先判斷鍵是否為空，如果為空在table[0]中取鍵為空的鍵值對(duì)层宫，如果不存在為空的則返回null杨伙。

??????? 如果鍵不為空，則獲取這個(gè)Key的hashcode值萌腿，根據(jù)此值確定該鍵值對(duì)的存儲(chǔ)位置限匣；遍歷所在桶中的Entry鏈表，查找其中是否已經(jīng)有了以Key值為Key存儲(chǔ)的Entry對(duì)象哮奇，若已存在膛腐，定位到對(duì)應(yīng)的Entry,獲得Value值睛约；返回舊值鼎俘；若不存在，則返回空辩涝。

HashMap的總結(jié)

??????? 本文主要講了HashMap的存儲(chǔ)結(jié)構(gòu)以及基本屬性贸伐、構(gòu)造方法，同時(shí)分析了比較常用的put和get方法怔揩。其他方法請(qǐng)讀者自行查看捉邢。在看HashMap的源碼時(shí)，我認(rèn)為以下幾個(gè)方面比較重要商膊，能夠理解到以下的幾點(diǎn)伏伐，搞定HashMap基本不成問(wèn)題。

???????? HashMap的存儲(chǔ)結(jié)構(gòu)晕拆，以及為什么要這樣進(jìn)行存儲(chǔ)藐翎。

???????? HashMap的各個(gè)屬性的含義，以及其擴(kuò)容的策略（擴(kuò)容算法）实幕。

???????? Hash值的計(jì)算.確定桶的位置吝镣。

???????? HashMap中的value可以相同，鍵不可以相同昆庇。

???????? HashMap是非線程安全的末贾。