概念

• HasnMap是基于map接口實(shí)現(xiàn)，元素以鍵值對的方式存儲，并且鍵和值都可以使用null，因?yàn)?key不允許重復(fù)，因此只能有一個(gè)鍵為null
• HaasnMap是 無序不重復(fù)的，而且HashMap是線程不安全 的
• JDK7HashMap的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組+鏈表
• JDK8HashMap的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組 + 鏈表 + 紅黑樹

存儲的優(yōu)點(diǎn)

• 數(shù)組的特點(diǎn)：查詢效率高，插入和刪除效率低
• 鏈表的特點(diǎn)：查詢效率 低，插入和刪除效率高
• 在HasnMap底層使用數(shù)組加 (鏈表或紅黑樹) 的結(jié)構(gòu)完美的解決了數(shù)組和鏈表的問題，使的查詢和插入，刪除的效率都 很高
• HashMap的散列表是懶加載機(jī)制，在第一次put的時(shí)候才會創(chuàng)建

HashMap存儲元素的過程

首先將k、v封裝到Node對象當(dāng)中(節(jié)點(diǎn))

調(diào)用k的hasnCode()方法取出hash值;通過hashcode值和數(shù)組長度取模得到元素存儲的下標(biāo)

此時(shí)分為兩種情況

• 下標(biāo)位置上沒有元素，直接把元素方進(jìn)入
• 該所以已有元素，判斷該位置的元素和當(dāng)前元素是否相等，使用equals來比較(默認(rèn)是比較兩個(gè)對象的地址)。如果兩只相等則直接覆蓋，如果不等則(Hash碰撞)在原元素下面使用鏈表的結(jié)構(gòu)存儲該元素(如果已存在鏈表，則插在鏈表尾部)，每個(gè)元素節(jié)點(diǎn)都有一個(gè)next屬性指向下一個(gè)節(jié)點(diǎn)，這就由數(shù)組結(jié)構(gòu)變成了數(shù)組+鏈表;因?yàn)殒湵碇性靥嗟臅r(shí)候回影響查找效率，所以當(dāng)鏈表的元素個(gè)數(shù)達(dá)到 8 的時(shí)候使用鏈表存儲就轉(zhuǎn)變成了使用紅黑樹存儲(當(dāng)紅黑樹上的節(jié)點(diǎn)數(shù)量小于 6 個(gè)，會重新把紅黑樹變成單向鏈表數(shù)據(jù)結(jié)構(gòu))，原因就是紅黑樹是平衡二叉樹，在查找性能方面比聊表要高

HashMap取值的實(shí)現(xiàn)

• 先調(diào)用k的hashCode()方法得出哈希值，并通過hash算法轉(zhuǎn)換成數(shù)組的下標(biāo)
• 通過hash值轉(zhuǎn)換成數(shù)組下標(biāo)后，通過數(shù)組定位到下標(biāo)位置，如果改位置上什么都沒有，范圍null;如果該位置上有單向鏈表，那么就拿參數(shù)K和單向鏈表上的每一個(gè)節(jié)點(diǎn)的K進(jìn)行equals比較，如果所有equals都返回false，則返回null，如果有一個(gè)節(jié)點(diǎn)的K和參數(shù)K通過equals返回true，那么此時(shí)該節(jié)點(diǎn)的value就是要獲取的value值

擴(kuò)容

• HashMap中有兩個(gè)重要參數(shù)，初始容量大小和負(fù)載因子，在HashMap剛開始初始化的時(shí)候，使用默認(rèn)的構(gòu)造方法，會返回一個(gè)空的table，并且 thershold(擴(kuò)容閾值)為 0 ，因此第一次擴(kuò)容的時(shí)候默認(rèn)值就會是 16 ，負(fù)載因子默認(rèn)為 0.75 ，用數(shù)組容量乘以負(fù)載因子得到一個(gè)值，一旦數(shù)組中存儲的元素個(gè)數(shù)超過這個(gè)值就會調(diào)用rehash方法將數(shù)組容量增加到原來的兩倍，threshold也會變?yōu)樵瓉淼膬杀?/li>
• 在做擴(kuò)容的時(shí)候會生成一個(gè)新的數(shù)組，原來的所有數(shù)據(jù)需要重新計(jì)算哈希碼值重新分配到新的數(shù)組，所以擴(kuò)容的操作非常消耗性能。所以，如果知道要存入的數(shù)據(jù)量比較大的話，可以在創(chuàng)建的時(shí)候先指定一個(gè)比較大的數(shù)據(jù)容量
• 也可以引申到一個(gè)問題HashMap是先插入還是先擴(kuò)容：HashMap初始化后首次插入數(shù)據(jù)時(shí)，先發(fā)生resize擴(kuò)容再插入數(shù)據(jù)，之后每當(dāng)插入的數(shù)據(jù)個(gè)數(shù)達(dá)到threshold時(shí)就會發(fā)生resize，此時(shí)是先插入數(shù)據(jù)再resize

HashMap中的擴(kuò)容是在元素插入之前進(jìn)行的擴(kuò)容還是元素插入之后進(jìn)行的擴(kuò)容

在 JDK1.7中是在元素插入 前 進(jìn)行的擴(kuò)容，在JDK1.8 中是先加入元素 后 再判斷是否進(jìn)行擴(kuò)容

存儲元素超過閾值一定會進(jìn)行擴(kuò)容嗎

在 JDK1.7 中不一定，只有存儲元素超過閾值并且當(dāng)前存儲位置不為null，才會進(jìn)行擴(kuò)容，在 JDK1.8 中會進(jìn)行擴(kuò)容

HashMap和HashTable區(qū)別

線程方面

• HashMap是非線程安全的，HashTable是線程安全的。 Hashtable的實(shí)現(xiàn)方法里面都添加了synchronized關(guān)鍵字來確保線程同步，因此相對而言HashMap性能會高一些，我們平時(shí)使用時(shí)若無特殊需求建議使用HashMap，在多線程環(huán)境下若使用HashMap需要使用Collections.synchronizedMap()方法來獲取一個(gè)線程安全的集合
• HashMap的key可以為null，HashTable的key不可為null
• HashMap是對Map接口的實(shí)現(xiàn)，HashTable實(shí)現(xiàn)了Map接口和Dictionary抽象類
• HashMap的初始容量為 16 ，Hashtable初始容量為 11 ，兩者的填充因子默認(rèn)都是 0.75 ，HashMap擴(kuò)容時(shí)是當(dāng)前容量翻倍即：capacity * 2，- Hashtable擴(kuò)容時(shí)是容量翻倍+1即：capacity * 2+1

HashMap中的hashcode怎么生成

調(diào)用對象key的hashCode方法，再對這個(gè)hashcode方法進(jìn)行一些右移以及異或運(yùn)算(使的hashCode的高位和低位都參與到運(yùn)算中);通過右移和異或運(yùn)算可以使hashMap的散列化更強(qiáng)，提高h(yuǎn)ashMap的get方法的效率

為什么使用HashCode

HashCode的存在主要是為了查找的快捷性, HashCode是用來在散列存儲結(jié)構(gòu)中確定對象的存儲地址的 ( 用hashcode來代表對象在hash表中的位置 ) , hashCode存在的重要的原因之一就是在HashMap(HashSet其實(shí)就是HashMap)中使用(其實(shí)Object類的hashCode方法注釋已經(jīng)說明了)，HashMap之所以速度 快 ，因?yàn)樗褂玫氖?散列表 ，根據(jù)key的hashcode值生成數(shù)組下標(biāo)(通過內(nèi)存地址直接查找，不需要判斷，但是需要多出很多內(nèi)存，相當(dāng)于以空間換時(shí)間)

equals方法和hashcode的關(guān)系

歸納總結(jié)：

• 若重寫了equals(Object obj)方法，則有必要重寫hashCode()方法
• 若兩個(gè)對象equals(Object obj)返回true，則hashCode()有必要也返回相同的int數(shù)
• 若兩個(gè)對象equals(Object obj)返回false，則hashCode()不一定返回不同的int數(shù)
• 若兩個(gè)對象hashCode()返回相同int數(shù)，則equals(Object obj)不一定返回true
• 若兩個(gè)對象hashCode()返回不同int數(shù)，則equals(Object obj)一定返回false
• 同一對象在執(zhí)行期間若已經(jīng)存儲在集合中，則不能修改影響hashCode值的相關(guān)信息，否則會導(dǎo)致內(nèi)存泄露問題

key為null怎么辦

key為null的時(shí)候，只會放在hashMap的0位置(即key的hashCode為0，對數(shù)組長度取余后的下標(biāo)也是0)，不會有鏈表 在HashMap源碼中對put方法對null做了處理，key為null的判斷后進(jìn)入putForNullKey(V value)這個(gè)方法，李里面for循環(huán)是在talbe[0]鏈表 中查找key為null的元素，如果找到，則將value重新賦值給這個(gè)元素的value，并返回原來的value。如果沒找到則將這個(gè)元素添加到talbe[0]鏈表的表頭

/** 
 * HashMap的put方法 
 */ 
public V put(K key, V value) { 
    if (table == EMPTY_TABLE) { 
        inflateTable(threshold); 
    } 
 
    // key為null調(diào)用putForNullKey(value) 
    if (key == null) return putForNullKey(value); 
 
    int hash = hash(key); 
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
        Object k; 
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
            V oldValue = e.value; 
            e.value = value; 
            e.recordAccess(this); 
            return oldValue; 
        } 
    } 
    modCount++; 
    addEntry(hash, key, value, i); 
    return null; 
} 
 
/** 
 * Offloaded version of put for null keys 
 */ 
private V putForNullKey(V value) { 
    // for循環(huán)處理key為空的情況 
    for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
        if (e.key == null) { 
            V oldValue = e.value; 
            e.value = value; 
            e.recordAccess(this); 
            return oldValue; 
        } 
    } 
    modCount++; 
    addEntry(0, null, value, 0); 
    return null; 
} 

 【編輯推薦】