一、HashMap 簡介

HashMap 底層采用哈希表結構 數組加鏈表加紅黑樹實現，允許儲存null鍵和null值

數組優點：通過數組下標可以快速實現對數組元素的訪問，效率高

鏈表優點：插入或刪除數據不需要移動元素，只需要修改節點引用效率高

二、源碼分析2.1 繼承和實現

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L;

繼承AbstractMap<K,V>

實現了map接口 cloneable接口和可序列化接口

2.2 屬性

//hashmap默認容量為 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap默認容量 16//最大容量為2的30 1073741824static final int MAXIMUM_CAPACITY = 1 << 30; ////默認加載因子為0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;//鏈表轉為紅黑樹的閾值static final int TREEIFY_THRESHOLD = 8;//紅黑樹轉為鏈表的閾值static final int UNTREEIFY_THRESHOLD = 6;//鏈表轉為紅黑樹時數組容量必須大于64static final int MIN_TREEIFY_CAPACITY = 64;//transient Node<K,V>[] table;transient Set<Map.Entry<K,V>> entrySet;transient int size;//用于快速失敗機制 在對HashMap進行迭代時，如果期間其他線程的參與導致HashMap的結構發生變化了（比如put，remove等操作），直接拋出ConcurrentModificationException異常transient int modCount;//擴容閾值，計算方法為數組容量*填充因子int threshold;//加載因子 填充因子final float loadFactor;

loadFactor決定數組何時進行擴容，而且為什么是0.75f

它也叫擴容因子 比如數組長度為32，所以數組擴容閾值為32*0.75=24當數組中數據個數為24時數組進行擴容，

數組容量在創建的時候就確定，擴容時重新創建一個指定容量的數組，然后講舊數組的值復制到新數組中，擴容過程非常耗時，所以0.75時基于容量和性能之間平衡的結果。

如果加載因子過大，也就是擴容閾值會變大，擴容門檻高，這樣容量的占用率就會降低，但哈希碰撞的幾率就會增加，效率下降 如果加載因子過小，擴容閾值變小，擴容門檻低，容量占用變大但哈希碰撞幾率下降

此外用于存儲數據的table字段使用transient修飾，通過transient修飾的字段在序列化的時候將被排除在外，那么HashMap在序列化后進行反序列化時，是如何恢復數據的呢？HashMap通過自定義的readObject/writeObject方法自定義序列化和反序列化操作。這樣做主要是出于以下兩點考慮：

1.table一般不會存滿，即容量大于實際鍵值對個數，序列化table未使用的部分不僅浪費時間也浪費空間；

2.key對應的類型如果沒有重寫hashCode方法，那么它將調用Object的hashCode方法，該方法為native方法，在不同JVM下實現可能不同；換句話說，同一個鍵值對在不同的JVM環境下，在table中存儲的位置可能不同，那么在反序列化table操作時可能會出錯。

所以在HashXXX類中（如HashTable，HashSet，LinkedHashMap等等），我們可以看到，這些類用于存儲數據的字段都用transient修飾，并且都自定義了readObject/writeObject方法。readObject/writeObject方法

2.3 節點類型Node內部類

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next; } public final K getKey(){ return key; } public final V getValue() { return value; } public final String toString() { return key + '=' + value; } public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue; } public final boolean equals(Object o) {if (o == this) return true;if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false; }}

Node包含四個字段

final int hash; final K key; V value; Node<K,V> next;//包含鏈表下一個節點

HashMap通過hash方法計算key的哈希值，然后通過（n-1）&hash得到key在數組中存放的下標，當兩個key相同時，會以鏈地址法處理哈希碰撞

在鏈表中查找數據必須從第一個元素開始，時間復雜度為O n 所以當鏈表長度越來越長時HashMap的查詢效率就會越來越低

所以為了解決這個問題JDK1.8實現了數組+鏈表+紅黑樹來解決 當鏈表長度超過8個時并且數組長度大于64時進行樹化，轉化后查詢時間復雜度為O(logN).

2.4 紅黑樹的節點

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next); }

包含左右孩子節點和雙親結點，和前驅節點，還有節點是否時紅或者黑

三、構造方法3.1 構造器1

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

最常用的構造器。默認的填充因子 0.75f 這里的填充因子后面會講到。

3.2 構造器2

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}

給定容量構造器

3.3 構造器3

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)// 如果小于0，拋出異常throw new IllegalArgumentException('Illegal initial capacity: ' + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)//大于最大值initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor))//若填充因子小于0或者判斷非法throw new IllegalArgumentException('Illegal load factor: ' + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);} static final int tableSizeFor(int cap) {int n = cap - 1;　讓cap-1再賦值給n的目的是另找到的目標值大于或等于原值n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

給定容量和填充因子。

這里的tableSizeFor會將傳進的容量值進行**大于等于最近**二次冪處理。跟循環數組的處理方式差不多

3.4 構造器4

public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false);}四、put

public V put(K key, V value) { //底層是調用putval return putVal(hash(key), key, value, false, true);} //這里調用了hashmap提供的hash方法，32為都參與了運算所以降低了hash碰撞的幾率，這里還跟數組容量有關//下面再討論 static final int hash(Object key) {int h; //這里就可以看到hashmapreturn (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

通過hash函數可以看到當key為null時，key為0，所以HashMap 是允許儲存空值的。而后面的公式通過hashcode的高16位異或低1位得到的hash值，主要從性能、哈希碰撞角度考慮，減少系統開銷，不會因為高位沒有參與下標計算而引起的碰撞

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //請注意這里的hash是已經算過的hash(key)，然后計算數組下標位置(n - 1) & hash Node<K,V>[] tab; Node<K,V> p; int n, i; //首先判斷數組哈希表是否為null或者長度為0，是則進行數組初始化操作 if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; //這里tab指向table數組 n是數組長度 //如果該數組下標位置沒有數據直接插入 if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null); else {//該位置有元素 Node<K,V> e; K k;//首先判斷此位置的值的hash和key的地址和值是否相等//如果相等直接覆蓋//小問題這里為什么先判斷hash值而不是判斷key值，因為hash值判斷最快，如果hash值不同就不用判斷下面的//hash不同則key一定不同，但key相同hash值是可能相同的，效率提高if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//否則就是該位置可以不存在，如果該節點是紅黑樹類型，else if (p instanceof TreeNode) //則按照紅黑樹的插入 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else { //否則就為鏈表結構，遍歷鏈表，尾插 for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果鏈表長度大于等于轉為紅黑樹閾值8，則轉為紅黑樹 //這里為什么要-1，因為數組下標從0開始 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //轉為紅黑樹操作時，內部還會判斷數組長度是否小于MIN_TREEIFY_CAPACITY 64，如果是的話不轉換treeifyBin(tab, hash); break;//退出}//如果鏈表中已經存在該key，直接覆蓋if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;//遍歷數組 e = p.nextp = e; }}//e代表被覆蓋的值if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null)e.value = value; // 如果onlyIfAbsent為false并且oldValue為null,我們便對我們的value進行保存 afterNodeAccess(e); return oldValue;} } ++modCount; //如果鍵值對個數大于擴容閾值，進行擴容操作 if (++size > threshold)resize(); afterNodeInsertion(evict); return null;}

流程圖

五、get

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //如果桶為空，size為0，目標位置是否為空，是直接返回null if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//如果數組該下標位置就是要找的值，直接返回if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first;//否則如果頭節點的next有值if ((e = first.next) != null) { //如果該類型為紅黑樹，從紅黑樹中找 if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key); do {//否則遍歷鏈表if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null);} } return null;}六、resize

數組的擴容和初始化都要靠resize完成

final Node<K,V>[] resize() { //擴容前數組 Node<K,V>[] oldTab = table; //擴容前數組大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; //擴容前擴容閾值 int oldThr = threshold; //定義新數組和新閾值 int newCap, newThr = 0; //如果擴容前數組 if (oldCap > 0) {//如果超過最大值就不用再擴容if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab;}//2倍擴容不能大于最大值else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //擴容閾值/2 newThr = oldThr << 1; // double threshold } //數組中沒有值，帶參初始化會進入這里 //且擴容因子大于0 else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr; //不帶參默認會到這里 else {//否則擴充因子 <= 0//就是沒初始化過，使用默認的初始化容量，16 * 0.75newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果新容量為0，重新計算threshold擴容閾值 if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({'rawtypes','unchecked'}) //定義新數組進行擴容 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //這里采用高低映射的方式進行對新數組的映射 if (oldTab != null) {//遍歷舊數組復制到新數組中//遍歷for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) {oldTab[j] = null;//如果當前節點鏈表數據只有一個，則直接賦值if (e.next == null) newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode) //否則紅黑樹操作 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order //鏈表賦值 高低映射 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do {next = e.next;//判斷原索引和擴容后索引是否相同if ((e.hash & oldCap) == 0) { //相同則低位鏈表尾插 if (loTail == null)loHead = e; elseloTail.next = e; loTail = e;}else { //否則高位鏈表尾插 if (hiTail == null)hiHead = e; elsehiTail.next = e; hiTail = e;} } while ((e = next) != null); //如果低位映射不為空，斷低位尾部后的數據，因為尾巴后可能還會有數據，因為是個鏈表，所以采用頭尾引用來記錄有效值 //付給新數組 if (loTail != null) {loTail.next = null;newTab[j] = loHead; } //高位引用 直接講原索引+oldCap放到哈希桶中 //因為是2倍擴容，擴容后位置是原位置+增長的長度 if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead; }} }} } return newTab;}七、基于JDK1.7的優化7.1 底層實現

1.7基于數組+鏈表 而1.8基于鏈表+數組+紅黑樹

7.2 hash

final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}

效率基于1.8低

7.3 put

1.7使用的是數組加鏈表，解決哈希沖突采用的是鏈表，而且1.8采用的是尾插，而1.7采用頭插

7.4 擴容

1.7在擴容時會重新計算h每個元素的hash值，按舊鏈表的正序遍歷鏈表，然后在新鏈表的頭部插入，所以會出現逆序的情況，而1.8是通過高低位映射，不會出現逆序。

到此這篇關于Java源碼解析之HashMap的put、resize方法詳解的文章就介紹到這了,更多相關HashMap的put、resize方法內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！