HashMap的底層實(shí)現(xiàn)原理
HashMap底層實(shí)現(xiàn)采用的是哈希表，一種非常重要的數(shù)據(jù)結(jié)構(gòu)
哈希表的基本結(jié)構(gòu)是:數(shù)組+鏈表
數(shù)組的特點(diǎn)：占用空間連續(xù)，尋址容易，查詢(xún)速度快.但是，增加和刪除的效率非常低
鏈表的特點(diǎn)：占用空間不連續(xù)，尋址困難，查詢(xún)速度慢.但是，增加和刪除的效率非常高
HashMap源碼兩個(gè)核心內(nèi)容：Entry[]table就是HashMap的核心數(shù)組結(jié)構(gòu)，也稱(chēng)之為位桶數(shù)組；Entry對(duì)象是一個(gè)單向鏈表的結(jié)構(gòu)，里面存儲(chǔ)了四個(gè)重要的屬性hash,key,value,next
如下圖：
HashMap存儲(chǔ)數(shù)據(jù)的過(guò)程put(key,value)如下：
步驟如下：
1、獲得key對(duì)象的hashcode–首先調(diào)用key對(duì)象的hashcode()方法，獲得hashcode.
2、根據(jù)hashcode計(jì)算出hash值(要求在[0,數(shù)組長(zhǎng)度-1]區(qū)間)，hashcode是一個(gè)整數(shù)，需要將它轉(zhuǎn)化為[0,數(shù)組長(zhǎng)度-1]的范圍，要求轉(zhuǎn)化后的hash值盡量均勻地分布在[0,數(shù)組長(zhǎng)度-1]這個(gè)區(qū)間，減少"hash沖突".
一種極端簡(jiǎn)單和低下的算法:
hash值=hashcode/hashcode;
也就是說(shuō)，hash值總是1，意味著鍵值對(duì)對(duì)象會(huì)存儲(chǔ)到數(shù)組索引1位置，這樣就形成一個(gè)非常長(zhǎng)的鏈表，相當(dāng)于每存儲(chǔ)一個(gè)對(duì)象都會(huì)發(fā)生"hash沖突"，HashMap也退化為一個(gè)"鏈表".
一種簡(jiǎn)單和常用的算法是(相除取余算法):
hash值=hashcode%數(shù)組長(zhǎng)度
這種算法可以讓hash值均勻的分布在[0,數(shù)組長(zhǎng)度-1]的區(qū)間，早期的HashTable就是采用這種算法。但是，這種算法由于使用了"除法"，效率低下。JDK后來(lái)改進(jìn)了算法，首先約定數(shù)組長(zhǎng)度必須為2的整數(shù)冪，這樣采用位運(yùn)算即可實(shí)現(xiàn)取余的效果：hash值=hashcode&(數(shù)組長(zhǎng)度-1)
public?class?TestHash?{ public?static?void?main(String[]?args)?{ int?hashcode?=?1111; int?length?=?16;//length為2的整數(shù)冪，則hashcode&(length-1)相當(dāng)于hashcode%length myhash(hashcode,?length); } public?static?void?myhash(int?hashcode,int?length){ //取余 System.out.println(hashcode%length); //length為2的整數(shù)冪情況下，和取余的值一樣 System.out.println(hashcode&(length-1)); }}3、生成Entry對(duì)象
一個(gè)Entry對(duì)象包含四個(gè)部分，key對(duì)象、value對(duì)象、hash值、指向下一個(gè)Entry對(duì)象的引用，現(xiàn)在算出了hash值，下一個(gè)Entry對(duì)象的引用為null。
4、將Entry對(duì)象放到table數(shù)組中
如果本Entry對(duì)象對(duì)應(yīng)的數(shù)組索引位置還沒(méi)有放Entry對(duì)象，則直接將Entry對(duì)象存儲(chǔ)進(jìn)數(shù)組，如果對(duì)應(yīng)索引位置已經(jīng)有Entry對(duì)象，則將已有Entry對(duì)象的next指向本Entry對(duì)象，形成鏈表。
深圳達(dá)內(nèi)教育HashMap底層實(shí)現(xiàn)原理視頻教程，快速掌握HashMap技術(shù)，強(qiáng)化自身技能：
課程學(xué)習(xí)目錄
1.HashMap底層數(shù)據(jù)結(jié)構(gòu)分析
2.JDK1.7中的HashMap底層實(shí)現(xiàn)分析
3.JDK1.8中的HashMap底層實(shí)現(xiàn)分析
4.HashMap的put操作源碼分析（上）
5.HashMap的put操作源碼分析（下）
6.HashMap的get操作源碼分析
7.HashMap常見(jiàn)面試題分析
8.HashMap底層實(shí)現(xiàn)原理總結(jié)與展望
以上就是對(duì)“Java架構(gòu)師入門(mén)培訓(xùn)視頻之HashMap”的介紹，希望對(duì)大家有所幫助，還想學(xué)習(xí)更多關(guān)于Java的課程，可以關(guān)注深圳達(dá)內(nèi)教育官網(wǎng)Java視頻教程，免費(fèi)下載學(xué)習(xí)。
Java培訓(xùn)視頻
