HashMap的底層實現原理

HashMap底層實現采用的是哈希表，一種非常重要的數據結構

哈希表的基本結構是:數組+鏈表

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

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

HashMap源碼兩個核心內容：Entry[]table就是HashMap的核心數組結構，也稱之為位桶數組；Entry對象是一個單向鏈表的結構，里面存儲了四個重要的屬性hash,key,value,next

如下圖：

HashMap存儲數據的過程put(key,value)如下：

步驟如下：

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

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

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

hash值=hashcode/hashcode;

也就是說，hash值總是1，意味著鍵值對對象會存儲到數組索引1位置，這樣就形成一個非常長的鏈表，相當于每存儲一個對象都會發生"hash沖突"，HashMap也退化為一個"鏈表".

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

hash值=hashcode%數組長度

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

/**
?*?測試hash算法
?*/public?class?TestHash?{
	public?static?void?main(String[]?args)?{
		int?hashcode?=?1111;
		int?length?=?16;//length為2的整數冪，則hashcode&(length-1)相當于hashcode%length
		myhash(hashcode,?length);
	}
	public?static?void?myhash(int?hashcode,int?length){
		//取余
		System.out.println(hashcode%length);
		//length為2的整數冪情況下，和取余的值一樣
		System.out.println(hashcode&(length-1));
	}}

3、生成Entry對象

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

4、將Entry對象放到table數組中

如果本Entry對象對應的數組索引位置還沒有放Entry對象，則直接將Entry對象存儲進數組，如果對應索引位置已經有Entry對象，則將已有Entry對象的next指向本Entry對象，形成鏈表。

動力節點HashMap底層實現原理視頻教程，快速掌握HashMap技術，強化自身技能：

課程學習目錄

1.HashMap底層數據結構分析

2.JDK1.7中的HashMap底層實現分析

3.JDK1.8中的HashMap底層實現分析

4.HashMap的put操作源碼分析（上）

5.HashMap的put操作源碼分析（下）

6.HashMap的get操作源碼分析

7.HashMap常見面試題分析

8.HashMap底層實現原理總結與展望

以上就是對“Java架構師入門培訓視頻之HashMap”的介紹，希望對大家有所幫助，還想學習更多關于Java的課程，可以關注動力節點官網Java視頻教程，免費下載學習。