[[420125]]

前言

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

今天我們來(lái)講解分析下

一、HashMap底層實(shí)現(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)

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

優(yōu)點(diǎn)：是隨機(jī)讀取效率很高，原因數(shù)組是連續(xù)(隨機(jī)訪問(wèn)性強(qiáng)，查找速度快)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因?yàn)閑quals方法默認(rèn)比較的是兩個(gè)對(duì)象的內(nèi)存地址

二、HashMap紅黑樹原理分析

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

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

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

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

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

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