Java源碼解析之HashMap的put、resize方法詳解

Posted on by

一、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默認容量為 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap默認容量 16
//最大容量為2的30   1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;  //
//默認加載因子為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表轉為紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
//鏈表轉為紅黑樹時數組容量必須大於64
static 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;
      //這裡就可以看到hashmap
        return (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.next
                p = 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;
}

流程圖

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-HHFhKMDq-1618929232359)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20210420203344879.png)]

五、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 threshold
        newCap = oldThr;
    //不帶參默認會到這裡
    else {//否則擴充因子 <= 0
        //就是沒初始化過，使用默認的初始化容量，16 * 0.75
        newCap = 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;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            //否則高位鏈表尾插
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.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方法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

    None Found