目錄

1.HashMap概述

2.JDK7與JDK8的HashMap區(qū)別

3.HashMap的主要方法分析

4.常見問題分析總結(jié)

1.HashMap概述

HashMap是使用頻率最高的用于映射鍵值對(key和value)處理的數(shù)據(jù)類型。隨著JDK版本的跟新，JDK1.8對HashMap底層的實(shí)現(xiàn)進(jìn)行了優(yōu)化，列入引入紅黑樹的數(shù)據(jù)結(jié)構(gòu)和擴(kuò)容的優(yōu)化等。本文結(jié)合JDK1.7和JDK1.8的區(qū)別，深入探討HashMap的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)和功能原理。

在討論哈希表之前，我們先大概了解下其他數(shù)據(jù)結(jié)構(gòu)在新增，查找等基礎(chǔ)操作執(zhí)行性能

數(shù)組：采用一段連續(xù)的存儲(chǔ)單元來存儲(chǔ)數(shù)據(jù)。對于指定下標(biāo)的查找，時(shí)間復(fù)雜度為O(1)；通過給定值進(jìn)行查找，需要遍歷數(shù)組，逐一比對給定關(guān)鍵字和數(shù)組元素，時(shí)間復(fù)雜度為O(n)，當(dāng)然，對于有序數(shù)組，則可采用二分查找，插值查找，斐波那契查找等方式，可將查找復(fù)雜度提高為O(logn)；對于一般的插入刪除操作，涉及到數(shù)組元素的移動(dòng)，其平均復(fù)雜度也為O(n)

線性鏈表：對于鏈表的新增，刪除等操作（在找到指定操作位置后），僅需處理結(jié)點(diǎn)間的引用即可，時(shí)間復(fù)雜度為O(1)，而查找操作需要遍歷鏈表逐一進(jìn)行比對，復(fù)雜度為O(n)

二叉樹：對一棵相對平衡的有序二叉樹，對其進(jìn)行插入，查找，刪除等操作，平均復(fù)雜度均為O(logn)。

哈希表：相比上述幾種數(shù)據(jù)結(jié)構(gòu)，在哈希表中進(jìn)行添加，刪除，查找等操作，性能十分之高，不考慮哈希沖突的情況下（后面會(huì)探討下哈希沖突的情況），僅需一次定位即可完成，時(shí)間復(fù)雜度為O(1)，接下來我們就來看看哈希表是如何實(shí)現(xiàn)達(dá)到驚艷的常數(shù)階O(1)的。

我們知道，數(shù)據(jù)結(jié)構(gòu)的物理存儲(chǔ)結(jié)構(gòu)只有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（像棧，隊(duì)列，樹，圖等是從邏輯結(jié)構(gòu)去抽象的，映射到內(nèi)存中，也這兩種物理組織形式），而在上面我們提到過，在數(shù)組中根據(jù)下標(biāo)查找某個(gè)元素，一次定位就可以達(dá)到，哈希表利用了這種特性，哈希表的主干就是數(shù)組。

比如我們要新增或查找某個(gè)元素，我們通過把當(dāng)前元素的關(guān)鍵字 通過某個(gè)函數(shù)映射到數(shù)組中的某個(gè)位置，通過數(shù)組下標(biāo)一次定位就可完成操作。

哈希沖突

如果兩個(gè)不同的元素，通過哈希函數(shù)得出的實(shí)際存儲(chǔ)地址相同怎么辦？也就是說，當(dāng)我們對某個(gè)元素進(jìn)行哈希運(yùn)算，得到一個(gè)存儲(chǔ)地址，然后要進(jìn)行插入的時(shí)候，發(fā)現(xiàn)已經(jīng)被其他元素占用了，其實(shí)這就是所謂的哈希沖突，也叫哈希碰撞。前面我們提到過，哈希函數(shù)的設(shè)計(jì)至關(guān)重要，好的哈希函數(shù)會(huì)盡可能地保證 計(jì)算簡單和散列地址分布均勻,但是，我們需要清楚的是，數(shù)組是一塊連續(xù)的固定長度的內(nèi)存空間，再好的哈希函數(shù)也不能保證得到的存儲(chǔ)地址絕對不發(fā)生沖突。那么哈希沖突如何解決呢？哈希沖突的解決方案有多種:開放定址法（發(fā)生沖突，繼續(xù)尋找下一塊未被占用的存儲(chǔ)地址），再散列函數(shù)法，鏈地址法，而HashMap即是采用了鏈地址法，也就是數(shù)組+鏈表的方式。

HashMap的幾個(gè)重要知識點(diǎn)

1. HashMap是無序且不安全的數(shù)據(jù)結(jié)構(gòu)。
2. HashMap 是以key–value對的形式存儲(chǔ)的，key值是唯一的（可以為null），一個(gè)key只能對應(yīng)著一個(gè)value，但是value是可以重復(fù)的。
3. HashMap 如果再次添加相同的key值，它會(huì)覆蓋key值所對應(yīng)的內(nèi)容，這也是與HashSet不同的一點(diǎn)，Set通過add添加相同的對象，不會(huì)再添加到Set中去。
4. HashMap 提供了get方法，通過key值取對應(yīng)的value值，但是HashSet只能通過迭代器Iterator來遍歷數(shù)據(jù)，找對象。

2.JDK7與JDK8的HashMap區(qū)別

既然講HashMap，那就不得不說一下JDK1.7與JDK1.8（及jdk8以后）的HashMap有什么區(qū)別：

1. jdk1.8中添加了紅黑樹，當(dāng)鏈表長度大于等于8的時(shí)候鏈表會(huì)變成紅黑樹
2. 鏈表新節(jié)點(diǎn)插入鏈表的順序不同（jdk1.7是插入頭結(jié)點(diǎn)，jdk1.8因?yàn)橐焰湵碜優(yōu)榧t黑樹所以采用插入尾節(jié)點(diǎn)）
3. hash算法簡化 ( jdk1.8 )
4. resize的邏輯修改（jdk1.7會(huì)出現(xiàn)死循環(huán)，jdk1.8不會(huì)）

3.HashMap的主要方法分析

put方法

put方法用于將鍵值對插入到 HashMap 中。讓我們看一下put方法的源代碼：

首先，通過has(key)方法計(jì)算鍵的哈希碼，并調(diào)用putVal()方法進(jìn)行插入操作。下面是putVal()方法的源代碼：

??putVal()方法的核心是通過哈希碼定位桶，然后在桶中進(jìn)行插入操作。如果桶為空，則直接在桶中插入新節(jié)點(diǎn)。如果桶不為空，則遍歷鏈表或紅黑樹，查找鍵是否已存在。如果鍵已存在，則替換對應(yīng)的值；如果鍵不存在，則將新節(jié)點(diǎn)插入到鏈表的末尾，并根據(jù)鏈表長度是否達(dá)到閾值來決定是否將鏈表轉(zhuǎn)化為紅黑樹。最后，更新修改次數(shù)和元素?cái)?shù)量，并進(jìn)行必要的操作。

get方法

當(dāng)我們需要根據(jù)鍵來獲取值時(shí)，可以使用 HashMap 的get(key)方法。下面講解下 HashMap 的get方法的原理。

首先，我們傳入要查找的鍵key，然后通過hash(key)方法計(jì)算鍵的哈希碼。哈希碼被用來確定鍵在 HashMap 中的桶（bucket）位置。根據(jù)哈希碼，我們可以確定鍵在數(shù)組中的索引位置。

接下來，我們在確定的索引位置找到對應(yīng)的桶。如果桶為空，即沒有鍵值對存在，那么返回 null，表示沒有找到對應(yīng)的值。

如果桶不為空，那么可能存在多個(gè)鍵值對，這時(shí)我們需要遍歷鏈表或紅黑樹來找到具有相同鍵的節(jié)點(diǎn)。在遍歷過程中，我們會(huì)使用鍵的 equals() 方法來比較傳入的鍵和當(dāng)前節(jié)點(diǎn)的鍵是否相等。如果找到了相等的鍵，那么返回對應(yīng)節(jié)點(diǎn)的值。

如果遍歷完整個(gè)鏈表或紅黑樹仍然沒有找到相等的鍵，那么返回 null，表示沒有找到對應(yīng)的值。

整個(gè)get()方法的原理就是根據(jù)鍵的哈希碼確定索引位置，然后在對應(yīng)的桶中遍歷鏈表或紅黑樹，通過 equals() 方法比較鍵的相等性來找到對應(yīng)的值。

resize方法

resize方法用于動(dòng)態(tài)擴(kuò)容 HashMap。當(dāng)元素?cái)?shù)量超過閾值時(shí)，HashMap 會(huì)自動(dòng)觸發(fā)擴(kuò)容操作。resize方法的主要功能是創(chuàng)建一個(gè)新的數(shù)組，并將所有鍵值對重新計(jì)算哈希碼和索引位置，然后將它們分配到新的桶中。擴(kuò)容后的容量是原來的兩倍，并根據(jù)負(fù)載因子重新計(jì)算閾值。在轉(zhuǎn)移鍵值對時(shí)，會(huì)根據(jù)哈希碼的高位來確定是保留在原來的位置還是移動(dòng)到新的位置。如果鏈表長度超過閾值，則會(huì)將鏈表轉(zhuǎn)化為紅黑樹以提高查找效率。

4.常見問題分析總結(jié)

4.1為什么要用HashMap，你知道底層原理嗎？

HashMap結(jié)合了查詢效率快以及增刪效率快的優(yōu)點(diǎn)，作為一個(gè)容器是非?？少F的。HashMap存的都是一個(gè)個(gè)鍵值對，我們通過鍵值對對其進(jìn)行修改和訪問，在 JDK 1.7及以前底層是一個(gè)數(shù)組+鏈表的結(jié)構(gòu)，當(dāng)發(fā)生哈希沖突時(shí)，就將節(jié)點(diǎn)采用頭插法的方式放在鏈表頭部。在JDK1.7以后底層是一個(gè)數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)，同樣的，發(fā)生哈希沖突時(shí)，依舊是插到鏈表里去，只不過現(xiàn)在是尾插法，這樣做就是為了避免出現(xiàn)循環(huán)數(shù)據(jù)，另外當(dāng)鏈表節(jié)點(diǎn)大于8時(shí)，會(huì)轉(zhuǎn)成紅黑樹進(jìn)行存儲(chǔ)，但這并不代表刪除了鏈表結(jié)構(gòu)，鏈表結(jié)構(gòu)依然存在，當(dāng)節(jié)點(diǎn)數(shù)量重新小于8后，紅黑樹又會(huì)重新變成鏈表結(jié)構(gòu)。(再說說get(),put()方法原理就差不多了)。

4.2HashMap 中的 hash 值有什么用？

HashMap中的hash值是由hash函數(shù)產(chǎn)生的，它是保證HashMap能正常運(yùn)轉(zhuǎn)的基石，所有鍵值對進(jìn)行存儲(chǔ)時(shí)的位置都是靠它和 (length - 1) 進(jìn)行位運(yùn)算得出的，我們進(jìn)行插入、訪問、刪除都必須先得到對應(yīng)的hash值，再通過它算出對應(yīng)的索引值，最后才能操作對應(yīng)的鍵值對。

4.3HashMap中初始化大小為什么是16呢？

首先我們看hashMap的源碼可知當(dāng)新put一個(gè)數(shù)據(jù)時(shí)會(huì)進(jìn)行計(jì)算位于table數(shù)組(也稱為桶)中的下標(biāo)：

因?yàn)槭菍⒍M(jìn)制進(jìn)行按位于，(16-1) 是 1111,末位是1，這樣也能保證計(jì)算后的index既可以是奇數(shù)也可以是偶數(shù)，并且只要傳進(jìn)來的key足夠分散，均勻那么按位于的時(shí)候獲得的index就會(huì)減少重復(fù)，這樣也就減少了hash的碰撞以及hashMap的查詢效率。

那么到了這里你也許會(huì)問？ 那么就然16可以，是不是只要是2的整數(shù)次冪就可以呢？

答案是肯定的。那為什么不是8,4呢？ 因?yàn)槭?或者4的話很容易導(dǎo)致map擴(kuò)容影響性能，如果分配的太大的話又會(huì)浪費(fèi)資源，所以就使用16作為初始大小。

4.4為什么建議用 String Integer 這樣的包裝類作為 HashMap 的鍵？

首先，這些類內(nèi)部重寫了hashCode()，equal()方法，本身就遵循HashMap中的規(guī)范，可以有效減小hash碰撞的概率。其次，這些類都是final類型，也就是說key是不可變的，避免同一個(gè)對象的計(jì)算出的hash值不一樣。除了上面所說的，很多容器都不能用基本類型并且也不能存null值也是一個(gè)原因。

4.5重寫equals方法需同時(shí)重寫hashCode方法嗎？

?我們舉例來看看，如果重寫了equals而不重寫hashcode會(huì)發(fā)生什么樣的問題

package HashBucketDemo;

import java.util.HashMap;

public class MyTest {
    private static class Person{
        int idCard;
        String name;

        public Person(int idCard, String name) {
            this.idCard = idCard;
            this.name = name;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()){
                return false;
            }
            Person person = (Person) o;
            //兩個(gè)對象是否等值，通過idCard來確定
            return this.idCard == person.idCard;
        }

    }
    public static void main(String []args){
        HashMap<Person,String> map = new HashMap<Person, String>();
        Person person = new Person(1234,"大大怪");
        //put到hashmap中去
        map.put(person,"呃呃呃呃呃");
        //get取出，從邏輯上講應(yīng)該能輸出“呃呃呃呃呃”
        System.out.println("結(jié)果:"+map.get(new Person(1234,"大大怪")));
    }
}

這是因?yàn)槲覀冊谶M(jìn)行g(shù)et和put操作的時(shí)候，使用的key從邏輯上講是等值的（通過equals比較是相等的），但由于沒有重寫hashCode方法，所以put操作時(shí)，key(hashcode1)–>hash–>indexFor–>最終索引位置 ，而通過key取出value的時(shí)候 key(hashcode1)–>hash–>indexFor–>最終索引位置，由于hashcode1不等于hashcode2，導(dǎo)致沒有定位到一個(gè)數(shù)組位置而返回邏輯上錯(cuò)誤的值null。

所以，在重寫equals的方法的時(shí)候，必須注意重寫hashCode方法，同時(shí)還要保證通過equals判斷相等的兩個(gè)對象，調(diào)用hashCode方法要返回同樣的整數(shù)值。而如果equals判斷不相等的兩個(gè)對象，其hashCode可以相同（只不過會(huì)發(fā)生哈希沖突，應(yīng)盡量避免）。

4.6為什么HashMap的默認(rèn)負(fù)載因子是0.75，而不是0.5或者是整數(shù)1呢？

1. 閾值(threshold) = 負(fù)載因子(loadFactor) x 容量(capacity) 根據(jù)HashMap的擴(kuò)容機(jī)制，他會(huì)保證容量(capacity)的值永遠(yuǎn)都是2的冪 為了保證負(fù)載因子x容量的結(jié)果是一個(gè)整數(shù)，這個(gè)值是0.75(4/3)比較合理，因?yàn)檫@個(gè)數(shù)和任何2的次冪乘積結(jié)果都是整數(shù)。
2. 理論上來講，負(fù)載因子越大，導(dǎo)致哈希沖突的概率也就越大，負(fù)載因子越小，費(fèi)的空間也就越大,這是一個(gè)無法避免的利弊關(guān)系，所以通過一個(gè)簡單的數(shù)學(xué)推理，可以測算出這個(gè)數(shù)值在0.75左右是比較合理的，是一個(gè)平衡點(diǎn)。

4.7JDK 1.7中為什么會(huì)形成死循環(huán)?(重點(diǎn))

此處JDK為1.7，為頭插法

在多線程下擴(kuò)容會(huì)形成死循環(huán)，我們先來回顧下正常情況下的擴(kuò)容。

?成功擴(kuò)容后，我們發(fā)現(xiàn)鏈表被倒置了，現(xiàn)在再來看看?多線程?下對?HashMap?進(jìn)行擴(kuò)容形成環(huán)形數(shù)據(jù)結(jié)構(gòu)的情況。

假設(shè)現(xiàn)在有兩個(gè)線程在同時(shí)擴(kuò)容?HashMap?，當(dāng)線程A執(zhí)行到?Entry<K,V> next = e.next?時(shí)被掛起，待到線程B擴(kuò)容完畢后，線程A重新拿到?CPU時(shí)間片?。

因?yàn)榫€程A在擴(kuò)容前執(zhí)行過?Entry<K,V> next = e.next，因此現(xiàn)在線程A的?e?和?next?分別指向?key("cofbro")?和?key("cc")。

現(xiàn)在 線程A 開始擴(kuò)容，首先執(zhí)行 newTab[i] = e，將 entry 插入到數(shù)組中，隨后按照順序執(zhí)行 e = next，然后進(jìn)入下一個(gè)循環(huán) Entry<K,V> next = e.next，因?yàn)榇藭r(shí)HashMap已經(jīng)被 線程B 擴(kuò)容完成，所以此時(shí)的 next = key("cofbro") 。?

?現(xiàn)在繼續(xù)執(zhí)行上個(gè)操作流程，不過由于?key("cofbro").next?沒有節(jié)點(diǎn)了，因此?next?是?null。

我們看到這個(gè)時(shí)候又會(huì)將?key("cofbro")?插到鏈表的頭部，死循環(huán)就這樣產(chǎn)生了。

?4.8HashMap put方法邏輯圖（JDK1.8）

?文章來源地址http://www.zghlxwxcb.cn/news/detail-636742.html

到了這里，關(guān)于重溫HashMap底層原理的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！