Java常見面試題 -- HashMap 和HashTable

HashMap：

（1）基礎結構：

存儲的是存在映射關系的鍵值對，存儲在被稱哈希表的資料結構中，通過計算key的hashcode來确定兼職對在數組的位置。假如産生碰撞，則使用

連結清單

或者

紅黑樹

（注意key最好使用不可變類型，否則當對象發生變化時，重新計算它的hashcode值）

（2）優化方式（分布政策）：

1. 數組的長度始終保持為2的次幂
2. 将哈希值的高位參與運算
3. 通過位于操作來等價取模操作

(3) 動态擴容：

由于底層數組的長度始終為2的次幂，因為數組長度length會參與位與操作，來确定元素所在數組中的新位置，是以原數組中的元素所在位置要麼保持不動，要麼就是移動2次幂個位置，提高動态擴容效率

缺點：

1. 線程不安全，可能會在擴容時出現環形連結清單異常
2. 進行put操作容易出現同在髒資料讀取問題

差別

• HashMap方法沒有 synchronized修飾，線程非安全，HashTable 線程安全
• HashMap允許 key 和 value為 null，而HashTable不允許

底層實作：數組+連結清單實作

jdk8開始連結清單高度到8、數組長度超過64.連結清單轉變為紅黑樹，元素以内部類 Node節點存在

• 計算 key 的 hash 值，二次hash然後對數組長度取模，對應到數組下标
• 如果沒有産生 hash 沖突，先進行 equal 比較，相同則取代該元素。不同，則判斷連結清單高度插傳入連結表，連結清單高度達到8，并且數組長度到64則轉變為紅黑數，長度低于6則将紅黑樹轉回連結清單
• key 為 null ，存在小标0的位置