HashMap底層原理剖析(超詳細！！！)

一、散串列結構

散串列結構就是陣列+鏈表的結構

二、什么是哈希？

Hash也稱散列、哈希，對應的英文單詞Hash，基本原理就是把任意長度的輸入，通過Hash演算法變成固定長度的輸出

這個映射的規則就是對應的哈希演算法，而原始資料映射后的二進制就是哈希值

不同的資料它對應的哈希碼值是不一樣的

哈希演算法的效率非常高

三、HashMap原理講解

3.1繼承體系圖

3.2Node資料結構分析

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;計算得到哈希值
    final K key;
    V value;
    Node<K,V> next;
}

interface Entry<K, V> {
        K getKey();
        V getValue();
        V setValue(V value);

3.3底層存盤結構

當鏈表長度到達8時，升級成紅黑樹結構

3.4put資料原理分析

首先put進去一個key----value
根據key值會計算出一個hash值
經過擾動使資料更散列
構造出一個node物件
最后在通過路由演算法得出一個對應的index

3.5什么是哈希碰撞？

當傳入的資料key對應計算出的hash值的后四位和上一個一樣時，這時候計算出的index就會一致，就會發生碰撞，導致資料變成鏈表
例如:
(16-1)------->0000 0000 0000 1111
“張三”------->0100 1101 0001 1011
“李四”-------->1011 1010 0010 1011

此時，就會發現，張三和李四計算出的hash值轉化為二進制的后四位一致，導致計算出index一致

3.6JDK8為什么引入紅黑樹？

哈希碰撞，會帶來鏈化，效率會變低

引入紅黑樹會提高查找效率

3.7擴容機制

每次擴容為初始容量的2倍

eg：16------->32

為了防止資料過多，導致線性查詢，效率變低，擴容使得桶數變多，每條鏈上資料變少，查詢更快

四、手撕原始碼

1.HashMap核心屬性分析

樹化閾值-----8和64

負載因子0.75

threshold擴容閾值，當哈希表中的元素超過閾值時，觸發擴容

loadFactory負載因子0.75，去計算閾值 eg：16*0.75

size-------當前哈希表中元素個數

modCount--------當前哈希表結構修改次數

2.構造方法分析

public HashMap(int initialCapacity, float loadFactor) {
    //校驗 小于0報錯
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //capacity大于最大值取最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //負載因子不能小于等于0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //tableSizeFor方法
    this.threshold = tableSizeFor(initialCapacity);
}

---------------------------------------------------------
//傳入一個初始容量，默認負載因子0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
---------------------------------------------------------
//無引數，負載因子默認0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
---------------------------------------------------------
//傳入一個map的物件
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

3.put方法分析

public V put(K key, V value) {
    //回傳putVal方法，給key進行了一次rehash
    return putVal(hash(key), key, value, false, true);
}
----------------------------------------------------------
static final int hash(Object key) {
    //讓key對應的hash值的高16位也參與運算
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
----------------------------------------------------------
final V putVal(int hash, K key, V value, boolean  onlyIfAbsent,boolean evict) 
{
    //tab：參考當前HashMap的散串列
    //p：表示當前散串列的元素
    //n：表示散串列陣列的長度
    //i：表示路由尋址的結果
    Node<K,V>[] tab; Node<K,V> p; int n, i;
----------------------------------------------------------   	//延遲初始化邏輯，當第一次呼叫putVal的時候，才去初始化HashMap物件的散串列大小
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
----------------------------------------------------------
    //尋找找到桶位，且剛好為null，則把k-v封裝成node物件放進去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
----------------------------------------------------------
    else {
      //e：不為null時，找到一個與當前要插入的key-val一致的key物件
      //k：臨時的一個key
        Node<K,V> e; K k;
        //表示桶位中的該元素，與你當前插入的元素key一致，后續會有替換操作
        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 {
            //鏈表的情況，而且鏈表的頭元素與我們要插入的key不一致
            for (int binCount = 0; ; ++binCount) {
                
                //條件成立，即說明迭代到最后一個鏈表了，也沒找到與你要插入的key一致的node物件
                //說明要加入到鏈表的最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //說明當前鏈表長度達到樹化標準
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //說明找到的元素key一樣，進行替換，break跳出回圈即可
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
----------------------------------------------------------
    //e不等于null，說明找到了一個與你插入元素完全一致的，進行替換 
    if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
----------------------------------------------------------
    //modCount：表示散串列結構被修改次數，替換元素不算次數
    ++modCount;
    //插入新元素，size自增，如果自增大于擴容閾值，則觸發擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

4.resize()方法分析

//為了解決哈希沖突，影響哈希效率，所以會有擴容機制
----------------------------------------------------------
final Node<K,V>[] resize() {
    //oldTab：參考擴容前的哈希表
    //oldCap：表示擴容前table的陣列長度
    //oldThr：表示擴容之前閾值
    //newCap，newThr：擴容后的陣列長度大小，以及擴容后下次的閾值
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
----------------------------------------------------------
    //條件成立，說明hashmap散串列已經初始化過了，這是一次正常擴容
    if (oldCap > 0) {
        //擴容之前的table陣列大小，已經達到了最大閾值后，則不擴容
        //且設定擴容條件為int最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
----------------------------------------------------------
    //oldCAP左移一位，實作數值翻倍，且賦值給newcap，newcap小于數值最大值限制 且擴容之前閾值>=16
    //這種情況下，則下一次擴容閾值等于當前閾值翻倍
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
----------------------------------------------------------    //oldCap == 0，說明hashmap散串列為null
   //1.new HashMap(inttCap，loadFactor);
   //2.new HashMap(inttCap);
   //3.new HashMap(map); map有資料
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;//一定是2的次方數
----------------------------------------------------------
    //oldCap==0，oldThr==0
    //new HashMap();
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
----------------------------------------------------------
    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;
    //說明，hashmap本次擴容之前，table不為null
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;//當前node節點
            //說明當前桶位中有資料，但是具體是鏈表還是紅黑樹，還是單個資料，不確定
            if ((e = oldTab[j]) != null) {
                //方便jvm GC時回收
                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;
                        //hash--……1 1111
                        //hash--……0 1111
                        //0b 10000
                        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;
                    }
                    //
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

5.get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(key)) == null ? null : e.value;
}
----------------------------------------------------------
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; //tab：參考當前hashmap的散串列
    Node<K,V> first, e;//first：桶位中的頭元素，e：臨時node元素
    int n, hash; //n：table陣列長度
    K k;
 ---------------------------------------------------------
     if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
         //定位出來的桶位元素，就是我們要get的元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
----------------------------------------------------------         //說明當前桶位不止一個元素，可能是樹或者鏈表
        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;
}

6.remove方法分析

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
----------------------------------------------------------
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
    //tab：參考當前HashMap的散串列
    //p：表示當前散串列的元素
    //n：表示散串列陣列的長度
    //index：表示路由尋址的結果
        Node<K,V>[] tab; Node<K,V> p; int n, index;
---------------------------------------------------------- 
        if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {
  //說明路由的桶位是有資料的，需要進行查找操作，且洗掉  
----------------------------------------------------------   //node:查找到的結果， e：當前node的下一個元素
            Node<K,V> node = null, e; K k; V v;
            //當前桶位中的元素即為要洗掉的元素
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
----------------------------------------------------------   			//當前桶位的元素為紅黑樹         
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
          node=((TreeNode<K,V>)p).getTreeNode(hash, key);
----------------------------------------------------------             //當前桶位為鏈表   
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
----------------------------------------------------------    //判斷node不為空的情況，說明按照key找到了要洗掉的資料        
            if (node != null && (!matchValue || (v = node.value) == value ||(value != null&&value.equals(v)))) {
            //結果是紅黑樹
            if (node instanceof TreeNode)               ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //結果為單個元素    
            else if (node == p)
               tab[index] = node.next;
           //結果為鏈表     
            else
               p.next = node.next;
                ++modCount;//修改次數自增
                --size;//長度減少
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }  

7.replace方法分析

@Override
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if ((e = getNode(key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}
----------------------------------------------------------
@Override
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}
ll && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}
----------------------------------------------------------
@Override
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}