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)

/**
?*?測(cè)試hash算法
?*/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òng)力節(jié)點(diǎn)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òng)力節(jié)點(diǎn)官網(wǎng)Java視頻教程，免費(fèi)下載學(xué)習(xí)。