HashMap概述

Hash，又稱散列。哈希表是一種以鍵-值(key-value) 存儲(chǔ)數(shù)據(jù)的，和數(shù)組、鏈表、二叉樹等同樣典型的一種數(shù)據(jù)結(jié)構(gòu)。Java中用HashMap來實(shí)現(xiàn)了哈希表這種數(shù)據(jù)結(jié)構(gòu)。

內(nèi)部實(shí)現(xiàn)

前言 - hashCode()和equals(obj)方法
java.lang.Object中的方法定義

/** JNI，調(diào)用底層其它語言實(shí)現(xiàn) */  
public native int hashCode();  
  
/** 默認(rèn)同==，直接比較對象 */  
public boolean equals(Object obj) {  
    return (this == obj);  
}  

hashCode是Object類中的方法，因此所有Java對象都有hashCode方法。當(dāng)類的對象用作HashMap這類哈希結(jié)構(gòu)的key值時(shí)，它的返回值用來支撐Hash算法的計(jì)算。其它時(shí)候，hashCode并沒有什么作用。所以很多情況下我們都不需要重寫hashCode方法，而Object類中將它定義為native方法。

equals也是Object類中的方法，默認(rèn)情況下equals比較的是兩個(gè)對象的引用是否相同，如果要將類的對象用作HashMap的key值，我們一般會(huì)重寫equals方法。Integer, String等基本類型都已經(jīng)重寫了equals方法，所以我們可以很方便的將它們用作hash的key。

• 底層結(jié)構(gòu)

transient Entry<K,V>[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

HashMap底層是以數(shù)組+鏈表+紅黑樹（jdk1.8增加了紅黑樹，這里暫時(shí)討論1.7以前版本）來存儲(chǔ)K/V數(shù)據(jù)的。Entry[] 就是一個(gè)K/V鍵值對數(shù)組，通常也叫bucket（散列桶）數(shù)組，數(shù)組中的每一個(gè)Entry又是一個(gè)鏈表，next用于存儲(chǔ)鏈表中的下一個(gè)條目。

HashMap底層結(jié)構(gòu).png

• 存儲(chǔ)k/v操作 put(key,value)

1、判斷key是否是null，如果是，hash值直接置為0，散列位置為bucket數(shù)組中第一個(gè)位置，index＝0。直接到步驟3。
2、如果key不為null，根據(jù)key的hashcode值計(jì)算hash值(h = hash(k.hashcode))，根據(jù)哈希值h找到key被散列到bucket數(shù)組中的位置index( index = h&(length-1) )。
3、找到bucket數(shù)組對應(yīng)位置 table[index] 的鏈表。如果鏈表為空，那么新建一個(gè)entry，k/v/hash值存儲(chǔ)于entry中，next指向null，table[index]=entry。 如果鏈表非空，遍歷，判斷當(dāng)前key是否和鏈表中某個(gè)entry的key值equals，如果equals，用value替換掉之前舊的value，然后方法立即返回。如果遍歷完沒有找到，那么創(chuàng)建一個(gè)新的entry，將新的entry置于鏈頭，next指向之前的鏈頭entry。 添加entry之前判斷是否需要擴(kuò)容，如果需要，以2的倍數(shù)擴(kuò)容

HashMap put圖解.png

觀察元素put的過程，我們發(fā)現(xiàn)在根據(jù)key尋找存儲(chǔ)地址時(shí)，先比較了key的hashCode，如果hashCode相同，再比較了equals，那么兩個(gè)key equals的前提是hashCode相等。所以就可以理解我們在初學(xué)java時(shí)，都熟記的一條原則：重寫equals方法，必須重寫hashCode方法。equals相等，hashCode一定相同。hashCode相同，不一定equals。

• 根據(jù)k值獲取v操作 get(key)

1、判斷key是否是null，如果是，hash值直接置為0，散列地址為bucket數(shù)組中第一個(gè)位置，index＝0。找到bucket數(shù)組對應(yīng)位置 table[0] 的鏈表。如果鏈表為空，那么返回null；如果不為空，遍歷找到key＝null的entry，返回entry的value值。
2、如果key不為null，根據(jù)key的hashcode值計(jì)算hash值(h = hash(k.hashcode))，根據(jù)哈希值h找到key被散列到bucket數(shù)組中的位置index( index = h&(length-1) )。
3、找到bucket數(shù)組對應(yīng)位置 table[index] 的鏈表。如果鏈表為空，那么返回null；如果不為空，遍歷entry，判斷當(dāng)前k的hash值等于entry的hash值，且key值和entry的key值equals的entry條目，返回entry的value值。

進(jìn)階分析

1. hash碰撞
   ［什么是hash碰撞？］
   對不同的key可能得到同一散列地址，即key1≠key2，而hash(key1)=hash(key2)，這種現(xiàn)象稱碰撞。比如上面的例子中“張三”和“張三的弟弟”兩個(gè)key在進(jìn)行hash的時(shí)候，得到的hash值都為8，index計(jì)算都為0，那么就產(chǎn)生了hash碰撞。

［為什么會(huì)有hash碰撞？］
產(chǎn)生上述hash碰撞的原因是由于我們的hashCode方法實(shí)現(xiàn)不合理，兩個(gè)同姓不同名的person，我們在定義Person類的時(shí)候不能簡單地用“姓氏”一個(gè)屬性來計(jì)算hashCode，應(yīng)該綜合姓氏、姓名、年齡等所有屬性計(jì)算hashCode。通常我們在Eclipse等IDE自動(dòng)生成hashCode方法時(shí)，編譯器會(huì)默認(rèn)幫我們生成合理的hashCode算法就是這個(gè)道理。

［hash碰撞會(huì)帶來什么問題？］
我們知道，數(shù)組的優(yōu)勢是隨機(jī)存取速度快，鏈表的優(yōu)勢是插入刪除速度快。假設(shè)所有存入HashMap的entry的key都不會(huì)產(chǎn)生hash碰撞，那么所有bucketIndex位置就只會(huì)存儲(chǔ)一個(gè)entry，整個(gè)hash表就類似是一個(gè)entry數(shù)組，存取速度會(huì)非常快。反之，如果key的hash碰撞概率非常高的話，那么有可能產(chǎn)生某個(gè)bucketIndex位置存儲(chǔ)的entry非常之多，鏈表非常長。極端情況下就是整個(gè)entry數(shù)組，只有某個(gè)index位置有數(shù)據(jù)存儲(chǔ)，整個(gè)hash表幾乎就變成了一個(gè)鏈表，那么這個(gè)hash表的存取速度會(huì)非常慢。

［如何避免hash碰撞？］
hash值是根據(jù)對象的hashCode計(jì)算而來的，如果我們的hashCode算法比較優(yōu)秀，可以保證重復(fù)率低，那么hash碰撞的概率就會(huì)降低。但是想做到完全避免，是非常困難的。而且，就算hashCode計(jì)算結(jié)果不一樣，在計(jì)算bucketIndex的時(shí)候，也可能得到相同的結(jié)果。比如，“張三”的hashCode＝8，“張三的弟弟”的hashCode＝16，bucket數(shù)組長度為8，那么 index = h & (length-1)，二者得到的結(jié)果都是0，仍然會(huì)發(fā)生碰撞。
那么可能大家會(huì)有這樣的想法，我們把bucket數(shù)組長度調(diào)大，翻倍變成16，二者index計(jì)算的結(jié)果就不會(huì)相同了，就沒有碰撞了。但是，我們很難合理設(shè)計(jì)數(shù)組的長度，如果設(shè)計(jì)很長固然可以一定程度上減少hash碰撞，提高存取效率，但是同時(shí)也犧牲了內(nèi)存空間，所以在考慮平衡空間和時(shí)間的情況下，我們只能在初始情況下定義一個(gè)較小的數(shù)組長度，當(dāng)發(fā)現(xiàn)哈希表中存儲(chǔ)的數(shù)據(jù)較多，達(dá)到一定閾值時(shí)，再對數(shù)組長度進(jìn)行擴(kuò)容。

2. resize擴(kuò)容
   ［什么是擴(kuò)容？如何擴(kuò)容？］
   hashmap的初始容量為16，即table數(shù)組的長度為16。默認(rèn)加載因子為0.75，即閾值為16*0.75=12。當(dāng)hash表中存儲(chǔ)的entry數(shù)量達(dá)到12時(shí)，hashmap會(huì)進(jìn)行擴(kuò)容。擴(kuò)容就是table數(shù)組長度翻倍變成32，當(dāng)達(dá)到下一次閾值時(shí)，繼續(xù)擴(kuò)容長度達(dá)到64，依此類推，hashmap每次擴(kuò)容后容量大小都是2的指數(shù)。

［為什么要擴(kuò)容？］
前面提到，如果數(shù)組長度比較小，就會(huì)很容易產(chǎn)生hash碰撞，導(dǎo)致entry以鏈表的形式集中存儲(chǔ)在某一個(gè)或多個(gè)bucketIndex上，降低存取效率。所以為了盡量保證hashmap的存取效率，需要在適當(dāng)?shù)臅r(shí)候進(jìn)行擴(kuò)容。

［擴(kuò)容會(huì)帶來什么問題？］
擴(kuò)容后，會(huì)創(chuàng)建一個(gè)新的entry數(shù)組，將舊的entry數(shù)組數(shù)據(jù)拷貝到新的數(shù)組中。并且，這個(gè)拷貝不是簡單的范圍拷貝。擴(kuò)容后，因?yàn)閔ash的算法和數(shù)組length相關(guān)聯(lián)，最后一步是 h & (length - 1)，當(dāng)length發(fā)生變化時(shí)，entry的bucketIndex可能發(fā)生改變。即以前同時(shí)存儲(chǔ)在index＝0位置上的“張三”和“張三的弟弟”可能需要分散到index＝0，index＝8的2個(gè)不同位置上。所以，擴(kuò)容會(huì)帶來rehash，整個(gè)hash表中的entry的存儲(chǔ)位置需要重新計(jì)算，這個(gè)操作是很影響效率的。

［如何避免rehash？］
為了減少初始時(shí)內(nèi)存空間的占用，我們只能定義容量較小的hash表。所以rehash肯定會(huì)產(chǎn)生，除非我們在創(chuàng)建hashmap之前，提前預(yù)知存儲(chǔ)entry所需要的容量，然后根據(jù)可傳入capacity的構(gòu)造方法構(gòu)造一個(gè)hashmap。

多線程下的使用

HashMap是非線程安全的，在多線程環(huán)境下，我們可以使用concurrent包下的ConcurrentHashMap。（Hashtable雖然可以替代HashMap，并且是線程安全的，但是是通過在方法上加synchrionize實(shí)現(xiàn)，效率沒有ConcurrentHashMap的分段鎖高）

總結(jié)

1. HashMap底層是以數(shù)組+鏈表的結(jié)構(gòu)存儲(chǔ)鍵值對。
2. 當(dāng)某一個(gè)類的對象想用作HashMap的key值時(shí)，需要重寫hashCode和equals方法。hashCode的實(shí)現(xiàn)要降低重復(fù)概率，推薦使用IDE默認(rèn)的hashCode實(shí)現(xiàn)。
3. HashMap在給key尋找存儲(chǔ)位置時(shí)，先比較hashCode，再比較equals。
4. HashMap擴(kuò)容導(dǎo)致rehash會(huì)造成性能問題，大批量數(shù)據(jù)存儲(chǔ)應(yīng)盡量在構(gòu)造hashmap之前設(shè)置好容量，避免遞增式的rehash。
5. HashMap非線程安全，多線程下推薦使用ConcurrentHashMap。