1
概述
hashMap的基本結構
jdk8中hashmap的結構如上圖所示，它是由陣列+連結串列+紅黑樹組成，jdk8之前是由陣列+連結串列組成，那麼為什麼要這麼做那？讓我們帶著疑問一步步往下看。首先看下這幾個基本組成結構：
陣列：陣列儲存結構是連續的，空間複雜度大，但查詢的時間複雜度小。其定址（透過下標搜尋）效率高，一般的插入和刪除效率低。
連結串列：連結串列儲存結構是離散的，空間複雜度小。其定址（透過下標搜尋）效率低，一般的插入和刪除效率高。
紅黑樹：作為一種二叉查詢樹，但它在二叉查詢樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查詢、插入、刪除的時間複雜度最壞為O（log n）。由於連結串列的查詢時間複雜度為O（n），所以當連結串列很長時轉換成紅黑樹將很好的提高效率！
2
原始碼分析
2。1 常用
成員變數
連結串列的結構程式碼：
紅黑樹結構程式碼如下，紅黑樹的講解可以參考該部落格：https：//www。cnblogs。com/yyxt/p/4983967。html
2.2
常用
構造方法
以上有個tableSizeFor方法，為什麼總能返回2的指數倍，細節參考該部落格HashMap原始碼註解 之 靜態工具方法hash（）、tableSizeFor（）（四）：
https：//blog。csdn。net/fan2012huan/article/details/51097331
之所以保證要返回2的指數倍，是為了提高hash的效率。
2.3
常用方法
2.3.1
size：返回map的大小
public int size（） { return size；}
2.3.2
isEmpty：map是否為空
public boolean isEmpty（） { return size == 0； }
2.3.3
get(Object key)：返回指定鍵對應的值。
上面涉及到hash方法，它的實現方法是key的hash值高16位不變，透過低16位與高16位異或作為key的最終hash值，這樣簡單的異或可以在系統開銷不大的情況下，適當的減少碰撞。細節參考該部落格HashMap原始碼註解 之 靜態工具方法hash（）、tableSizeFor（）（四）：
https：//blog。csdn。net/fan2012huan/article/details/51097331
2.3.4
containsKey(Object key)：map中是否存在指定的鍵。
public boolean containsKey（Object key） { return getNode（hash（key）， key） ！= null； }
2.3.5
put(K key, V value)：將指定的鍵和值關聯,若原來存在相應的鍵值對，則將原來的值覆蓋。
以下的圖能形象的描述put邏輯的整個流程：
下面是
擴容機制
的程式碼，擴容的邏輯是第一次時容量設定為16，後面每次擴容為原來的2倍，直到最大容量。
3
總結
hashmap底層結構是由陣列+連結串列+紅黑樹組成，當連結串列長度大於8且容量大於最小樹化容量時將轉換成紅黑樹，這些使得hashmap能兼顧增刪改查的效能。
hashmap預設的容量為16，預設負載因數為0。75，當其容量大於擴容閾值（容量 * 負載因數）時，將進行擴容操作，每次擴充套件為原來的2倍，且必須保證為2的指數倍。
當發生hash碰撞時，hashmap採用的是鏈地址法，及在存在相同hash值的陣列位置存放連結串列。
hashmap不是執行緒安全的，可以使用Collections。synchronizedMap（）來封裝不安全的HashMap的方法，或者使用相應的併發容器類
ConcurrentHashMap
，它的效能更好。
