Java8中HashMap有必要來看下探討下了

創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、梁子湖網(wǎng)絡(luò)推廣、小程序設(shè)計(jì)、梁子湖網(wǎng)絡(luò)營銷、梁子湖企業(yè)策劃、梁子湖品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供梁子湖建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18982081108，官方網(wǎng)址：muchs.cn

HashMap是Java開發(fā)當(dāng)中使用得非常多的一種數(shù)據(jù)結(jié)構(gòu)，因?yàn)槠淇梢钥焖俚亩ㄎ坏叫枰檎业綌?shù)據(jù)，其最快的速度可以達(dá)到O(1)，最差的時(shí)候也可以達(dá)到O(n)。本文以Java8中的HashMap做為分析原型，因?yàn)椴煌腏DK版本中的HashMap，可能存在著底層實(shí)現(xiàn)上的不一樣。

HashMap是通過數(shù)組存儲所有的數(shù)據(jù)，每個(gè)元素所存放數(shù)組的下標(biāo)，是根據(jù)該存儲元素的key的Hash值與該數(shù)組的長度減去1做與運(yùn)算，如下所示：

index?=?(length_of_array?-?1)?&?hash_of_the_key;

數(shù)組中存放元素的數(shù)據(jù)結(jié)構(gòu)使用了Node和TreeNode兩種數(shù)據(jù)結(jié)構(gòu)，在單個(gè)Hash值對應(yīng)的存儲元素小于8個(gè)時(shí)，默認(rèn)值為Node的單向鏈表形式存儲，當(dāng)單個(gè)Hash值存儲的元素大于8個(gè)時(shí)，其會使用TreeNode的數(shù)據(jù)結(jié)構(gòu)存儲。

因?yàn)樵趩蝹€(gè)Hash值對應(yīng)的元素小于等于8個(gè)時(shí)，其查詢時(shí)間最差為O(8)，但是當(dāng)單個(gè)Hash值對應(yīng)的元素大于8個(gè)時(shí)，再通過Node的單向鏈表的方式進(jìn)行查詢，速度上就會變得更慢了；這個(gè)時(shí)候HashMap就會將Node的普通節(jié)點(diǎn)轉(zhuǎn)為TreeNode（紅黑樹）進(jìn)行存儲，這是由于TreeNode占用的空間大小約為常規(guī)節(jié)點(diǎn)的兩倍，但是其查詢速度可以得到保證，這個(gè)是通過空間換時(shí)間了。當(dāng)TreeNode中包括的元素變得比較少時(shí)，為了存儲空間的占用，也會轉(zhuǎn)換為Node節(jié)點(diǎn)單向鏈表的方式實(shí)現(xiàn)，它們之間可以互相轉(zhuǎn)換的。

Node：

static?class?Node<K,V>?implements?Map.Entry<K,V>?{
?final?int?hash;
?final?K?key;
?V?value;?Node<K,V>?next;?Node(int?hash,?K?key,?V?value,?Node<K,V>?next)?{
?this.hash?=?hash;
?this.key?=?key;
?this.value?=?value;
?this.next?=?next;
?}
?......
}

可以看到每個(gè)Node中包括了4個(gè)屬性，分別為：

hash值：當(dāng)前Node的Hash值
key：當(dāng)前Node的keyvalue:當(dāng)前Node的valuenext:表示指向下一個(gè)Node的指針，相同hash值的Node，通過next進(jìn)行遍歷查找

TreeNode：

static?final?class?TreeNode<K,V>?extends?LinkedHashMap.Entry<K,V>?{?TreeNode<K,V>?parent;?//?red-black?tree?links
?TreeNode<K,V>?left;?TreeNode<K,V>?right;?TreeNode<K,V>?prev;?//?needed?to?unlink?next?upon?deletion
?boolean?red;?TreeNode(int?hash,?K?key,?V?val,?Node<K,V>?next)?{?super(hash,?key,?val,?next);
?}
?......
}

可以看到TreeNode使用的是紅黑樹（Red Black Tree）的數(shù)據(jù)結(jié)構(gòu)，紅黑樹是一種自平衡二叉查找樹，在進(jìn)行插入和刪除操作時(shí)通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能，即使在最壞情況運(yùn)行時(shí)間也是非常良好的，并且在實(shí)踐中是非常高效的，它可以在O(log n)時(shí)間內(nèi)做查找、插入和刪除等操作，這里的n 是樹中元素的數(shù)目。

以下是一張關(guān)于HashMap存儲結(jié)構(gòu)的示意圖：

Java8中HashMap有必要來看下探討下了

寫入數(shù)據(jù)（一切皆在注釋中）

其方法如下：

//寫入數(shù)據(jù)public?V?put(K?key,?V?value)?{?//首先根據(jù)hash方法，獲取對應(yīng)key的hash值，計(jì)算方法見后面
?return?putVal(hash(key),?key,?value,?false,?true);
}final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,boolean?evict)?{
?Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?i;?//判斷用戶存放元素的數(shù)組是否為空
?if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)?//為空則進(jìn)行初使化，并將初使化后的數(shù)組賦值給變量tab，數(shù)組的長值賦值給變量n
?n?=?(tab?=?resize()).length;?//判斷根據(jù)hash值與數(shù)組長度減1求與得到的下標(biāo)，
?//從數(shù)組中獲取元素并將其賦值給變量p(后續(xù)該變量p可以繼續(xù)使用)，并判斷該元素是否存在
?if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)?//如果不存在則創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將其放到數(shù)組對應(yīng)的下標(biāo)中
?tab[i]?=?newNode(hash,?key,?value,?null);?else?{//根據(jù)數(shù)組的下標(biāo)取到了元素，并且該元素p且不為空，下面要判斷p元素的類型是Node還是TreeNode
?Node<K,V>?e;?K?k;?//判斷該數(shù)組對應(yīng)下標(biāo)取到的第一值是不是與正在存入值的hash值相同、
?//key相等（可能是對象，也可能是字符串），如果相等，則將取第一個(gè)值賦值給變量e
?if?(p.hash?==?hash?&&
?((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
?e?=?p;?//判斷取的對象是不是TreeNode，如果是則執(zhí)行TreeNode的put方法
?else?if?(p?instanceof?TreeNode)
?e?=?((TreeNode<K,V>)p).putTreeVal(this,?tab,?hash,?key,?value);?else?{//是普通的Node節(jié)點(diǎn)，
?//根據(jù)next屬性對元素p執(zhí)行單向鏈表的遍歷
?for?(int?binCount?=?0;?;?++binCount)?{?//如果被遍歷的元素最后的next為空，表示后面沒有節(jié)點(diǎn)了，則將新節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的next屬性建立關(guān)系
?if?((e?=?p.next)?==?null)?{?//做為當(dāng)前節(jié)點(diǎn)的后面的一個(gè)節(jié)點(diǎn)
?p.next?=?newNode(hash,?key,?value,?null);?//判斷當(dāng)前節(jié)點(diǎn)的單向鏈接的數(shù)量（8個(gè)）是不是已經(jīng)達(dá)到了需要將其轉(zhuǎn)換為TreeNode了
?if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
?//如果是則將當(dāng)前數(shù)組下標(biāo)對應(yīng)的元素轉(zhuǎn)換為TreeNode
?treeifyBin(tab,?hash);?break;
?}?//判斷待插入的元素的hash值與key是否與單向鏈表中的某個(gè)元素的hash值與key是相同的，如果是則退出
?if?(e.hash?==?hash?&&
?((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))?break;
?p?=?e;
?}
?}?//判斷是否找到了與待插入元素的hash值與key值都相同的元素
?if?(e?!=?null)?{?//?existing?mapping?for?key
?V?oldValue?=?e.value;?//判斷是否要將舊值替換為新值
?if?(!onlyIfAbsent?||?oldValue?==?null)?//滿足于未指定不替換或舊值為空的情況，執(zhí)行將舊值替換為新值
?e.value?=?value;
?afterNodeAccess(e);?return?oldValue;
?}
?}
?++modCount;?if?(++size?>?threshold)
?resize();
?afterNodeInsertion(evict);?return?null;
}

Hash值的計(jì)算方法：

//?計(jì)算指定key的hash值，原理是將key的hash?code與hash?code無符號向右移16位的值，執(zhí)行異或運(yùn)算。//?在Java中整型為4個(gè)字節(jié)32位，無符號向右移16位，表示將高16位移到低16位上，然后再執(zhí)行異或運(yùn)行，也//?就是將hash?code的高16位與低16位進(jìn)行異或運(yùn)行。//?小于等于65535的數(shù)，其高16位全部都為0，因而將小于等于65535的值向右無符號移16位，則該數(shù)就變成了//?32位都是0，由于任何數(shù)與0進(jìn)行異或都等于本身，因而hash?code小于等于65535的key，其得到的hash值//?就等于其本身的hash?code。static?final?int?hash(Object?key)?{?int?h;?return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}

計(jì)算邏輯如下圖所示：

Java8中HashMap有必要來看下探討下了

讀取數(shù)據(jù)（一切皆在注釋中）

?public?V?get(Object?key)?{
?Node<K,V>?e;?//根據(jù)Key獲取元素
?if?((e?=?getNode(hash(key),?key))?==?null)?return?null;?if?(accessOrder)
?afterNodeAccess(e);?return?e.value;
?}?final?Node<K,V>?getNode(int?hash,?Object?key)?{
?Node<K,V>[]?tab;?Node<K,V>?first,?e;?int?n;?K?k;?//if語句的第一個(gè)判斷條件
?if?((tab?=?table)?!=?null?//將數(shù)組賦值給變量tab，將判斷是否為null
?&&?(n?=?tab.length)?>?0?//將數(shù)組的長值賦值給變量n
?&&?(first?=?tab[(n?-?1)?&?hash])?!=?null)?{//判斷根據(jù)hash和數(shù)組長度減1的與運(yùn)算，計(jì)算出來的的數(shù)組下標(biāo)的第一個(gè)元素是不是為空
?//判斷第一個(gè)元素是否要找的元素，大部份情況下只要hash值太集中，或者元素不是很多，第一個(gè)元素往往都是需要的最終元素
?if?(first.hash?==?hash?&&?//?always?check?first?node
?((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))?//第一個(gè)元素就是要找的元素，因?yàn)閔ash值和key都相等，直接返回
?return?first;?if?((e?=?first.next)?!=?null)?{//如果第一元素不是要找到的元，則判斷其next指向是否還有元素
?//有元素，判斷其是否是TreeNode
?if?(first?instanceof?TreeNode)?//是TreeNode則根據(jù)TreeNode的方式獲取數(shù)據(jù)
?return?((TreeNode<K,V>)first).getTreeNode(hash,?key);
?do?{//是Node單向鏈表，則通過next循環(huán)匹配，找到就退出，否則直到匹配完最后一個(gè)元素才退出
?if?(e.hash?==?hash?&&
?((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))?return?e;
?}?while?((e?=?e.next)?!=?null);
?}
?}?//沒有找到則返回null
?return?null;
?}

喜歡這篇文章的話，可以給作者點(diǎn)個(gè)喜歡，點(diǎn)下關(guān)注，每天都會分享Java相關(guān)文章！

記得一定要關(guān)注我哦，會不定時(shí)的福利贈送，包括整理的面試題，學(xué)習(xí)資料，源碼等~~

當(dāng)前名稱：Java8中HashMap有必要來看下探討下了
鏈接URL：http://muchs.cn/article36/gedgsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、App設(shè)計(jì)、Google、網(wǎng)站設(shè)計(jì)公司、企業(yè)建站、網(wǎng)站建設(shè)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容