HashMap (JDK1.8) 分析

来源:https://www.cnblogs.com/l-y-h/archive/2020/01/18/12210482.html
-Advertisement-
Play Games

一、HashMap(JDK1.8) 1、基本知識、數據結構 （1）時間複雜度：用來衡量演算法的運行時間。 參考：https://blog.csdn.net/qq_41523096/article/details/82142747 （2）數組：採用一段連續的存儲空間來存儲數據。查找方便，增刪麻煩。 （3 ...


一、HashMap(JDK1.8)

1、基本知識、數據結構

（1）時間複雜度：用來衡量演算法的運行時間。
　　參考：https://blog.csdn.net/qq_41523096/article/details/82142747

（2）數組：採用一段連續的存儲空間來存儲數據。查找方便，增刪麻煩。

（3）鏈表：採用一段不連續的存儲空間存儲數據，每個數據中都存有指向下一條數據的指針。即 n 個節點離散分配，彼此通過指針相連，每個節點只有一個前驅節點，每個節點只有一個後續節點。增刪方便，查找麻煩，

（4）紅黑樹：一種自平衡的二叉查找樹，時間複雜度 O(log n)。

（5）散列表、哈希表：結合數組 與 鏈表的優點。通過 散列函數 計算 key，並將其映射到 散列表的 某個位置（連續的存儲空間）。對於相同的 hash 值（產生 hash 衝突），通常採用 拉鏈法來解決。簡單地講，就是將 hash(key) 得到的結果 作為 數組的下標，若多個key 的 hash(key) 相同，那麼在當前數組下標的位置建立一個鏈表來保存數據。

（6）HashMap：基於 哈希表的 Map 介面的非同步實現（即線程不安全），提供所有可選的映射操作。底層採用 數組 + 鏈表 + 紅黑樹的形式，允許 null 的 Key 以及 null 的 Value。不保證映射的順序且不保證順序恆久不變。

2、HashMap JDK1.8 底層數據結構

（1）採用 數組 + 鏈表的形式。
　　HashMap 採用 Node 數組來存儲 key-value 鍵值對，且數組中的每個 Node 實際上是一個單向的鏈表，內部存儲下一個 Node 實體的指針。

 

 

transient Node<K,V>[] table;

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;
    }
}

 

（2）當前數組長度大於某個閾值（預設為 64），且鏈表長度大於某個閾值（預設為 8）時，鏈表會轉為 紅黑樹。

 

 

 

二、HashMap JDK1.8 源碼分析

1、基本常量、成員變數

/**
* 初始數組容量，必須為 2 的整數次冪。預設為 2^4 = 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
* 最大數組容量, 預設為 2^30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 負載因數，預設為 0.75。
* 用於計算 HashMap 容量。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 樹化的第一個條件：
* 鏈表轉紅黑樹的閾值，預設為 8。
* 即鏈表長度大於等於 8 時，當前鏈表會轉為紅黑樹進行存儲。
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 紅黑樹轉鏈表的閾值，預設為 6。
* 即紅黑樹節點小於等於 6 時，當前紅黑樹會轉為鏈表進行存儲。
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 樹化的第二個條件：
* 樹化最小容量，預設為 64。
* 當前數組長度大於等於 64 時，才可以進行 鏈表轉紅黑樹。
*/
static final int MIN_TREEIFY_CAPACITY = 64

/**
* 數組，用於存儲 Node<K, V> 鏈表
*/
transient Node<K,V>[] table;

/**
* 用於存儲 Node<K, V> 的總個數
*/
transient int size;

/**
* 數組長度閾值，當超過該值後，會調整數組的長度。一般通過 capacity * load factor 計算
*/
int threshold;

/**
* 負載因數，用於計算閾值，預設為 0.75
*/
final float loadFactor;

/**
* 用於快速失敗（fail-fast）機制，當對象結構被修改後會改變。
*/
transient int modCount;

 

2、核心構造方法

（1）源碼：

/**
* 常用無參構造方法，以預設值構造 HashMap。
*/
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


/**
 * HashMap 核心構造方法，根據 初始化容量 以及 負載因數創建 HashMap.
 * @param  initialCapacity 初始化容量
 * @param  loadFactor      負載因數
 * @throws IllegalArgumentException 非法數據異常
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 如果初始化容量 小於 0 ，則會拋出 非法數據 異常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    
    // 如果初始化容量 大於 最大容量值，則給其賦值為最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
        
    // 若負載因數小於 0 或者 不合法， 拋出 非法數據異常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    
    // 若上述條件均成立，則保存 負載因數的值
    this.loadFactor = loadFactor;
    
    // 若上述條件均成立，則保存 數組長度的閾值（2的整數次冪）。
    this.threshold = tableSizeFor(initialCapacity);
}

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;
}

 

（2）分析：
　　上例的構造函數，根據 初始化容量以及 負載因數去創建 HashMap，沒有去 實例化 Node 數組，數組的實例化 需要在 put 方法里實現。
　　數組長度閾值 通過 tableSizeFor() 方法實現，能返回一個比給定容量大的 且 最小的 2 的次冪的數。比如 initialCapacity = 21， tableSizeFor() 返回的結果為 32。

3、hash(key)

　　用於計算 key 的 hash 值。
（1）源碼：

/**
* 計算 key 的 hash 值的方法
*/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// Node 數組
transient Node<K,V>[] table;

// 獲取某個 key 所在位置時，通過 (table.length - 1) & hash(key) 去計算數組下標
table[(table.length - 1) & hash(key)]

 

（2）分析
　　採用 高 16 位 與 低 16 位 異或，然後再進行移位運算。主要是為了減少衝突。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(length - 1) & hash(key)

【舉例：】
    假設某個值經過 hashCode 計算後為：
        1111 0101 1010 0101 1101 1110 0000 0000
    數組長度為 16，那麼 length -1 = 15，如下：
        0000 0000 0000 0000 0000 0000 0000 1111
    此時進行 (length - 1) & hash(key) 操作後，
        1111 0101 1010 0101 1101 1110 0000 0000
        &
        0000 0000 0000 0000 0000 0000 0000 1111
        =
        0000 0000 0000 0000 0000 0000 0000 0000
    即只要 hashCode 計算出的值最後四位為0，得到的結果就一定為 0，此時衝突會大大提高。
    
    採用 高16位 與 低16位 異或，計算為：
        1111 0101 1010 0101 1101 1110 0000 0000
        ^
        0000 0000 0000 0000 1111 0101 1010 0101
        =
        1111 0101 1010 0101 0010 1011 1010 0101
     此時進行 (length - 1) & hash(key) 操作後，
         1111 0101 1010 0101 0010 1011 1010 0101
         &
         0000 0000 0000 0000 0000 0000 0000 1111
         =
         0000 0000 0000 0000 0000 0000 0000 0101
     此時計算出來的，是hashcode結果的後幾位的值，這樣就可以減少衝突的發生。

 

4、put、putVal

方法作用：
　　Step1： 給 HashMap 的數組 初始化。
　　Step2： 定義 鏈表 轉為 紅黑樹的條件。
　　Step3： 定義數據存儲的動作（存儲的方式：鏈表還是紅黑樹）。

（1）分析 put 過程
　　Step1：put 內部調用 putVal() 方法。
　　Step2：先判斷 數組是否為 null 或者 長度為0，是的話，則調用 resize 方法給數組擴容。
　　Step3：對 key 進行 hash 並執行位運算（(length - 1) & hash(key)），得到數組下標。若不衝突，即當前數組位置不存在元素，直接在此處添加一個節點即可。
　　Step4：若衝突，即當前數組位置存在元素，則根據節點的情況進行判斷。
　　　　如果 恰好是第一個 元素，則進行替換 value 的操作。
　　　　如果不是第一個元素，則判斷是否為 紅黑樹結構，是則添加一個樹節點。
　　　　如果不是紅黑樹結構（即鏈表），則採用尾插法給鏈表插入一個節點，鏈表長度大於等於 8 時，將鏈表轉為紅黑樹結構。
　　Step5：若 Node 長度大於閾值，還得重新 resize 擴容。

（2）源碼：

// Node 數組
transient Node<K,V>[] table;

// 插入數據的操作
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
* 真正的插入數據的方法。
* @param key 的 hash 值
* @param key
* @param value
* @param onlyIfAbsent為 true，插入數據若存在值時，不會進行修改操作
* @param evict if false, the table is in creation mode.
* @return 上一個值，若不存在，則返回 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 如果 Node 數組為 null 或者 長度為 0 時，即 Node 數組不存在，則調用 resize() 方法，重新獲取一個調整大小後的 Node 數組。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // 如果當前數組元素沒有值，即不存在 哈希衝突的情況，直接添加一個 Node 進去（多線程時，此處可能導致線程不安全）。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 存在哈希衝突的情況下，需要找到 插入或修改 的節點的位置，然後再操作（插入或修改）
        Node<K,V> e; K k;
        
        // Step1:找到節點的位置1
        // 判斷第一個節點 是不是我們需要找的，判斷條件： hash 是否相等、 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 {
            // 是鏈表節點，遍歷查找節點
            for (int binCount = 0; ; ++binCount) {
                // 第一個條件判斷得知 第一個節點不是我們要的，所以可以直接從第二個節點開始（p.next），然後遍歷得第三、四個節點。
                if ((e = p.next) == null) {
                    // 如果第二（三、四。。。）個節點沒有值，直接添加一個 Node 即可，此時的 e 為 null。
                    p.next = newNode(hash, key, value, null);
                    
                    // 如果鏈表長度大於等於 8，則轉為紅黑樹 ，並結束遍歷操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    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;
            // 此處是 空實現，LinkedHashMap使用
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // 添加節點的後續操作
    // 修改次數加1
    ++modCount;
    
    // 當Node節點數 size 大於 閾值時，需要執行 resize 方法調整數組長度。
    if (++size > threshold)
        resize();
    // 此處是 空實現，LinkedHashMap使用
    afterNodeInsertion(evict);
    
    // 添加節點成功，返回 null
    return null;
}

 

5、resize

　　用於給數組擴容。
（1）resize 過程
　　Step1：計算新數組的閾值、新數組的長度。
　　Step2：給新數組複製。對於鏈表節點採用 e.hash & oldCap 去確定元素的位置，新位置只有兩種可能（在原位置、或者在原位置的基礎上增加 舊數組長度）

【舉例：】
    e.hash = 10 = 0000 1010,     oldCap = 16 = 0001 0000
則  e.hash & oldCap = 0000 0000 = 0

    e.hash = 18 = 0001 0010,     oldCap = 16 = 0001 0000
則  e.hash & oldCap = 0001 0000 = 16

當 e.hash & oldCap == 0 時，新位置為 原數據所在的位置。即 table[j]
當 e.hash & oldCap != 0 時，新位置為 原數據所在的位置 + 原數組的長度。即 table[j + oldCap]

（2）源碼：

/**
* 給數組擴容
*/
final Node<K,V>[] resize() {
    // Step1：判斷數組是否需要擴容，若需要則擴容
    // 記錄原數組
    Node<K,V>[] oldTab = table;
    
    // 記錄原數組長度，若為 null，則為 0， 否則為 數組的長度
    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)
            newThr = oldThr << 1; // double threshold
    }
    // 原數組為null，若舊閾值大於0， 則數組長度為 閾值大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 原數組為 null，舊閾值小於等於0， 則數組長度、閾值均為預設值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 若新閾值為 0，則根據新數組長度重新計算閾值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // Step2:將原數組的數據複製到新數組中（重新計算元素新的位置）
    @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;
                        // 判斷節點是否需要移動，位運算 為 0 則不移動
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 位運算不為 0，需移動
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 將鏈表的尾節點置 null，並將頭節點放到新位置
                    if (loTail != null) {
                        loTail.next = null;
                        // 新位置為 原始位置
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 新位置為 原始位置 + 原始數組長度
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

 

6、get、getNode

　　用於獲取節點的 value 值。
（1）分析 get 的過程
　　Step1：先獲取節點，內部調用 getNode() 方法。
　　Step2：判斷 數組是否為 null 或者 長度為0，是則直接返回 null。對 key 進行 hash 並執行位運算（(length - 1) & hash(key)），得到數組下標，若當前數組下標位置數據為null，也返回 null。
　　Step3：若當前數組下標位置有值。
　　　　若 恰好是第一個元素，直接返回第一個節點即可。
　　　　若不是第一個元素，則判斷是否為 紅黑樹結構，是則返回樹節點。
　　　　若不是樹結構，則遍歷鏈表，返回相應的節點。

（2）源碼：

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

/**
* 真正獲取 value 的操作
*/
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 數組長度為 0 或者為 null，或者 節點不存在，直接返回一個 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;
        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;
}

 

三、常見面試題

1、為什麼使用 數組 + 鏈表 + 紅黑樹的 數據結構？

　　數組用於 確定 數據存儲的位置，鏈表用來解決 哈希衝突（當衝突時，在當前數組對應的位置形成一個鏈表）。當鏈表的長度大於等於 8 時，需要將其轉為 紅黑樹，查詢效率比鏈表高。
　　採用數組 + 鏈表的數據結構，可以結合 數組定址的優勢 以及 鏈表在增刪上的高效。

2、HashMap 什麼情況下會擴容？

　　當數組長度超過閾值時（loadFactor * capacity），預設負載因數（loadFactor） 為 0.75，數組（capacity）長度 為 16。
　　此時的閾值為 16 * 0.75 = 12，即只要數組長度大於 12 時，就會發生擴容（resize）。數組、閾值擴大到原來的 2 倍。即 當前數組長度為 16，擴容後變為 32，閾值為 24。

3、數組擴容為什麼長度是 2 的次冪？

　　為了實現高效、必須減少碰撞，即需要將數據儘量均勻分配，使每個鏈表長度大致相同。數據 key 的哈希值直接使用肯定是不行的，可以採用 取模運算 ，即 hash(key) % length，得到的餘數作為數組的下標（ table[hash(key) % length] ）。
　　但是取模運算的效率沒有 移位運算高（(length - 1) & hash(key)）。length 指的是數組的長度。

// Node 數組
transient Node<K,V>[] table;

JDK 1.8 源碼給的實現是 
    (length - 1) & hash(key)， // 計算數組下標值
    table[(length - 1) & hash(key)] // 定位到數組元素的位置
也即 
    (length - 1) & hash(key) == hash(key) % length,

想要上面等式成立， length 必須滿足 2 的次冪（效率最高）， 即 length = 2^n。

為什麼必須滿足 2 的次冪？
    因為只有 2 的次冪， length - 1 的二進位位全為1，使得 hash(key) 後幾位都進行 &1 操作， 這樣得到的結果等同於 hash(key) 後幾位的值。
    即 (length - 1) & hash(key) == hash(key) % length
    如果 不為 2 的次冪，那麼可能存在 某些值永遠都不會出現的情況。

舉個例子：
【hash(key) = 9, length = 16】
    此時 hash(key) % length = 9 % 16 = 9
    (length - 1) & hash(key) = 15 & 9 = 1111 & 1001 = 1001 = 9
    hash(key) % length == (length - 1) & hash(key)
    
【hash(key) = 27, length = 16】
    此時 hash(key) % length = 27 % 16 = 11
    (length - 1) & hash(key) = 15 & 27 = 01111 & 11011 = 1011 = 11
    hash(key) % length == (length - 1) & hash(key)
    
【hash(key) = 9, length = 15】
    此時 hash(key) % length = 9 % 15 = 9
    (length - 1) & hash(key) = 14 & 9 = 1110 & 1001 = 1000 = 8
    hash(key) % length !== (length - 1) & hash(key)
數組長度為 15 時，length -1 = 1110，此時不管如何，最後一位均不可能為 1，也即 1001、1101等這些值永遠都獲取不到。

 

4、String 中的 hashCode 方法

　　參考：https://segmentfault.com/a/1190000010799123。
　　以 31 為權，對每一個字元的 ASCII 碼進行運算。
　　選用 31 的原因，31 * i = 32 * i - i = (i << 5) - i，31 可以被虛擬機優化成 位運算，效率更高。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

 

5、HashMap 線程不安全？舉個例子？

　　HashMap 採用尾插法將數據插入鏈表的尾部，但其 putVal 方法是線程不安全的。putVal 方法中有段代碼如下：

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

　　當線程 A 與線程 B 同時進行 put 操作時，且兩個值的 key 經過 hash() 是一致的，即占用同一個數組元素。若此時數組元素為 null，線程 A 執行到這段代碼的時候，發現該位置數據為 null，則觸發一次 newNode 操作，這時線程 B 恰好也執行到這，同樣觸發一次 newNode 操作，這時不管是線程 A 還是線程 B成功，都會覆蓋當前元素，即線程不安全。
JDK 7 用的頭插法，會造成死迴圈（沒有過多研究，有時間再補充）。

6、HashMap、HashTable、ConcurrentHashMap的區別

（1）HashMap 是線程非安全的，允許存在 null 的 key 以及 null 的 value。且只有一個為 null 的key，可以存在多個為 null 的 value。HashMap 的效率比 HashTable 高
（2）HashTable 是線程安全的，不允許存在 null 值。
（3）ConcurrentHashMap 是線程安全的 HashMap，併發能力比 HashTable 強。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Json介紹
    Json的介紹和Json結構 JSON是JavaScript Object Notation的縮寫，意思是JavaScript 對象表示法 是存儲和交換文本信息的語法。類似 XML，不過它比 XML 更小、更快，更易解析 官網的介紹 http://www.json.org/json zh.html ...
  • 解決el-tree lazy懶載入時，連續勾選前兩個子節點後第二次進入預設選中時，將父節點也勾選的問題
    在用到el-tree的懶載入和預設勾選功能時，若第一次勾選前幾個連續節點，第二次進入預設勾選時，由於el-tree子節點尚未完全載入（只載入出來前幾個），預設勾選已經開始（已載入出來的子節點被預設勾選），這時el-tree會認為子節點全部勾選，所以父節點也被勾選，這就導致所有子節點都被勾選； 解決方 ...
  • 在 React 中使用 Typescript
    本篇不會過多講述 ts 語法，著重記錄下 在 React 中使用 ts 的方法以及踩坑經過。 ...
  • vue koa2 mongodb 從零開始做個人博客(一) 登錄註冊功能前端部分
    0.效果演示 插入視頻插不進來，就很煩。可以出門右拐去優酷看下(點我！)。 1.準備工作 1.1前端框架 前端使用了基於vue.js的nuxt.js。為什麼使用nuxt.js？ 首先我做的是博客的項目，所以SSR至關重要。雖然跟本文要講的登錄註冊沒有什麼關係，但是文章如果用axios來非同步獲取的話， ...
  • 性能調優，程式員轉型架構師的攔路虎【1】
    X 維度本身超出了技術範疇，但為了更好地服務業務，技術人也有必要懂得一些基礎的業務優化思路。如果只知道埋頭趕路，不知道抬頭看天，那我們技術人很容易做了費力不討好的事情，例如：某些性能瓶頸是由於業務流程設計不合理導致的，在業務流程優化完善之前，我們僅僅從技術視角去優化改善，極有可能事倍功半。具體說來，... ...
  • 大白話原型模式（Prototype Pattern）
    意圖 原型模式是創建型設計模式，可以複製已存在的對象而無需依賴它的類。 問題 假如現在有一個對象，我們想完全複製一份新的，我們該如何做？ 1. 創建同一個類的新對象 2. 遍歷所有已存在對象的值，然後將他們的值複製到新對象。 很好，但是我們會發現存在如下問題： 1. 該對象的值並不一定全對對外開放， ...
  • Java連載75-StringBuffer和StringBuilder
    一、StringBuffer和StringBuilder 1.StringBuffer是什麼？ 答：是一個字元串緩衝區，工作原理：預先在記憶體中申請一塊空間以容納字元序列，如果預留的空間，則進行自動擴容，以容納更多的字元序列。 2.StringBuffer\StringBuilder和String最大 ...
  • 實測兩款 GitHub 開源搶票插件，所有坑都幫你踩過了
    如果你對自己手速和市面上的各種 “加速包” 都沒什麼信心的話，不妨試試用程式員的手段搶票？ 況且，[12306 官方宣佈屏蔽了一大批付費搶票軟體]，這也意味著你即使給這些軟體付了會員費，也依舊搶不到票。 所以只能回到最初的手動搶票？No！No！No！ GitHub 上有兩個 “年經” 項目，每到春運 ...
一周排行
    -Advertisement-
    Play Games
  • Dapr Outbox 執行流程
    Dapr Outbox 是1.12中的功能。 本文只介紹Dapr Outbox 執行流程，Dapr Outbox基本用法請閱讀官方文檔 。本文中appID=order-processor，topic=orders 本文前提知識：熟悉Dapr狀態管理、Dapr發佈訂閱和Outbox 模式。 Outbo ...
  • Advanced .Net Debugging 7：托管堆與垃圾收集
    引言 在前幾章我們深度講解了單元測試和集成測試的基礎知識，這一章我們來講解一下代碼覆蓋率,代碼覆蓋率是單元測試運行的度量值,覆蓋率通常以百分比表示，用於衡量代碼被測試覆蓋的程度，幫助開發人員評估測試用例的質量和代碼的健壯性。常見的覆蓋率包括語句覆蓋率（Line Coverage）、分支覆蓋率（Bra ...
  • C#S7.NET實現西門子PLCDB塊數據採集的完整步驟
    前言 本文介紹瞭如何使用S7.NET庫實現對西門子PLC DB塊數據的讀寫，記錄了使用電腦模擬，模擬PLC，自至完成測試的詳細流程，並重點介紹了在這個過程中的易錯點，供參考。 用到的軟體： 1.Windows環境下鏈路層網路訪問的行業標準工具（WinPcap_4_1_3.exe）下載鏈接：http ...
  • WPF控制項：密碼框綁定MVVM
    從依賴倒置原則（Dependency Inversion Principle, DIP）到控制反轉（Inversion of Control, IoC）再到依賴註入（Dependency Injection, DI）的演進過程，我們可以理解為一種逐步抽象和解耦的設計思想。這種思想在C#等面向對象的編 ...
  • Python中的私有屬性與私有方法
    關於Python中的私有屬性和私有方法 Python對於類的成員沒有嚴格的訪問控制限制，這與其他面相對對象語言有區別。關於私有屬性和私有方法，有如下要點： 1、通常我們約定，兩個下劃線開頭的屬性是私有的（private）。其他為公共的（public）； 2、類內部可以訪問私有屬性（方法）； 3、類外 ...
  • C++ 訪問說明符詳解：封裝數據，控制訪問，提升安全性
    C++ 訪問說明符 訪問說明符是 C++ 中控制類成員（屬性和方法）可訪問性的關鍵字。它們用於封裝類數據並保護其免受意外修改或濫用。 三種訪問說明符： public：允許從類外部的任何地方訪問成員。 private：僅允許在類內部訪問成員。 protected：允許在類內部及其派生類中訪問成員。 示 ...
  • static_cast與dynamic_cast到底是什麼？
    寫這個隨筆說一下C++的static_cast和dynamic_cast用在子類與父類的指針轉換時的一些事宜。首先，【static_cast，dynamic_cast】【父類指針，子類指針】，兩兩一組，共有4種組合：用 static_cast 父類轉子類、用 static_cast 子類轉父類、使用 ...
  • C語言數據結構：雙向鏈表的增刪操作
    /******************************************************************************************************** * * * 設計雙向鏈表的介面 * * * * Copyright (c) 2023-2 ...
  • @ComponentScan註解的實現，Spring掃描包的過程
    相信接觸過spring做開發的小伙伴們一定使用過@ComponentScan註解 @ComponentScan("com.wangm.lifecycle") public class AppConfig { } @ComponentScan指定basePackage，將包下的類按照一定規則註冊成Be ...
  • opensips開啟python支持
    操作系統 ：CentOS 7.6_x64 opensips版本： 2.4.9 python版本：2.7.5 python作為腳本語言，使用起來很方便，查了下opensips的文檔，支持使用python腳本寫邏輯代碼。今天整理下CentOS7環境下opensips2.4.9的python模塊筆記及使用 ...
所有分類