主頁 > 後端開發 > 【JDK原始碼】HashMap原始碼分析（附常見面試題）

【JDK原始碼】HashMap原始碼分析（附常見面試題）

2022-01-03 08:21:06 後端開發

在這里插入圖片描述

HashMap原始碼分析（附面試題）

1.什么是哈希？

在分析HashMap之前，我們先來了解什么是哈希？

概念：Hash也稱散列、哈希，對應的英文都是Hash，基本原理就是把任意長度的輸入，通過Hash演算法變成固定長度的輸出這個映射的規則就是對應的Hash演算法，而原始資料映射后的二進制串就是哈希值，

Hash的特點:

  1. 從hash值不可以反向推導出原始的資料
  2. 輸入資料的微小變化會得到完全不同的hash值，相同的資料會得到相同的
  3. 哈希演算法的執行效率要高效，長的文本也能快速地計算出哈希值
  4. hash演算法的沖突概率要小

由于hash的原理是將輸入空間的值映射成hash空間內，而hash值的空間遠小于輸入的空間，根據抽屜原理，一定會存在不同的輸入被映射成相同輸出的情況，

抽屜原理：桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發現至少會有一個抽屜里面放不少于兩個蘋果，
這一現象就是我們所說的“抽屜原理”，

2.HashMap的繼承體系

HashMap采用key/value存盤結構，每個key對應唯一的value，查詢和修改的速度都很快，能達到O(1)的平均時間復雜度，它是非執行緒安全的，且不保證元素存盤的順序，

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-8rNFqNRP-1641090759949)(HashMap原始碼分析（附常見面試題）.assets/image-20211231093118109.png)]

從繼承體系可以看出：

  • HashMap 實作了Cloneable介面，可以被克隆，
  • HashMap 實作了Serializable介面，屬于標記性介面，HashMap 物件可以被序列化和反序列化，
  • HashMap 繼承了AbstractMap，父類提供了 Map 實作介面，具有Map的所有功能，以最大限度地減少實作此介面所需的作業，

3.底層存盤結構

  • 1.7 陣列 + 鏈表
  • 1.8 陣列 + （鏈表 | 紅黑樹）

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-TONIod9y-1641090759953)(HashMap原始碼分析（附常見面試題）.assets/image-20211128085755408.png)]

在Java中，HashMap的實作采用了（陣列 + 鏈表 + 紅黑樹）的復雜結構，陣列的一個元素又稱作桶，

在添加元素時，會根據hash值算出元素在陣列中的位置，如果該位置沒有元素，則直接把元素放置在此處，如果該位置有元素了，則把元素以鏈表的形式放置在鏈表的尾部，

當一個鏈表的元素個數達到一定的數量（且陣列的長度達到一定的長度）后，則把鏈表轉化為紅黑樹，從而提高效率，

陣列的查詢效率為O(1)，鏈表的查詢效率是O(k)，紅黑樹的查詢效率是O(log k)，k為桶中的元素個數，所以當元素數量非常多的時候，轉化為紅黑樹能極大地提高效率，

樹化需要同時滿足兩個條件：

  1. 鏈表長度大于8，并不是大于等于8
  2. 陣列長度達到64，如果陣列長度不夠64，會優先進行resize()擴容，

4.內部類

Node內部類

Node是HashMap的靜態內部類，實作了Map.Entry<K,V>介面，我們存盤的鍵值對都是以Node的形式存盤在map中的，其重要屬性如下：

static class Node<K,V> implements Map.Entry<K,V> {
    //基于key的hashValue經過hash擾動后得到的，是hash分布更均勻
    final int hash;
    //put進來的key
    final K key;
    //對應的value
    V value;
    //指向鏈表中的下一個Node
    Node<K,V> next;
    ...
}

5.HashMap核心屬性分析

  	/**
     * HashMap的初始化容量（必須是 2 的 n 次冪）默認的初始容量為16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * table最大長度
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默認的負載因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 樹化閾值：當一個桶中的元素個數大于8時進行樹化（同時需要陣列長度達到64）
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 樹降級為鏈表的閾值：當一個桶中的元素個數小于等于6時把樹轉化為鏈表
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    /**
     * Node陣列，又叫作桶（bucket）
     */
    transient Node<K,V>[] table;

    /**
     * 作為entrySet()的快取
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 當前哈希表中元素的個數
     */
    transient int size;

    /**
     * 當前哈希表結構修改次數
     */
    transient int modCount;

    /**
     * 擴容閾值，當你的哈希表中的元素超過閾值時，觸發擴容（threshold = capacity * loadFactor）
     */
    int threshold;

    /**
     * 負載因子（默認0.75）
     */
    final float loadFactor;

從屬性原始碼我們可以得到幾個資訊：

  1. 容量：容量為陣列的長度，亦即桶的個數，默認為16，最大為2的30次方，當容量達到64時才可以樹化，
  2. 裝載因子：用來計算容量達到多少時才進行擴容，默認裝載因子為0.75，
  3. 樹化：當容量達到64且鏈表的長度大于8時進行樹化，當鏈表的長度小于6時反樹化，

6.HashMap構造方法

HashMap()

構造一個空的HashMap，默認初始容量（16）和默認負載因子（0.75）

public HashMap() {
   // 將默認的負載因子0.75賦值給loadFactor，并沒有創建陣列
   this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

HashMap(int initialCapacity)

構造指定初始容量initialCapacity的HashMap，其實也是呼叫HashMap(int initialCapacity，float loadFactor)，默認的負載因子

/**
* 指定初始容量大小的建構式
* @param initialCapacity
*/
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

HashMap(int initialCapacity，float loadFactor)

構造一個具有指定的初始容量initialCapacity和負載因子loadFactor的 HashMap

/*
指定“容量大小”和“負載因子”的建構式
initialCapacity：指定的容量
loadFactor:指定的負載因子
*/
public HashMap(int initialCapacity, float loadFactor) {
    //判斷初始容量initialCapacity是否小于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //判斷初始容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //判斷負載因子loadFactor是否<=0或者是否是一個非數值
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    //將指定的負載因子loadFactor賦值給HashMap成員變數的負載因子
    this.loadFactor = loadFactor;
    //給擴容閾值賦值（只能是2的次方）
    this.threshold = tableSizeFor(initialCapacity);
}
	 /**
     * 作用：回傳比指定cap容量大的最小2的n次冪數
     * 栗子：cap=10
     * n=10-1=9
     * 0b1001 | 0b0100 = 0b1101
     * 0b1101 | 0b0011 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * ob1111->15
     * 15>0 -> return 15+1(16)
     * 模式：0001 1101 1100 => 0001 1111 1111 +1 => 0010 0000 0000
     */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    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;
}

7.put方法

put方法的整體流程：

  1. 計算key的hash值
  2. 如果桶（陣列）數量為0，則初始化桶
  3. 如果key所在的桶沒有元素，則直接插入
  4. 如果key所在的桶中的第一個元素的key與待插入的key相同，說明找到了元素，轉后續流程（9）處理
  5. 如果第一個元素是樹節點，則呼叫樹節點的putTreeVal()尋找元素或插入樹節點
  6. 如果不是以上三種情況，則遍歷桶對應的鏈表查找key是否存在于鏈表中
  7. 如果找到了對應key的元素，則轉后續流程（9）處理
  8. 如果沒找到對應key的元素，則在鏈表最后插入一個新節點并判斷是否需要樹化
  9. 如果找到了對應key的元素，則判斷是否需要替換舊值，并直接回傳舊值
  10. 如果插入了元素，則數量加1并判斷是否需要擴容
public V put(K key, V value) {
	 // 呼叫hash(key)計算出key的hash值
    return putVal(hash(key), key, value, false, true);
}

	/**
     * 作用：讓key的hash值的高16位參與運算
     * @param key
     * @return
     */
static final int hash(Object key) {
    int h;
    //key==null直接回傳0
    //1、否則呼叫key的hashCode()方法計算出key的哈希值然后賦值給h,
    //2、后與h無符號右移16位后的二進制進行按位異或得到最后的hash值,
    //3、這樣做是為了使計算出的hash更分散，讓高16位可以參與（低16位具有高16位的特征）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

	/**
     *
     * @param hash  key的hash值
     * @param key   原始key
     * @param value 要存放的值
     * @param onlyIfAbsent  如果 true 代表不更改現有的值，也就是說如果存在key就不改變，一般傳入false
     * @param evict  如果為false表示 table 為創建狀態
     * @return
     */
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;
    // 如果桶的數量為0，則初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 呼叫resize()初始化
        n = (tab = resize()).length;
    //最簡單的一種情況：尋址找到的桶位null，直接將創建一個新結點放入桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //e：不為null的話，找到一個與當前要插入的key-value一致的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)
            // 如果第一個元素是樹節點，則呼叫樹節點的putTreeVal插入元素
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
			// 遍歷這個桶對應的鏈表，binCount用于存盤鏈表中元素的個數
            for (int binCount = 0; ; ++binCount) {
                //條件成立的話，說明迭代到最后一個元素了，也沒找到一個與你插入的key一致的node
                //說明需要加入到當前鏈表的尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //條件成立的話，說明當前鏈表的長度達到樹化的標準了，需要進行樹化
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        //樹化操作
                        treeifyBin(tab, hash);
                    break;
                }
                //說明條件成立的化，找到了相同key的node元素，進行替換操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //e不等于null，說明找到了一個與你插入元素key完全一致的資料，需要進行替換
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 在節點被訪問后做點什么事，在LinkedHashMap中用到
            afterNodeAccess(e);
            // 回傳舊值
            return oldValue;
        }
    }
    //散串列結果修改次數加一，替換Node元素的value不計數
    ++modCount;
    //插入新元素，size自增
    //如果大于擴容閾值，擴容
    if (++size > threshold)
        resize();
    // 在節點插入后做點什么事，在LinkedHashMap中用到
    afterNodeInsertion(evict);
    // 沒找到元素回傳null
    return null;
}

8.resize擴容方法

整個擴容流程：

  1. 如果使用是默認構造方法，則第一次插入元素時初始化為默認值，容量為16，擴容門檻為12
  2. 如果使用的是非默認構造方法，則第一次插入元素時初始化容量等于擴容門檻，擴容門檻在構造方法里等于傳入容量向上最近的2的n次方
  3. 如果舊容量大于0，則新容量等于舊容量的2倍，但不超過最大容量2的30次方，新擴容門檻為舊擴容門檻的2倍
  4. 創建一個新容量的桶
  5. 搬移元素，原鏈表分化成兩個鏈表，低位鏈表存盤在原來桶的位置，高位鏈表搬移到原來桶的位置加舊容量的位置
/**
     * 為什么需要擴容？
     * 為了解決hash沖突導致的鏈化影響查詢效率的問題，擴容會緩解該問題
     *
     * @return
     */
final Node<K, V>[] resize() {
    //參考擴容前的哈希表
    Node<K, V>[] oldTab = table;
    //表示擴容之前的table陣列的長度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //擴容之前的擴容閾值
    int oldThr = threshold;
    //newCap：擴容之后table陣列的大小
    //newThr：擴容之后，下次在觸發擴容的條件
    int newCap, newThr = 0;
    //條件入如果成立：說明hashMap中的散串列已經初始化過了，是一次正常擴容
    if (oldCap > 0) {
        //如果舊容量達到最大容量，則不再進行擴容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果舊容量的兩倍小于最大容量并且舊容量大于默認初始容量（16），則容量擴大為兩部，擴容門檻也擴大為兩倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        //使用非默認構造方法創建的map，第一次插入元素會走到這里
        //1.new HashMap(initCap,loadFactor);
        //2.new HashMap(initCap);
        //3.new HashMap(map); map有資料
        // 如果舊容量為0且舊擴容門檻大于0，則把新容量賦值為舊門檻
        newCap = oldThr;
    else {
        //使用默認構造方法創建的map，第一次插入元素會走這里
        newCap = DEFAULT_INITIAL_CAPACITY;
        //如果舊容量舊擴容門檻都是0，說明還未初始化過，則初始化容量為默認容量，擴容門檻為默認容量*默認裝載因子
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
        //如果舊容量舊擴容門檻都是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節點
            Node<K, V> e;
            //如果當前桶中第一個元素不為空，說明當前桶位有資料，賦值給e
            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 {
                    //第三種情況：鏈表情況
                    // 比如，假如原來容量為4，3、7、11、15這四個元素都在三號桶中
                    // 現在擴容到8，則3和11還是在三號桶，7和15要搬移到七號桶中去
                    // 也就是分化成了兩個鏈表
                    //低位鏈表：存放在擴容之后下標位置與當前陣列下標位置一致
                    Node<K, V> loHead = null, loTail = null;
                    //高位鏈表：存放在擴容之后的陣列的下標位置=為當前陣列下標位置+擴容之前陣列的長度
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        // (e.hash & oldCap) == 0的元素放在低位鏈表中
                        //比如3&4==0
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else {
                            // (e.hash & oldCap) != 0的元素放在高位鏈表中
                            //比如，7&4！=0
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍歷完成分化成兩個鏈表了
                    // 低位鏈表在新桶中的位置與舊桶一樣（即3和11還在三號桶中）
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 高位鏈表在新桶中的位置正好是原來的位置加上舊容量（即7和15搬移到七號桶了）
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

9.get方法

public V get(Object key) {
    Node<K, V> e;
    //這里hash(key)是因為put的時候hash了，這里取自然也需要hash
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K, V> getNode(int hash, Object key) {
    //參考當前hashMap的散串列
    Node<K, V>[] tab;
    //first:桶位中的頭元素
    //e:臨時node元素
    Node<K, V> first, e;
    //n:table陣列長度
    int n;
    K k;
    // 如果桶的數量大于0并且待查找的key所在的桶的第一個元素不為空
    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;
        // 第一個元素不是要查找的元素，并且當前桶位不止一個元素，可能存在鏈表或者樹
        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;
}

get方法具體分這幾步：

  1. 計算key的hash值
  2. 找到key所在的桶及其第一個元素
  3. 如果第一個元素的key等于待查找的key，直接回傳
  4. 如果第一個元素是樹節點就按樹的方式來查找
  5. 否則就按鏈表方式查找

10.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) {
    //參考當前hashMap中的散串列
    Node<K, V>[] tab;
    //當前node元素
    Node<K, V> p;
    //n:表示散串列陣列長度
    //index:表示尋址結果
    int n, index;
    // 如果桶的數量大于0且待洗掉的元素所在的桶的第一個元素不為空
    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;
        // 如果第一個元素正好就是要找的元素，賦值給node變數后續洗掉使用
        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);
            }
        }
        // 如果找到了元素，則看引數是否需要匹配value值，如果不需要匹配直接洗掉，如果需要匹配則看value值是否與傳入的value相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                // 如果是樹節點，呼叫樹的洗掉方法（以node呼叫的，是洗掉自己）
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 如果待洗掉的元素是第一個元素，則把第二個元素移到第一的位置
                tab[index] = node.next;
            else
                // 否則洗掉node節點，將當前元素p的下一個元素設定為洗掉元素的下一個元素
                p.next = node.next;
            ++modCount;
            --size;
            // 洗掉節點后置處理
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

整個remove流程分為這幾步：

  1. 先查找元素所在的節點
  2. 如果找到的節點是樹節點，則按樹的移除節點處理
  3. 如果找到的節點是桶中的第一個節點，則把第二個節點移到第一的位置
  4. 否則按鏈表洗掉節點處理
  5. 修改size，呼叫移除節點后置處理等

11.總結

  1. HashMap是一種散串列，采用（陣列 + 鏈表 + 紅黑樹）的存盤結構
  2. HashMap的默認初始容量為16（1<<4），默認裝載因子為0.75f，容量總是2的n次方
  3. HashMap擴容時每次容量變為原來的兩倍
  4. 當桶的數量小于64時不會進行樹化，只會擴容
  5. 當桶的數量大于64且單個桶中元素的數量大于8時，進行樹化
  6. 當單個桶中元素數量小于6時，進行反樹化
  7. HashMap是非執行緒安全的容器
  8. HashMap查找添加元素的時間復雜度都為O(1)

HashMap在JDK1.7和1.8中不同

  • 1.7 陣列 + 鏈表
  • 1.8 陣列 + （鏈表 | 紅黑樹）

為啥要用紅黑樹？

紅黑樹用來避免 DoS 攻擊，防止鏈表超長時性能下降，樹化應當是偶然情況，是保底策略

為何不一上來就樹化？

  • hash 表的查找，更新的時間復雜度是 O ( 1 ) O(1) O(1)，而紅黑樹的查找，更新的時間復雜度是 O ( l o g 2 ? n ) O(log_2?n ) O(log2??n)
  • TreeNode 占用空間也比普通 Node 的大，如非必要，盡量還是使用鏈表

樹化閾值為何是8？

hash 值如果足夠隨機，則在 hash 表內按泊松分布，在負載因子 0.75 的情況下，長度超過 8 的鏈表出現概率是 0.00000006，樹化閾值選擇 8 就是為了讓樹化幾率足夠小

樹化規則

  • 當鏈表長度超過樹化閾值 8 時，先嘗試擴容來減少鏈表長度，如果陣列容量已經 >=64，才會進行樹化
  • 樹化的兩個條件：鏈表長度超過樹化閾值>8 && 陣列容量>=64

退化規則

  • 情況1：在擴容時如果拆分樹時，樹元素個數 <= 6 則會退化鏈表
  • 情況2：移除之前，remove 樹節點時，若 root、root.left、root.right、root.left.left 有一個為 null ，也會退化為鏈表

索引計算方法

  1. 首先，計算物件的 hashCode()
  2. 再進行呼叫 HashMap 的 hash() 方法進行二次哈希，二次 hash() 是為了綜合高位資料，讓哈希分布更為均勻
  3. 最后 & (capacity – 1) 得到索引

陣列容量為何是 2 的 n 次冪

  • 計算索引時效率更高：如果是 2 的 n 次冪可以使用位與運算代替取模
  • 擴容時重新計算索引效率更高： hash & oldCap == 0 的元素留在原來位置 ，否則新位置 = 舊位置 + oldCap

注意：

  • 二次 hash 是為了配合 容量是 2 的 n 次冪 這一設計前提，如果 hash 表的容量不是 2 的 n 次冪，則不必二次 hash
  • 容量是 2 的 n 次冪 這一設計計算索引效率更好，但 hash 的分散性就不好，需要二次 hash 來作為補償，沒有采用這一設計的典型例子是 Hashtable

put 流程

  1. HashMap 是懶惰創建陣列的，首次使用才創建陣列
  2. 計算索引（桶下標）
  3. 如果桶下標還沒人占用，創建 Node 占位回傳
  4. 如果桶下標已經有人占用
    • 已經是 TreeNode 走紅黑樹的添加或更新邏輯
    • 是普通 Node，走鏈表的添加或更新邏輯，如果鏈表長度超過樹化閾值，走樹化邏輯
  5. 回傳前檢查容量是否超過閾值，一旦超過進行擴容

put流程1.7中和1.8的區別

  1. 鏈表插入節點時，1.7 是頭插法，1.8 是尾插法
  2. 1.7 是大于等于閾值且沒有空位時才擴容，而 1.8 是大于閾值就擴容
  3. 1.8 在擴容計算 Node 索引時，會優化

擴容（加載）因子為何默認是 0.75f

  1. 在空間占用與查詢時間之間取得較好的權衡
  2. 大于這個值，空間節省了，但鏈表就會比較長影響性能
  3. 小于這個值，沖突減少了，但擴容就會更頻繁，空間占用也更多

key 的設計要求

  1. HashMap 的 key 可以為 null，但 Map 的其他實作則不然（Hashtable等）
  2. 作為 key 的物件，必須實作 hashCode 和 equals，并且 key 的內容不能修改（不可變）
  3. key 的 hashCode 應該有良好的散列性
  4. 如果 key 可變，例如修改了 age 會導致再次查詢時查詢不到

String 物件的 hashCode() 設計

  • 目標是達到較為均勻的散列效果，每個字串的 hashCode 足夠獨特
  • 字串中的每個字符都可以表現為一個數字，稱為 S i S_i Si?，其中 i 的范圍是 0 ~ n - 1
  • 散列公式為： S 0 ? 3 1 ( n ? 1 ) + S 1 ? 3 1 ( n ? 2 ) + … S i ? 3 1 ( n ? 1 ? i ) + … S ( n ? 1 ) ? 3 1 0 S_0?31^{(n-1)}+ S_1?31^{(n-2)}+ … S_i ? 31^{(n-1-i)}+ …S_{(n-1)}?31^0 S0??31(n?1)+S1??31(n?2)+…Si??31(n?1?i)+…S(n?1)??310
  • 31 代入公式有較好的散列特性，并且 31 * h 可以被優化為
    • 即 $32 ?h -h $
    • 即 2 5 ? h ? h 2^5 ?h -h 25?h?h
    • 即 h ? 5 ? h h?5 -h h?5?h

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/401629.html

標籤：java

上一篇：springMVC小結

下一篇：JAVA實作客戶資訊管理系統以及給大一寒假學生的建議

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態，例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1：當函式不可能拋出例外或不能接受拋出例外時，使用noexcept 理由 如果不打算拋出例外的話，程式就會認為無法處理這種錯誤，并且應當盡早終止，如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接：https://codeforces.com/problemset/problem/1400/E 來源：Codeforces 思路：給你一個陣列，現在你可以進行兩種操作，操作1：將一段沒有 0 的區間進行減一的操作，操作2：將 i 位置上的元素歸零。最終問：將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯，就附帶了一個自己的翻譯版本 思考 這一題，它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數，這里就不慢慢介紹了。但是，重讀題，我們突然發現反向質數都是 $7$ 位，而將它反過來后的數字卻是 $6$ 位數，這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記：C++中的 const 變數詳解，教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中，會分配記憶體（也就是說可以通過地址間接修改變數的值）。測驗代碼如下： 運行結果： 2、全域const變數存放在只讀資料段（不能通過地址修改，會發生寫入錯誤）， 默認為外部聯編，可以給其他源檔案使用（需要用extern關鍵字修飾） 運行結果： ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中，添加資源 2. 點擊新添加的資源，復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案，編輯，使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索，點擊查找全部，然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h，在其中預先定義好宏 ID（不清楚其實ID值應該設定多少，可以先新建一個相同的資源項，再在這個資源的ID值的基礎上遞增即可） 2. 在資源視圖中選中專案資源，按F7編輯資源檔案，按 ID 型別 相對路徑的形式添加 資源。（別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記：關于C++的參考型別，專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考，也叫別名。 參考就是給一個變數名取一個變數名，方便我們間接地使用這個變數。我們可以給一個變數創建N個參考，這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間，占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名，但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++：初學者完整指南

    眾所周知，C ++的學習曲線陡峭，但是花時間學習這種語言將為您的職業帶來奇跡，并使您與其他開發人員區分開。您會更輕松地學習新語言，形成真正的解決問題的技能，并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣（即清晰一致的編碼風格，在撰寫代碼時注釋代碼，并限制類內部的可見性），并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • Rust中的智能指標:Box<T> Rc<T> Arc<T> Cell<T> RefCell<T> Weak

    Rust中的智能指標是什么 智能指標（smart pointers）是一類資料結構，是擁有資料所有權和額外功能的指標。是指標的進一步發展 指標（pointer）是一個包含記憶體地址的變數的通用概念。這個地址參考，或 ” 指向”（points at）一些其 他資料 。參考以 & 符號為標志并借用了他們所 ......

    uj5u.com 2023-04-20 07:24:10 more
  • Java的值傳遞和參考傳遞

    值傳遞不會改變本身，參考傳遞（如果傳遞的值需要實體化到堆里）如果發生修改了會改變本身。 1.基本資料型別都是值傳遞 package com.example.basic; public class Test { public static void main(String[] args) { int ......

    uj5u.com 2023-04-20 07:24:04 more
  • [2]SpinalHDL教程——Scala簡單入門

    第一個 Scala 程式 shell里面輸入 $ scala scala> 1 + 1 res0: Int = 2 scala> println("Hello World!") Hello World! 檔案形式 object HelloWorld { /* 這是我的第一個 Scala 程式 * 以 ......

    uj5u.com 2023-04-20 07:23:58 more
  • 理解函式指標和回呼函式

    理解 函式指標 指向函式的指標。比如： 理解函式指標的偽代碼 void (*p)(int type, char *data); // 定義一個函式指標p void func(int type, char *data); // 宣告一個函式func p = func; // 將指標p指向函式func ......

    uj5u.com 2023-04-20 07:23:52 more
  • Django筆記二十五之資料庫函式之日期函式

    本文首發于公眾號：Hunter后端 原文鏈接：Django筆記二十五之資料庫函式之日期函式 日期函式主要介紹兩個大類，Extract() 和 Trunc() Extract() 函式作用是提取日期，比如我們可以提取一個日期欄位的年份，月份，日等資料 Trunc() 的作用則是截取，比如 2022-0 ......

    uj5u.com 2023-04-20 07:23:45 more
  • 一天吃透JVM面試八股文

    什么是JVM？ JVM，全稱Java Virtual Machine（Java虛擬機），是通過在實際的計算機上仿真模擬各種計算機功能來實作的。由一套位元組碼指令集、一組暫存器、一個堆疊、一個垃圾回收堆和一個存盤方法域等組成。JVM屏蔽了與作業系統平臺相關的資訊，使得Java程式只需要生成在Java虛擬機 ......

    uj5u.com 2023-04-20 07:23:31 more
  • 使用Java接入小程式訂閱訊息！

    更新完微信服務號的模板訊息之后，我又趕緊把微信小程式的訂閱訊息給實作了！之前我一直以為微信小程式也是要企業才能申請，沒想到小程式個人就能申請。 訊息推送平臺🔥推送下發【郵件】【短信】【微信服務號】【微信小程式】【企業微信】【釘釘】等訊息型別。 https://gitee.com/zhongfuch ......

    uj5u.com 2023-04-20 07:22:59 more
  • java -- 緩沖流、轉換流、序列化流

    緩沖流 緩沖流, 也叫高效流, 按照資料型別分類： 位元組緩沖流：BufferedInputStream，BufferedOutputStream 字符緩沖流：BufferedReader，BufferedWriter 緩沖流的基本原理，是在創建流物件時，會創建一個內置的默認大小的緩沖區陣列，通過緩沖 ......

    uj5u.com 2023-04-20 07:22:49 more
  • Java-SpringBoot-Range請求頭設定實作視頻分段傳輸

    老實說，人太懶了，現在基本都不喜歡寫筆記了，但是網上有關Range請求頭的文章都太水了 下面是抄的一段StackOverflow的代碼...自己大修改過的，寫的注釋挺全的，應該直接看得懂，就不解釋了 寫的不好...只是希望能給視頻網站開發的新手一點點幫助吧. 業務場景：視頻分段傳輸、視頻多段傳輸（理 ......

    uj5u.com 2023-04-20 07:22:42 more
  • Windows 10開發教程_編程入門自學教程_菜鳥教程-免費教程分享

    教程簡介 Windows 10開發入門教程 - 從簡單的步驟了解Windows 10開發，從基本到高級概念，包括簡介，UWP，第一個應用程式，商店，XAML控制元件，資料系結，XAML性能，自適應設計，自適應UI，自適應代碼，檔案管理，SQLite資料庫，應用程式到應用程式通信，應用程式本地化，應用程式 ......

    uj5u.com 2023-04-20 07:22:35 more

Copyright © 2010-2020 有解無憂