HashMap （JDK1.7：一維數組+單向鏈表，頭插法 JDK1.8：一維數組+單向鏈表+紅黑樹，尾插法）

默認長度為16，長度必須是2的冪 最大容量1<<30(十億多)

默認負載因子0.75

添加put過程

獲取key的hash值 -- hashCode()

通過hash值計算在數組中的下標

判斷下標上是否有元素存在

沒有 -- 創(chuàng)建entry對象，存入數組中

有 -- 判斷多個key是否相同 -- (hash)&&(== || equals)

相同 -- 替換原value值

不同 -- 添加元素(JDK1.7頭插法 ， JDK1.8尾插法)

HashMap內部類Entry(單向鏈表)

key value hash next

Hash回環(huán)解決

如果出現了Hash回環(huán)，不應該怪HashMap，因為HashMap明確表示該類不是一個線程安全的類，多線程下應使用ConcurrentHashMap

使用線程安全的ConcurrentHashMap

多線程下使用HashMap可能出現的情況

一個線程不斷添加元素，導致HashMap擴容

一個線程不斷遍歷元素（第一個線程在擴容期間發(fā)生了引用地址回環(huán)），當前線程遍歷時就會出現臟數據

默認的負載因子為什么是0.75？

取得了時間與空間的平衡

負載因子過大，利用了空間，浪費了時間

負載因子過小，利用了時間，浪費了空間

減少Hash碰撞的方法？

重寫equals和hashCode方法，equals底層為== 不重寫就無法判斷是否相同

為什么長度會是2的冪？(重要)

獲取元素在數組的下標是 元素的hash值&數組長度-1

如果數組的長度不是2的冪，-1就會導致二進制中的某幾位都是0，和元素的hash值做&運算，二進制上的某幾位就永遠是0，最終導致下標分布不均勻，浪費空間

HashMap什么時候擴容？

如果映射關系個數大于等于閾值 并且 當前下標上的元素不為null，就擴容

JDK1.7HashMap與JDK1.8HashMap的區(qū)別？

JDK1.7HashMap

數據結構：一維數組+單向鏈表

計算hash值：位運算

單項鏈表插值法：頭插法

JDK1.8HashMap

數據結構

一維數組+單向鏈表--鏈表長度>8&&數組長度>64 -->一維數組+紅黑樹（目的：提高查詢效率）

一維數組+紅黑樹--紅黑樹節(jié)點<6 --> 一維數組+單向鏈表

計算hash值：高16位^低16位（計算更加散列的hash值）

單項鏈表插值法：尾插法