1. 首頁 > 生活百科 > >

HashMap底層原理及jdk1.8源碼解讀

生活百科

一、前言寫在前面：小編碼字收集資料花了一天的時間整理出來，對你有幫助一鍵三連走一波哈，謝謝啦?。?
HashMap在我們日常開發中可謂經常遇到，HashMap 源碼和底層原理在現在面試中是必問的 。所以我們要掌握一下，也是作為兩年開發經驗必備的知識點！HashMap基于Map接口實現，元素以<Key,Value>的方式存儲 ， 并且允許使用null 鍵和null值，因為key不允許重復，因此只能有一個鍵為null，另外HashMap是無序的、線程不安全的 。
HashMap繼承類圖快捷鍵Ctrl+alt+U

HashMap底層原理及jdk1.8源碼解讀

文章插圖
二、存儲結構介紹
Jdk7.0之前 數組 + 鏈表Jdk8.0開始 數組 + 鏈表 + 二叉樹鏈表內元素個數>8個 由鏈表轉成二叉樹鏈表內元素個數<6個 由二叉樹轉成鏈表紅黑樹，是一個自平衡的二叉搜索樹，因此可以使查詢的時間復雜度降為O(logn)鏈表的長度特別長的時候 ， 查詢效率將直線下降，查詢的時間復雜度為 O(n)Jdk1.7中鏈表新元素添加到鏈表的頭結點，先加到鏈表的頭節點，再移到數組下標位置 。簡稱頭插法（并發時可能出現死循環）Jdk1.8中鏈表新元素添加到鏈表的尾結點 。簡稱尾插法（解決了頭插法死循環）
底層結構實例圖
HashMap底層原理及jdk1.8源碼解讀

文章插圖
三、源碼分析之常用變量解讀/** * 默認初始容量 - 必須是 2 的冪 。*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** * 最大容量，如果一個更高的值被任何一個帶參數的構造函數隱式指定使用 。必須是 2 <= 1<<30 的冪 。* 簡單理解為：最大容量2的30次冪，如果帶容量也會轉化為2的次冪 */static final int MAXIMUM_CAPACITY = 1 << 30;/** * 構造函數中未指定時使用的負載因子 。經過官方測試測出減少hash碰撞的最佳值 */static final float DEFAULT_LOAD_FACTOR = 0.75f;/** * 使用紅黑樹的計數閾值，超過8則轉化為紅黑樹 */static final int TREEIFY_THRESHOLD = 8;/** * 使用紅黑樹的計數閾值，低于6則轉化為鏈表 */static final int UNTREEIFY_THRESHOLD = 6;/** * 鏈表轉化為紅黑樹 ， 除了有閾值的限制，還有另外一個限制，需要數組容量至少達到64 ， 才會轉化為紅黑樹 。* 這是為了避免，數組擴容和樹化閾值之間的沖突 。*/static final int MIN_TREEIFY_CAPACITY = 64;/** * 在首次使用時初始化，并根據需要調整大小 。分配時 ， 長度始終是 2 的冪 。* （我們還在某些操作中允許長度為零，以允許當前不需要的引導機制） */transient Node<K,V>[] table;/** * 保存緩存的 entrySet() ， 也就是存放的鍵值對 */transient Set<Map.Entry<K,V>> entrySet;/** * 此映射中包含的鍵值映射的數量，就是數組的大小 */transient int size;/** * 記錄集合的結構變化和操作次數（例如remove一次進行modCount++） 。* 該字段用于使 HashMap 的 Collection-views 上的迭代器快速失敗 。如果失敗也就是我們常見的CME * （ConcurrentModificationException）異常 */transient int modCount;/** * 數組擴容的大小 * 計算方法 capacity * load factor容量 * 加載因子 * @serial */int threshold;/** * 哈希表的負載因子 。* @serial */final float loadFactor;四、源碼分析之構造方法解讀/** * 構造一個具有指定初始容量和負載因子的構造方法 * 不建議使用這個構造方法，加載因子經過官方測試是效率最好的 ， 所以為了效率應該保持默認 */public HashMap(int initialCapacity, float loadFactor) { // 參數為負數會拋出IllegalArgumentException異常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 傳的值超過最大值則使用默認最大值if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// 哈希表的負載因子 。this.loadFactor = loadFactor;// 初始化的參數默認如果不是2的次冪，直接給你轉化為2的次冪// 傳的參數為11，會自動轉化為比參數大的最近的2的次冪的值，也就是16 。// 我們后面會詳細說這個方法怎么進行轉化的this.threshold = tableSizeFor(initialCapacity);}/** * 構造一個只有指定初始容量的方法 */public HashMap(int initialCapacity) {// 我們會發現還是調用上面兩個參數的構造方法，自動幫我們設置了加載因子this(initialCapacity, DEFAULT_LOAD_FACTOR);}/** * 構造一個具有默認初始容量(16) 和默認負載因子(0.75)的構造方法 */public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}/** * 指定map集合，轉化為HashMap的構造方法 */public HashMap(Map<? extends K, ? extends V> m) { // 使用默認加載因子this.loadFactor = DEFAULT_LOAD_FACTOR; //調用PutMapEntries()來完成HashMap的初始化賦值過程putMapEntries(m, false);}/** * 將傳入的子Map中的全部元素逐個添加到HashMap中 */final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { // 獲得參數Map的大?。?并賦值給sint s = m.size();// 判斷大小是否大于0if (s > 0) {// 證明有元素來插入HashMap// 判斷table是否已經初始化如果table=null一般就是構造函數來調用的putMapEntries，或者構造后還沒放過任何元素if (table == null) { // pre-size// 如果未初始化 ， 則計算HashMap的最小需要的容量（即容量剛好不大于擴容閾值） 。這里Map的大小s就被當作HashMap的擴容閾值，然后用傳入Map的大小除以負載因子就能得到對應的HashMap的容量大?。ǖ鼻癿的大小 / 負載因子 = HashMap容量）// ((float)s / loadFactor)但這樣會算出小數來 ， 但作為容量就必須向上取整，所以這里要加1 。此時ft可以臨時看作HashMap容量大小float ft = ((float)s / loadFactor) + 1.0F;// 判斷ft是否超過最大容量大小 ， 小于則用ft，大于則取最大容量int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 暫時存放到擴容閾值上,tableSizeFor會把t重新計算到2的次冪給擴容數組大小if (t > threshold)threshold = tableSizeFor(t);}// 如果當前Map已經初始化,且這個map中的元素個數大于擴容的閥值就得擴容// 這種情況屬于預先擴大容量，再put元素else if (s > threshold)// 后面展開說resize();// 遍歷map,將map中的key和value都添加到HashMap中for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = https://www.huyubaike.com/biancheng/e.getValue();// 調用HashMap的put方法的具體實現方法putVal來對數據進行存放 。該方法的具體細節在后面會進行講解// putVal可能也會觸發resizeputVal(hash(key), key, value, false, evict);}}}

推薦閱讀