1.HashMap底層原理 數(shù)據(jù)結構
????底層使用哈希表(數(shù)組+鏈表進行存儲),在jdk1.8后 當鏈表長度大于等于8時 將鏈表轉為紅黑樹 ,時間復雜度由O(n)變?yōu)镺(logn)

2.HashMap的put過程

????(1)對key計算hash值 求下標

????(2)如果沒有發(fā)生hash碰撞,直接放入桶中

????(3)如果發(fā)生碰撞,放在鏈表的后面 并計算鏈表長度 大于8轉為紅黑樹

????(4)如果節(jié)點已經(jīng)存在進行覆蓋

????(5)如果長度大于(長度*負載因子0.75) 進行擴容resize

3.HashMap中的hash函數(shù)是怎么實現(xiàn)的

? ? (1)高16bit不變 低16bit和高16bit做了一個異或(^)

? ? (2)(n-1)&hash? 得到下標

4.擴容過程是什么樣的,原來某位置的元素,移動到了新數(shù)組,位置怎么確定

????(1)擴容為原來的2倍,對每個節(jié)點重新計算hash值

? ? (2)可能的位置是原來的位置 或者是(原下標+原容量)的位置

5.hash沖突還有那些解決辦法

? ? 開放定址法(線性探測) 鏈地址法?再哈希法

6.鏈表查找某個元素的時間復雜度是O(n),怎么優(yōu)化

? ? 單向鏈表 無法優(yōu)化 一種是hashMap實現(xiàn)的紅黑樹 另一種是可以通過雙向鏈表來實現(xiàn) 這樣就可以使用折半查找 但是因為要保存上一個元素的地址 更加耗費內(nèi)存空間