HashMap
Hash ：散列澜术，通過關(guān)于鍵值(key)的函數(shù)强窖，將數(shù)據(jù)映射到內(nèi)存存儲(chǔ)中一個(gè)位置來(lái)訪問岂却。這個(gè)過程叫做Hash井氢，這個(gè)映射函數(shù)稱做散列函數(shù)弦追，存放記錄的數(shù)組稱做散列表(Hash Table),又叫哈希表岳链。JAVA函數(shù)hashCode()即請(qǐng)求對(duì)象的哈希值花竞。
哈希表、散列表
保存“鍵值對(duì)”
方法
put(k, v)
get(k)
remove(k)
size()
1.1哈希運(yùn)算過程
HashMap顳部使用Entry[]數(shù)組來(lái)存放數(shù)據(jù)
數(shù)組默認(rèn)的初始長(zhǎng)度是16
調(diào)用key.hashCode()獲取鍵的哈希值
用哈希值來(lái)計(jì)算下標(biāo)i
把鍵值對(duì)封裝成Entry對(duì)象，放入i位
空位置约急，直接放入
有數(shù)據(jù)零远，依次用equals（）比較鍵是否相等
? 找到相等的，覆蓋值
? 沒有相等的厌蔽，用鏈表連接在一起
負(fù)載率/加載因子到0.75（數(shù)據(jù)數(shù)量/數(shù)組容量）
（注：裝填因子(載荷因子)
散列表的載荷因子定義為：
? α = 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度.
α是散列表裝滿程度的標(biāo)志因子牵辣。由于表長(zhǎng)是定值，α與“填入表中的元素個(gè)數(shù)”成正比奴饮，所以纬向，α越大，表明填入表中的元素越多戴卜，產(chǎn)生沖突的可能性就越大逾条；反之，α越小投剥，標(biāo)明填入表中的元素越少师脂，產(chǎn)生沖突的可能性就越小。實(shí)際上江锨，散列表的平均查找長(zhǎng)度是載荷因子α的函數(shù)吃警，只是不同處理沖突的方法有不同的函數(shù)。
對(duì)于開放定址法啄育，荷載因子是特別重要因素酌心，應(yīng)嚴(yán)格限制在0.7-0.8以下。超過0.8挑豌，查表時(shí)的CPU緩存不命中（cache missing）按照指數(shù)曲線上升谒府。因此，一些采用開放定址法的hash庫(kù)浮毯，如Java的系統(tǒng)庫(kù)限制了荷載因子為0.75完疫，超過此值將resize散列表。
（原文：https://blog.csdn.net/yt618121/article/details/81162836）
所有數(shù)據(jù)重新執(zhí)行哈希運(yùn)算债蓝，放入新數(shù)組
[if !supportLists]l? [endif]jdk1.8
鏈表長(zhǎng)度到8壳鹤，轉(zhuǎn)成紅黑樹
樹上的數(shù)據(jù)減少到6，轉(zhuǎn)會(huì)成鏈表
哈希運(yùn)算測(cè)試
學(xué)生對(duì)象饰迹，對(duì)應(yīng)成績(jī)
stu1??95
stu2??91
放入重復(fù)的學(xué)生芳誓，對(duì)應(yīng)一個(gè)新的值，覆蓋之前的成績(jī)
