一、快速入門

示例：有一定基礎的小伙伴們可以選擇性的跳過該步驟

HashMap是Java程式員使用頻率最高的用于映射鍵值對(key和value)處理的資料型別，隨著JDK版本的跟新，JDK1.8對HashMap底層的實作進行了優化，列入引入紅黑樹的資料結構和擴容的優化等，本文結合JDK1.7和JDK1.8的區別，深入探討HashMap的資料結構實作和功能原理，
Java為資料結構中的映射定義了一個介面java.uti.Map，此介面主要有四個常用的實作類，分別是HashMap，LinkedHashMap，Hashtable，TreeMap，IdentityHashMap，本篇文章主要講解HashMap以及底層實作原理，

1.HashMap的常用方法

//        Hashmap存值：----------------------------------》 .put("key","value")； ----------》無回傳值，
//
//        Hashmap取值：----------------------------------》 .get("key")；-------------------》 回傳Value的型別，
//
//        Hashmap判斷map是否為空：-----------------------》 .isEmpty()； -------------------》回傳boolean型別，
//
//        Hashmap判斷map中是否存在這個key：--------------》.containsKey("key")；------------》回傳boolean型別，
//
//        Hashmap判斷map中是否含有value：----------------》.containsValue("value")；-------》回傳boolean型別，
//
//        Hashmap洗掉這個key值下的value：----------------》.remove("key")；-----------------》回傳Value的型別，
//
//        Hashmap顯示所有的value值：---------------------》.values()； --------------------》回傳Value的型別，
//
//        Hashmap顯示map里的值得數量：-------------------》.size()； ----------------------》回傳int型別
//
//        HashMap顯示當前已存的key：---------------------》 .keySet()；-------------------》回傳Key的型別陣列，
//
//        Hashmap顯示所有的key和value：-----------------》.entrySet())；------------------》回傳Key=Value型別陣列，
//
//        Hashmap添加另一個同一型別的map：--------------》.putAll(map)； -----------------》(引數為另一個同一型別的map)無回傳值，
//
//        Hashmap洗掉這個key和value：------------------》.remove("key", "value")；-------》(如果該key值下面對應的是該value值則洗掉)回傳boolean型別，
//
//        Hashmap替換這個key對應的value值(JDK8新增)：---》.replace("key","value")；-------》回傳被替換掉的Value值的型別，
//
//        克隆Hashmap：-------------------------------》.clone()； ---------------------》回傳object型別，
//
//        清空Hashmap：-------------------------------》.clear()； ---------------------》無回傳值，

2.HashMap的幾個重要知識點

1. HashMap是無序且不安全的資料結構，

2. HashMap 是以key–value對的形式存盤的，key值是唯一的（可以為null），一個key只能對應著一個value，但是value是可以重復的，

3. HashMap 如果再次添加相同的key值，它會覆寫key值所對應的內容，這也是與HashSet不同的一點，Set通過add添加相同的物件，不會再添加到Set中去，

4. HashMap 提供了get方法，通過key值取對應的value值，但是HashSet只能通過迭代器Iterator來遍歷資料，找物件，

二、JDK7與JDK8的HashMap區別

既然講HashMap，那就不得不說一下JDK7與JDK8（及jdk8以后）的HashMap有什么區別：

1. jdk8中添加了紅黑樹，當鏈表長度大于等于8的時候鏈表會變成紅黑樹
2. 鏈表新節點插入鏈表的順序不同（jdk7是插入頭結點，jdk8因為要把鏈表變為紅 黑樹所以采用插入尾節點）
3. hash演算法簡化 ( jdk8 )
4. resize的邏輯修改（jdk7會出現死回圈，jdk8不會）

三、HashMap的容量與擴容機制

1.HashMap的默認負載因子

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     *默認的負載因子是0.75f,也就是75% 負載因子的作用就是計算擴容閾值用，比如說使用
     *無參構造方法創建的HashMap 物件，他初始長度默認是16  閾值 = 當前長度 * 0.75  就
     *能算出閾值，當當前長度大于等于閾值的時候HashMap就會進行自動擴容
     */

面試的時候，面試官經常會問道一個問題：為什么HashMap的默認負載因子是0.75，而不是0.5或者是整數1呢？
答案有兩種：

1. 閾值(threshold) = 負載因子(loadFactor) x 容量(capacity) 根據HashMap的擴容機制，他會保證容量(capacity)的值永遠都是2的冪 為了保證負載因子x容量的結果是一個整數，這個值是0.75(4/3)比較合理，因為這個數和任何2的次冪乘積結果都是整數，

2. 理論上來講，負載因子越大，導致哈希沖突的概率也就越大，負載因子越小，費的空間也就越大,這是一個無法避免的利弊關系，所以通過一個簡單的數學推理，可以測算出這個數值在0.75左右是比較合理的

2.HashMap的擴容機制

寫資料之后會可能觸發擴容，HashMap結構內，我記得有一個記錄當前資料量的欄位，這個資料量欄位到達擴容閾值的話，它就會觸發擴容的操作

閾值(threshold) = 負載因子(loadFactor) x 容量(capacity) 
當HashMap中table陣列(也稱為桶)長度 >= 閾值(threshold) 就會自動進行擴容，

擴容的規則是這樣的，因為table陣列長度必須是2的次方數，擴容其實每次都是按照上一次tableSize位運算得到的就是做一次左移1位運算，
假設當前tableSize是16的話 16轉為二進制再向左移一位就得到了32 即 16 << 1 == 32 即擴容后的容量，也就是說擴容后的容量是當前
容量的兩倍，但記住HashMap的擴容是采用當前容量向左位移一位（newtableSize = tableSize << 1），得到的擴容后容量，而不是當前容量x2

問題又來了，為什么計算擴容后容量要采用位移運算呢，怎么不直接乘以2呢？
這個問題就比較簡單了，因為cpu畢竟它不支持乘法運算，所有的乘法運算它最終都是再指令層面轉化為了加法實作的，這樣效率很低，如果用位運算的話對cpu來說就非常的簡潔高效，

3.HashMap中散串列陣列初始長度

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * HashMap中散串列陣列初始長度為 16 (1 << 4)
     * 創建HashMap的時候可以設定初始化容量和設定負載因子，
     * 但HashMap會自動優化設定的初始化容量引數，確保初始化
     * 容量始終為2的冪
     */

老問題又來了，為啥HashMap中初始化大小為什么是16呢？

首先我們看hashMap的原始碼可知當新put一個資料時會進行計算位于table陣列(也稱為桶)中的下標：

int index =key.hashCode()&(length-1);

hahmap每次擴容都是以 2的整數次冪進行擴容

因為是將二進制進行按位于，(16-1) 是 1111,末位是1，這樣也能保證計算后的index既可以是奇數也可以是偶數，并且只要傳進來的key足夠分散，均勻那么按位于的時候獲得的index就會減少重復，這樣也就減少了hash的碰撞以及hashMap的查詢效率，

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

答案是肯定的，那為什么不是8,4呢？ 因為是8或者4的話很容易導致map擴容影響性能，如果分配的太大的話又會浪費資源，所以就使用16作為初始大小，

四、HashMap的結構

JDK7與JDK8及以后的HashMap結構與存盤原理有所不同：
Jdk1.7：陣列 + 鏈表 ( 當陣列下標相同，則會在該下標下使用鏈表)
Jdk1.8：陣列 + 鏈表 + 紅黑樹 (預值為8 如果鏈表長度<=8則會把鏈表變成紅黑樹 )
Jdk1.7中鏈表新元素添加到鏈表的頭結點,先加到鏈表的頭節點,再移到陣列下標位置
Jdk1.8中鏈表新元素添加到鏈表的尾結點
(陣列通過下標索引查詢，所以查詢效率非常高，鏈表只能挨個遍歷，效率非常低，jdk1.8及以
上版本引入了紅黑樹，當鏈表的長度大于或等于8的時候則會把鏈表變成紅黑樹，以提高查詢效率)

五、HashMap存盤原理與存盤流程

1.HashMap存盤原理

1. 獲取到傳過來的key，呼叫hash演算法獲取到hash值

2. 獲取到hash值之后呼叫indexFor方法，通過獲取到的hash值以及陣列的長度算
   出陣列的下標 (把哈希值和陣列容量轉換為二進，再在陣列容量范圍內與哈希值
   進行一次與運算，同為1則1，不然則為0，得出陣列的下標值，這樣可以保證計算出的陣列下標不會大于當前陣列容量)

3. 把傳過來的key和value存到該陣列下標當中，

4. 如該陣列下標下以及有值了，則使用鏈表，jdk7是把新增元素添加到頭部節點 jdk8則添加到尾部節點，

2.HashMap存盤流程

前面尋址演算法都是一樣的，根據key的hashcode經過高低位異或之后的值，再按位與 &(table.lingth - 1),得到一個陣列下標，然后根據這個陣列下標內的狀況，狀況不同，然后情況也不同，大概分為了4種狀態：

( 1.)第一種就是陣列下標下內容為空：
這種情況沒什么好說的，為空據直接占有這個slot槽位就好了，然后把當前.put方法傳進來的key和value包裝成一個node物件,放到這個slot中就好了，

( 2.)第二種情況就是陣列下標下內容不為空，但它參考的node還沒有鏈化：
這種情況下先要對比一下這個node物件的key與當前put物件的key是否完全.相等，如果完全相等的情況下，就行進行replace操作，把之前的槽位中node.下的value替換成新的value就可以了，否則的話這個put操作就是一個正兒.八經的hash沖突,這種情況在slot槽位后面追加一個node就可以了,用尾插法 ( 前面講過，jdk7是把新增元素添加到頭部節點，而jdk8則添加到尾部節點)，

( 3.)第三種就是該陣列下標下內容已經被鏈化了：
這種情況和第二種情況處理很相似，首先也是迭代查找node，看看鏈表上中元素的key，與當前傳過來的key是否完全一致，如果完全一致的話還是repleace操作，用put過來的新value替換掉之前node中的value，否則的話就是一致迭代到鏈表尾節點也沒有匹配到完全一致的node，就和之前的一樣，把put進來資料包裝成node追加到鏈表的尾部，再檢查一下當前鏈表的長度，有沒有達到樹化閾值，如果達到了閾值就呼叫一個樹化方法，樹化操作都是在這個方法里完成的，

( 4.)第四種情況就是沖突很嚴重的情況下，這個鏈表已經轉化成紅黑樹了：
紅黑樹就比較復雜 要將清楚這個紅黑樹還得從TreeNode說起 TreeNode繼承了Node結構，在Node基礎上加了幾個欄位，分別是指向父節點parent欄位，指向左子節點left欄位，指向右子節點right欄位，還有一個表示顏色的red欄位，這就是TreeNode的基本結構，然后紅黑樹的插入操作，首先找到一個合適的插入點，就是找到插入節點的父節點，然后紅黑樹它又滿足二叉樹的所有特性，所以找這個父節點的操作和二叉樹排序是完全一致的，然后說一下這個二叉樹排序，其實就是二分查找演算法映射出來的結構，就是一個倒立的二叉樹，然后每個節點都可以有自己的子節點，本且左節點小于但前節點，右節點大于當前節點，然后每次向下查找一層就能那個排除掉一半的資料，查找效率非常的高效，當查找的程序中也是分情況的，

1. 首先第一種情況就是一直向下探測，直到查詢到左子樹或者右子樹位null，說明整個樹中，并沒有發現node鏈表中的key與當前put key一致的TreeNode,那此時探測節點就是插入父節點的所在了，然后就是判斷插入節點的hash值和父節點的hash值大小決定插入到父節點的左子樹還是右子樹，當然插入會打破平衡，還需要一個紅黑樹的平衡演算法保持平衡，

2. 其次第二種情況就是根節點在向下探測程序中發現TreeNode中key與當前put的key完全一致，然后就也是一次repleace操作，替換value，

六、jdk8中HashMap為什么要引入紅黑樹？

其實主要就是為了解決jdk1.8以前hash沖突所導致的鏈化嚴重的問題，因為鏈表結構的查詢效率是非常低的，他不像陣列，能通過索引快速找到想要的值，鏈表只能挨個遍歷，當hash沖突非常嚴重的時候，鏈表過長的情況下，就會嚴重影響查詢性能，本身散列串列最理想的查詢效率為O(1)，當時鏈化后鏈化特別嚴重，他就會導致查詢退化為O(n)為了解決這個問題所以jdk8中的HashMap添加了紅黑樹來解決這個問題，當鏈表長度>=8的時候鏈表就會變成紅黑樹，紅黑樹其實就是一顆特殊的二叉排序樹嘛，這個時間復雜…反正就是要比串列強很多

七、擴容后的新table陣列，那老陣列中的這個資料怎么遷移呢

遷移其實就是挨個桶位推進遷移，就是一個桶位一個桶位的處理，主要還是看當前處理桶位的資料狀態把，這里也是分了大概四種狀態：
這四種的遷移規則都不太一樣

(1.)第一種就是陣列下標下內容為空：
這種情況下就沒什么可說的，不用做什么處理，

( 2.)第二種情況就是陣列下標下內容不為空，但它參考的node還沒有鏈化：
當slot它不為空，但它參考的node還沒有鏈化的時候，說明這個槽位它沒有發生過hash沖突，直接遷移就好了，根據新表的tableSize計算出他在新表的位置,然后存放進去就好了，

( 3.)第三種就是slot內儲存了一個鏈化的node：
當node中next欄位它不為空，說明槽位發生過hash沖突，這個時候需要把當前槽位中保存的這個鏈表拆分成兩個鏈表，分別是高位鏈和低位鏈

(4.)第四種就是該槽位儲存了一個紅黑樹的根節點TreeNode物件：
這個就很復雜了，本文章暫時不做過多的介紹（博主還沒整明白 =_=! ）