[[420125]]

前言

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

今天我們來講解分析下

一、HashMap底層實現(xiàn)原理解析

我們常見的有數(shù)據(jù)結(jié)構(gòu)有三種結(jié)構(gòu)：數(shù)組結(jié)構(gòu) 、鏈表結(jié)構(gòu) 、哈希表結(jié)構(gòu)

1、數(shù)組結(jié)構(gòu)

存儲區(qū)間是連續(xù)，且占用內(nèi)存嚴(yán)重，空間復(fù)雜也很大，時間復(fù)雜為O(1)。

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

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

2、鏈表結(jié)構(gòu)

區(qū)間離散，占用內(nèi)存寬松，空間復(fù)雜度小，時間復(fù)雜度O(N)。

優(yōu)點：插入刪除速度快，內(nèi)存利用率高，沒有大小固定，擴展靈活。

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

3、哈希表結(jié)構(gòu)

結(jié)合數(shù)組結(jié)構(gòu)和鏈表結(jié)構(gòu)的優(yōu)點，從而實現(xiàn)了查詢和修改效率高，插入和刪除效率也高的一種數(shù)據(jù)結(jié)構(gòu)

常見的HashMap就是這樣的一種數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

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

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

(1)先調(diào)用k的hashCode()方法得出哈希值，并通過哈希算法轉(zhuǎn)換成數(shù)組的下標(biāo)。

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

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

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

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

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

因為equals方法默認(rèn)比較的是兩個對象的內(nèi)存地址

二、HashMap紅黑樹原理分析

相比 jdk1.7 的 HashMap 而言，jdk1.8最重要的就是引入了紅黑樹的設(shè)計，當(dāng)hash表的單一鏈表長度超過 8 個的時候，鏈表結(jié)構(gòu)就會轉(zhuǎn)為紅黑樹結(jié)構(gòu)。

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

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

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

關(guān)于紅黑樹的內(nèi)容，網(wǎng)上給出的內(nèi)容非常多，主要有以下幾個特性：

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