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

hashmap是線程不安全的 :?

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

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

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

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

哈希算法 :?

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