HashMap的底層實(shí)現(xiàn)原理

HashMap底層實(shí)現(xiàn)采用的是哈希表，一種非常重要的數(shù)據(jù)結(jié)構(gòu)

哈希表的基本結(jié)構(gòu)是:數(shù)組+鏈表

數(shù)組的特點(diǎn)：占用空間連續(xù)，尋址容易，查詢速度快.但是，增加和刪除的效率非常低

鏈表的特點(diǎn)：占用空間不連續(xù)，尋址困難，查詢速度慢.但是，增加和刪除的效率非常高

HashMap源碼兩個(gè)核心內(nèi)容：Entry[]table就是HashMap的核心數(shù)組結(jié)構(gòu)，也稱之為位桶數(shù)組；Entry對象是一個(gè)單向鏈表的結(jié)構(gòu)，里面存儲(chǔ)了四個(gè)重要的屬性hash,key,value,next

如下圖：

HashMap存儲(chǔ)數(shù)據(jù)的過程put(key,value)如下：

步驟如下：

1、獲得key對象的hashcode–首先調(diào)用key對象的hashcode()方法，獲得hashcode.

2、根據(jù)hashcode計(jì)算出hash值(要求在[0,數(shù)組長度-1]區(qū)間)，hashcode是一個(gè)整數(shù)，需要將它轉(zhuǎn)化為[0,數(shù)組長度-1]的范圍，要求轉(zhuǎn)化后的hash值盡量均勻地分布在[0,數(shù)組長度-1]這個(gè)區(qū)間，減少"hash沖突".

一種極端簡單和低下的算法:

hash值=hashcode/hashcode;

也就是說，hash值總是1，意味著鍵值對對象會(huì)存儲(chǔ)到數(shù)組索引1位置，這樣就形成一個(gè)非常長的鏈表，相當(dāng)于每存儲(chǔ)一個(gè)對象都會(huì)發(fā)生"hash沖突"，HashMap也退化為一個(gè)"鏈表".

一種簡單和常用的算法是(相除取余算法):

hash值=hashcode%數(shù)組長度

這種算法可以讓hash值均勻的分布在[0,數(shù)組長度-1]的區(qū)間，早期的HashTable就是采用這種算法。但是，這種算法由于使用了"除法"，效率低下。JDK后來改進(jìn)了算法，首先約定數(shù)組長度必須為2的整數(shù)冪，這樣采用位運(yùn)算即可實(shí)現(xiàn)取余的效果：hash值=hashcode&(數(shù)組長度-1)

/**
?*?測試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對象

一個(gè)Entry對象包含四個(gè)部分，key對象、value對象、hash值、指向下一個(gè)Entry對象的引用，現(xiàn)在算出了hash值，下一個(gè)Entry對象的引用為null。

4、將Entry對象放到table數(shù)組中

如果本Entry對象對應(yīng)的數(shù)組索引位置還沒有放Entry對象，則直接將Entry對象存儲(chǔ)進(jìn)數(shù)組，如果對應(yīng)索引位置已經(jīng)有Entry對象，則將已有Entry對象的next指向本Entry對象，形成鏈表。

動(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常見面試題分析

8.HashMap底層實(shí)現(xiàn)原理總結(jié)與展望

以上就是對“Java架構(gòu)師入門培訓(xùn)視頻之HashMap”的介紹，希望對大家有所幫助，還想學(xué)習(xí)更多關(guān)于Java的課程，可以關(guān)注動(dòng)力節(jié)點(diǎn)官網(wǎng)Java視頻教程，免費(fèi)下載學(xué)習(xí)。