建站
咨詢
售后
建站咨詢
新聞中心
[[420125]]
前言
HashMap是Java中最常用的集合類框架，也是Java語言中非常典型的數(shù)據(jù)結(jié)構(gòu)，同時也是我們需要掌握的數(shù)據(jù)結(jié)構(gòu)，更重要的是進(jìn)大廠面試必問之一;
成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),孟村企業(yè)網(wǎng)站建設(shè),孟村品牌網(wǎng)站建設(shè),網(wǎng)站定制,孟村網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,孟村網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。
今天我們來講解分析下
一、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)點：是隨機(jī)讀取效率很高，原因數(shù)組是連續(xù)(隨機(jī)訪問性強(qiáng)，查找速度快)。
缺點：插入和刪除數(shù)據(jù)效率低，因插入數(shù)據(jù)，這個位置后面的數(shù)據(jù)在內(nèi)存中要往后移的，且大小固定不易動態(tài)擴(kuò)展。
2、鏈表結(jié)構(gòu)
區(qū)間離散，占用內(nèi)存寬松，空間復(fù)雜度小，時間復(fù)雜度O(N)。
優(yōu)點：插入刪除速度快，內(nèi)存利用率高，沒有大小固定，擴(kuò)展靈活。
缺點：不能隨機(jī)查找，每次都是從第一個開始遍歷(查詢效率低)。
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進(jìn)行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進(jìn)行equals，如果所有equals方法都返回false，則get方法返回null。如果其中一個節(jié)點的K和參數(shù)K進(jìn)行equals返回true，那么此時該節(jié)點的value就是我們要找的value了，get方法最終返回這個要找的value。
5、為何隨機(jī)增刪、查詢效率都很高的原因是?
原因: 增刪是在鏈表上完成的，而查詢只需掃描部分，則效率高。
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)整使得查找樹重新滿足紅黑樹的條件;
當(dāng)前名稱：數(shù)據(jù)結(jié)構(gòu)之HashMap底層實現(xiàn)原理詳解
文章路徑：http://www.5511xx.com/article/cojhgps.html
