hashmap是一個(gè)以key,value形式存儲(chǔ)的集合,在JDK1.7中是以數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu),在JDK1.8中是數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu),他在對(duì)數(shù)據(jù)操作時(shí)繼承了數(shù)組的線性查找和鏈表的尋址修改

hashmap是線程不安全的 :?

1. ?在JDK1.7中會(huì)造成環(huán)形鏈和數(shù)據(jù)丟失的情況
2. ?在JDK1.8中hashmap的put過程會(huì)造成數(shù)據(jù)覆蓋的情況
3. put過程 :?
   1. 會(huì)對(duì)key計(jì)算求hash值,判斷是否發(fā)生哈希碰撞(計(jì)算出的哈希值相同)
   2. 發(fā)生了碰撞就放入bucket桶里面,沒有發(fā)生哈希碰撞就以鏈表的形式鏈接到后面
   3. hashmap的存儲(chǔ)過程 : 如果鏈表的長度大于8會(huì)轉(zhuǎn)為紅黑樹,如果鏈表的長度小于6會(huì)從紅黑樹轉(zhuǎn)為鏈表
   4. 然后就會(huì)去判斷節(jié)點(diǎn)上是否有值 ,有值的話會(huì)覆蓋舊值
   5. 如果桶滿了會(huì)進(jìn)行擴(kuò)容2倍在重排

其實(shí)hashmap主要的目的就是存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的,查詢的方式通過哈希算法計(jì)算的

首先他的結(jié)構(gòu)組成分為 :?

1. 數(shù)組結(jié)構(gòu) :
   1. 他是采用一段連續(xù)的存儲(chǔ)單元來存儲(chǔ)數(shù)據(jù)的
      1. 查詢 : 由于數(shù)組元素下標(biāo)是連續(xù)且自增的所以在做查詢時(shí)可以直接通過下標(biāo)找到對(duì)應(yīng)的節(jié)點(diǎn),一般在查詢頻繁的場(chǎng)景下使用最多
      2. 增刪 :?當(dāng)插入一個(gè)元素時(shí),這個(gè)元素在數(shù)組中是沒有下標(biāo)的,需要將元素添加到數(shù)組中的某個(gè)位置,那么在該元素之后的下標(biāo)都會(huì)向后移動(dòng),以至于后面的節(jié)點(diǎn)也要有相應(yīng)的改變,刪除會(huì)造成下標(biāo)向前移動(dòng)
   2. ArrayList : 就是一個(gè)基于數(shù)組結(jié)構(gòu)的集合,查詢快,增刪慢,
      1. 他還有一個(gè)擴(kuò)容機(jī)制 : 它的默認(rèn)容量是10,在使用ArrayList做增刪時(shí),他會(huì)創(chuàng)建一個(gè)新的數(shù)組且這個(gè)數(shù)組是原數(shù)組容量的1.5倍,并將原數(shù)組中的元素拷貝一份到新的數(shù)組中去,所以一般我們使用ArrayList做增刪時(shí)需要指定它的容量
2. 鏈表結(jié)構(gòu) :?
   1. 鏈表是一種物理存儲(chǔ)單元上非連續(xù),非順序的存儲(chǔ)結(jié)構(gòu),它的特點(diǎn)是增刪快,查詢慢
      1. 查詢 : 它的查詢需要通過頭節(jié)點(diǎn)將整個(gè)鏈表都遍歷一次,以至于查詢效率很慢
      2. 增刪 : 新增時(shí)上一個(gè)節(jié)點(diǎn)指向插入的節(jié)點(diǎn),插入的節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn);只需要去改變指針的指向就可以完成增刪操作
   2. LinkedList : 是基于鏈表結(jié)構(gòu)的,查詢慢,增刪快

哈希算法 :?

1. 哈希算法(不可逆的,冪等性的算法)也叫作散列算法,也就是把任意長度值(key)通過散列算法變換成固定長度的key(地址),通過這個(gè)地址進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu),他通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄,從而加快查找速度
2. 將lies計(jì)算出來的ascii碼相加
3. 然后除以10取模
   1. 為什么不直接存儲(chǔ),要進(jìn)行取模?
      1. 因?yàn)閿?shù)組是采用一段連續(xù)的存儲(chǔ)單元來存儲(chǔ)數(shù)據(jù)的,直接存儲(chǔ)的話值會(huì)很大,其中會(huì)浪費(fèi)很多的空間,取模的目的就是為了節(jié)省內(nèi)存空間
         1. 取模會(huì)出現(xiàn)的問題 :
            • 會(huì)發(fā)生哈希沖突(哈希碰撞) :
              • lies的值通過ascii碼計(jì)算的總和
              • foes的值通過ascii計(jì)算的總和
              • lies和foes取模之后的值相同,雖然他兩是不同的key,但是數(shù)組存同一個(gè)下標(biāo)元素時(shí)會(huì)進(jìn)行覆蓋,這就是哈希碰撞
            • 哈希碰撞解決方式 :?
              • 使用鏈表解決 : 根據(jù)鏈表的指針,可以讓lies指向foes,讓foes去匹配下標(biāo),如果匹配lies不相等,則去匹配下一個(gè)節(jié)點(diǎn)foes,最終找到這個(gè)foes
              • 這也是JDK1.8中引入紅黑樹的原因 : hashmap的存取過程
                • 創(chuàng)建一個(gè)hasdmap集合并指定它的容量
                • 往集合中添加元素時(shí),當(dāng)容量不夠,就只能把這個(gè)數(shù)據(jù)放到鏈表上,鏈表是無線延長的,又因?yàn)殒湵淼牟樵兯俣仁潜容^慢的,那么哈希沖突也就會(huì)變得十分嚴(yán)重,查詢末端數(shù)據(jù)的性能也就會(huì)變得很低(總結(jié) : jdk1.7的hashmap需要解決鏈表過長查詢效率低下的問題)
                • 在jdk1.8中 : 使用紅黑樹去判斷小中大(也就是左邊的小于右邊的),他的插入速度慢,而鏈表插入快,刪除快