一、HashMap
數(shù)組+最簡單的原理
[<張三屠阻，32歲>红省，<李四，54歲>] —>數(shù)組
對(duì)key計(jì)算出一個(gè)hash值国觉，根據(jù)這個(gè)hash值對(duì)數(shù)組進(jìn)行取模吧恃，也就是index,定位到數(shù)組里的元素中去
map.get(“張三“) —> hash值 —> 對(duì)數(shù)組長度進(jìn)行取模 —> return array[1]
Array[1]= <李四，54歲>
二麻诀、jdk1.8中對(duì)hash算法和尋址算法
1痕寓、hash值進(jìn)行右移 16位，把2進(jìn)制往右邊推16位蝇闭，把高16位推到低16位上來呻率，前面用0來補(bǔ)齊，然后原來的hash值 與 右移出來的hash值 進(jìn)行異或? ? 異或出來的hash值包含了高16位與低16位hash值得特征呻引。使高低16位都參與了運(yùn)算
異或出來的? hash值? 就是一個(gè)32位的 int值
異或? 兩個(gè)一樣? 是0礼仗；? ? 兩個(gè)不一樣 是1?
如 1? 0
? ? 1? 1
? ? 0? 1
數(shù)組—> hash值對(duì)數(shù)組長度取模，定位到數(shù)組的一個(gè)位置
2逻悠、優(yōu)化地方元践，尋址算法優(yōu)化
（n-1）& hash —> 數(shù)組里的一個(gè)位置
取模運(yùn)算，他是性能比較差童谒，為了優(yōu)化這個(gè)數(shù)組尋址的過程
（n-1）& hash —>效果要跟hash對(duì)n取模单旁，效果是一樣的，但是與運(yùn)算的性能要比hash對(duì)n取模要高很多
總結(jié)jdk1.8中對(duì)hash算法和尋址算法是如何優(yōu)化的饥伊？
1象浑、hash算法的優(yōu)化：對(duì)每個(gè)hash值蔫饰，在他的低16位中，讓高低16位進(jìn)行異或融柬，讓他的低16位同時(shí)保持了高低16位的特征死嗦，盡量避免一些hash值后續(xù)出現(xiàn)沖突趋距，大家可能會(huì)進(jìn)入數(shù)組的同一個(gè)位置粒氧。
2、尋址算法的優(yōu)化：用與運(yùn)算替代取模节腐，提升性能外盯。
三、解決hash沖突問題翼雀，鏈表+紅黑樹饱苟，O(n)和O(logn)
map.put 和 map.get —> hash算法優(yōu)化（避免hash沖突），尋址性能優(yōu)化
算出key 的hash值狼渊，到數(shù)組中尋址箱熬，找到一個(gè)位置，把key-value對(duì)放進(jìn)數(shù)組狈邑，或從數(shù)組里取出來
兩個(gè)key? 多個(gè)key 城须，他們算出來的hash值，與n-1 米苹，與運(yùn)算后糕伐，發(fā)現(xiàn)定位出來的數(shù)組的位置還是一樣的，hash碰撞蘸嘶，hash沖突
會(huì)在這位置掛一個(gè)鏈表良瞧，這個(gè)鏈表里放入多個(gè)元素，讓多個(gè)key-value 對(duì)训唱，同時(shí)放在數(shù)組的一個(gè)位置離
get褥蚯，如果定位到這個(gè)數(shù)組里發(fā)現(xiàn)這個(gè)位置掛了一個(gè)鏈表，此時(shí)遍歷鏈表况增，找到你要的key-value對(duì)就可以了
假設(shè)這個(gè)鏈表很長赞庶，可能會(huì)導(dǎo)致遍歷鏈表，性能會(huì)比較差? O(n)
優(yōu)化巡通，如果鏈表的長度達(dá)到了一定的長度之后尘执，其實(shí)會(huì)把鏈表轉(zhuǎn)換為紅黑樹，遍歷一顆紅黑樹找到一個(gè)元素宴凉，此時(shí)O(logn)誊锭，性能會(huì)比鏈表高一些
