[[420125]]

前言

HashMap是Java中最常用的集合類框架，也是Java語言中非常典型的數據結構，同時也是我們需要掌握的數據結構，更重要的是進大廠面試必問之一;

今天我們來講解分析下

一、HashMap底層實現原理解析

我們常見的有數據結構有三種結構：數組結構 、鏈表結構 、哈希表結構

1、數組結構

存儲區間是連續，且占用內存嚴重，空間復雜也很大，時間復雜為O(1)。

優點：是隨機讀取效率很高，原因數組是連續(隨機訪問性強，查找速度快)。

缺點：插入和刪除數據效率低，因插入數據，這個位置后面的數據在內存中要往后移的，且大小固定不易動態擴展。

2、鏈表結構

區間離散，占用內存寬松，空間復雜度小，時間復雜度O(N)。

優點：插入刪除速度快，內存利用率高，沒有大小固定，擴展靈活。

缺點：不能隨機查找，每次都是從第一個開始遍歷(查詢效率低)。

3、哈希表結構

結合數組結構和鏈表結構的優點，從而實現了查詢和修改效率高，插入和刪除效率也高的一種數據結構

常見的HashMap就是這樣的一種數據結構

4、HashMap中的put()和get()的實現原理：

①、map.put(k,v)實現原理

(1)首先將k,v封裝到Node對象當中(節點)。

(2)然后它的底層會調用K的hashCode()方法得出hash值。

(3)通過哈希表函數/哈希算法，將hash值轉換成數組的下標，下標位置上如果沒有任何元素，就把Node添加到這個位置上。如果說下標對應的位置上有鏈表。此時，就會拿著k和鏈表上每個節點的k進行equal。如果所有的equals方法返回都是false，那么這個新的節點將被添加到鏈表的末尾。如其中有一個equals返回了true，那么這個節點的value將會被覆蓋。

②、map.get(k)實現原理

(1)先調用k的hashCode()方法得出哈希值，并通過哈希算法轉換成數組的下標。

(2)通過上一步哈希算法轉換成數組的下標之后，在通過數組下標快速定位到某個位置上。如果這個位置上什么都沒有，則返回null。如果這個位置上有單向鏈表，那么它就會拿著K和單向鏈表上的每一個節點的K進行equals，如果所有equals方法都返回false，則get方法返回null。如果其中一個節點的K和參數K進行equals返回true，那么此時該節點的value就是我們要找的value了，get方法最終返回這個要找的value。

5、為何隨機增刪、查詢效率都很高的原因是?

原因: 增刪是在鏈表上完成的，而查詢只需掃描部分，則效率高。

HashMap集合的key，會先后調用兩個方法，hashCode and equals方法，這這兩個方法都需要重寫。

6、為什么放在hashMap集合key部分的元素需要重寫equals方法?

因為equals方法默認比較的是兩個對象的內存地址

二、HashMap紅黑樹原理分析

相比 jdk1.7 的 HashMap 而言，jdk1.8最重要的就是引入了紅黑樹的設計，當hash表的單一鏈表長度超過 8 個的時候，鏈表結構就會轉為紅黑樹結構。

為什么要這樣設計呢?好處就是避免在最極端的情況下鏈表變得很長很長，在查詢的時候，效率會非常慢。

• 紅黑樹查詢：其訪問性能近似于折半查找，時間復雜度 O(logn);
• 鏈表查詢：這種情況下，需要遍歷全部元素才行，時間復雜度 O(n);

簡單的說，紅黑樹是一種近似平衡的二叉查找樹，其主要的優點就是“平衡“，即左右子樹高度幾乎一致，以此來防止樹退化為鏈表，通過這種方式來保障查找的時間復雜度為 log(n)。

關于紅黑樹的內容，網上給出的內容非常多，主要有以下幾個特性：

• 每個節點要么是紅色，要么是黑色，但根節點永遠是黑色的;
• 每個紅色節點的兩個子節點一定都是黑色;
• 紅色節點不能連續(也即是，紅色節點的孩子和父親都不能是紅色);
• 從任一節點到其子樹中每個葉子節點的路徑都包含相同數量的黑色節點;
• 所有的葉節點都是是黑色的(注意這里說葉子節點其實是上圖中的 NIL 節點);
• 在樹的結構發生改變時(插入或者刪除操作)，往往會破壞上述條件 3 或條件 4，需要通過調整使得查找樹重新滿足紅黑樹的條件;