HashMap基礎知識
HashMap的小知識
- HashMap基礎知識
- 前言
- 一、HashMap的預備知識
- 二、HashMap的底層實作原理
- 三、HashMap的1.7和1.8
- 四、HashMap的put與get
前言
文章分為五部分
HashMap的預備知識
HashMap的底層實作原理
HashMap的1.7和1.8
HashMap的put與get
提示：以下是本篇文章正文內容，下面案例可供參考
一、HashMap的預備知識
1.HashMap是Map的常用子類
java.util.HashMap<k,v> 集合 implements Map<k,v>介面
2.HashMap集合特點
HashMap集合底層是哈希表，查詢速度特別快
jdk1.7：陣列+單向鏈表
jdk1.8：陣列+單向鏈表/紅黑樹（鏈表長度超過8，陣列達到64）
3.HashMap集合是一個無序的集合，存盤元素和取出元素的順序有可能不一致
二、HashMap的底層實作原理
HashMap是Java中的最頻繁的一種資料結構
在深入HashMap前先明白兩種資料結構，陣列和鏈表
陣列
查詢速度快，可以根據索引查詢；但插入和洗掉比較困難
鏈表
查詢速度慢，需要遍歷整個鏈表，但插入和洗掉操作比較容易，
HashMap
底層是一個hash表（陣列+鏈表），這種結構集合了陣列和鏈表的好處 ，在jdk1.7中，只是單純的陣列+鏈表的結構，但是如果散串列中的hash碰撞過多時，會造成效率的降低，所以在JKD1.8中對這種情況進行了控制，當一個hash值上的鏈表長度大于8時，該節點上的資料就不再以鏈表進行存盤，而是轉成了一個紅黑樹
HashMap 基于 Hash 演算法實作的
- 當我們往Hashmap中put元素時，利用key的hashCode重新hash計算出當前物件的元素在陣列中的下標
- 存盤時，如果出現hash值相同的key，此時有兩種情況，(1)如果key相同，則覆寫原始值；(2)如果key不同（出現沖突），則將當前的key-value放入鏈表中
- 獲取時，直接找到hash值對應的下標，在進一步判斷key是否相同，從而找到對應值，
- 理解了以上程序就不難明白HashMap是如何解決hash沖突的問題，核心就是使用了陣列的存盤方式，然后將沖突的key的物件放入鏈表中，一旦發現沖突就在鏈表中做進一步的對比，
三、HashMap的1.7和1.8
JDK1.7
JDK1.7采用的是拉鏈法，拉鏈法：將鏈表和陣列相結合，也就是說創建一個鏈表陣列，陣列中每一格就是一個鏈表，若遇到哈希沖突，則將沖突的值加到鏈表中即可，
JDK1.8
相比于之前的版本，jdk1.8在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）同時陣列長度達到64，將鏈表轉化為紅黑樹，以減少搜索時間，(紅黑樹節點為6時轉回鏈表)
JDK1.8主要對HashMap進行了一系列優化
- resize 擴容優化
- 引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率，紅黑樹演算法請參考
- 解決了多執行緒死回圈問題，但仍是非執行緒安全的，多執行緒時可能會造成資料丟失問題，
四、HashMap的put與get
put方法
key的hashcode經過高低位異或后的值，然后(table.length - 1) & hash得到槽位下標
- 此時有四種情況
- 當槽位（slot）為空，key和value包裝為一個node物件，直接存盤占用一個slot
- 槽位不為空，判斷key是否一樣，一樣則進行value替換；否則為hash沖突，存入鏈表中
- 已經鏈化，和2程序相同，比較存入鏈表但是會判斷是否達到了樹化的擴容閾值標準
- 紅黑樹的寫入操作
get方法
拿到key算出對應索引
5. 根據得到的索引，映射到對應的哈希桶，判斷該元素是不是頭結點，如果是則直接拿到
6. 如果不是頭一個節點，用do while回圈遍歷鏈表，鏈表都是next指向一次拿元素
7. 如果是紅黑樹，由于添加時保證樹有序，則利用折半法遍歷紅黑樹
如有不足，歡迎指出，共同進步！
- 文章著作權歸作者所有，歡迎轉載
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/274710.html
標籤：java