淺入淺出 1.7和1.8的 HashMap-有解無憂

前言

HashMap 是我們最最最常用的東西了，它就是我們在大學中學習資料結構的時候，學到的哈希表這種資料結構，面試中，HashMap 的問題也是常客，現在卷到必須答出來了，是必須會的知識，

我在學習 HashMap 的程序中，也遇到了不少問題，從概念到使用，整個程序都大大小小有些疑惑，然而我這些疑惑是因為我在某個知識環節上出了問題，導致不能理解，當我看了網上各種關于 HashMap 的有關博客以及 HashMap 的原始碼后，大致是理解了，但是我又不確定我是否是真的理解了，決定把 HashMap 的基本必須會的知識全部梳理下來，勢必得搞定它！

從最開始只是會使用它的 API 進行資料的存取，到決定要搞定疑惑、搞懂它的底層原理！

本篇文章，將從 0 淺入，從什么是哈希表講起，然后再說 Java 是怎樣實作哈希表的，整個梳理程序，將通過原始碼這個第一手的資料進行梳理分析，吸收知識、解決疑問，一步一步進行梳理，如果你是對 HashMap 懵懵懂懂的同學，那么歡迎跟著我的節奏一起來梳理！

閱讀完本篇文章，你將識訓：

認識哈希表、哈希沖突、沖突解決方法...
明白 Java 中哈希表是怎樣實作的...
table 陣列的意思、哈希桶的意思、Entry 的意思、Node 的意思...
1.7 的 HashMap 原始碼分析流程...
明白為什么已經有了 hashCode() 方法了，為什么還需要 hash() 方法
整個 put、get、擴容的程序...
1.8 的 HashMap 與 1.7 的不同的地方...
1.8 的擴容和 1.7 的擴容不一樣的地方...

總之，我相信螢屏前的你讀完肯定是有識訓的，當然，最大的識訓目前是我自己哈哈哈，

全文1萬2000多字，歡迎慢慢食用！由于本人水平有限，文中肯定還有許多不足之處，歡迎大家指出！

學習 HashMap 之前，我們需要知道什么？

我們知道 HashMap 就是 Java 中對哈希表這種資料結構的實作，倘若你不知道什么是哈希表，那么自然學習 HashMap 就會有大大的困難，倘若你知道哈希表，但僅僅是懵懵懂懂，有個簡單了解，那自然困難會降低許多，

所以，在學習 HashMap 之前，我們自然需要先知道什么是哈希表，當然還需要知道鏈表，不過本篇文章僅對哈希表作出說明，下面將開始講講哈希表這種抽象的資料結構，之所以說抽象，是因為下面只說哈希表應該具備的功能，但是不會給出具體實作，比如說我們可以簡單地使用陣列來實作哈希表，是吧，但是 Java 中的哈希表的實作就不是單單一個陣列就實作了的，

好了，廢話少說，開搞！

什么是哈希表？

哈希表（Hash Table，也有另一個稱呼：散串列），

哈希表是一種可以通過鍵（Key）直接訪問存盤在某個位置上的值（Value）的資料結構，

Hash 被翻譯成「哈希」、「散列」，Key 被翻譯成「鍵」、「關鍵字」

哈希表可以用來干嘛？

很簡單，和我們以前學習的資料結構一樣，可以用來存盤資料，

這不是廢話嘛？確實是廢話，

好吧，那么都可以存盤資料，為什么還會出現哈希表？直接用以前的順序表、鏈表、堆疊、佇列，這些資料結構來存盤不行嗎？這個問題問得好，確實，反正都是存盤，為什么還要哈希表？

要回答這個問題，就得說說為什么要有資料結構了，之所以需要資料結構，有一個目的就是：更有效地進行資料的存盤，不同的資料結構有不同的特性，順序表可以通過下標快速的查找出資料、鏈表可以不需要占用一整片連續的存盤空間進行存盤等等，哈希表也是一樣，

哈希表如何存盤資料？

哈希表存盤資料，給定一個 Key，存盤一個 Value，這里就需要用到一個哈希函式（散列函式），

以數學中的「函式」來理解，就是有一個函式是這樣的 $f(x) = y$，一個 $x$ 通過函式 $f$ 映射成值 $y$ ，

那么哈希函式也可以這樣理解：$hash(key) = address$

即鍵通過哈希函式映射成了一個地址，這個地址可以是陣列下標、記憶體地址等，

所以呢，存盤就是，通過哈希函式，把 Key 映射到某個地址，然后將 Value 存盤到這個地址上，

那么存盤后如何獲取，如何查找到這個 Value 呢？還是一樣，通過哈希函式獲得 Key 映射的地址，然后從這個地址取出 Value ，理想的情況下，在哈希表中查找資料，查找的時間復雜度是 $O(1)$ ，

所謂的「哈希」，就是 Key 通過哈希函式得到一個函式值（哈希值、哈希地址）的程序，

什么是哈希沖突？

在數學上，函式的映射可以是一對一，也可以是多對一的，也就是說一個 $x$ 可以映射一個 $y$ ，也可以多個 $x$ 映射到同一個 $y$ 上，

哈希函式也一樣，它有可能出現多對一的情況，即多個不同的 Key，通過哈希函式得到同一個地址（哈希值），

這就出現問題了，這種情況，就稱為「哈希沖突」，

哈希沖突完整定義：哈希函式可能把兩個或兩個以上的不同關鍵字映射到同一個地址，這種情況稱為沖突，發生沖突的不同關鍵字稱為同義詞，

你想一下，如果兩個不同的 Key，比方說 Key1 和 Key2，通過哈希函式得到同一個地址，那么你不解決這個沖突，直接進行存盤，那么就是這樣的：

Key1 先存盤，Key2 后存盤，自然只保存了 Key2
Key2 先存盤，Key1 后存盤，自然只保存了 Key1

這種情況是我們不想看到的，所以我們必須解決沖突，

如何解決沖突？

在解決沖突之前，我們應該盡量減少沖突的發生，這就需要設計得OK的哈希函式，當然沖突是必然的，是逃不掉的，當資料量夠多的時候，必然會發生沖突，所以就需要設計好解決沖突的方法，

哈希函式的設計注意點：

函式的定義域必須包含所有的 Key，函式的值域必須包含所有的 Value，其中值域是跟哈希表的大小有關的，
函式計算出來的地址（哈希值）應該能夠均勻分布在哈希表的記憶體地址空間上，從而減少沖突的發生，
函式能夠簡單就簡單實作，這樣計算會很快，

解決沖突的方法：

解決沖突的思想就是為沖突的 Key 找下一個沒有被占用的地址，

開放定址法
拉鏈法

這里就只說這個拉鏈法，

拉鏈法

把所有發生沖突的 Key 存盤在一個線性鏈表中，這個鏈表由 Key 哈希過后得到的地址（哈希地址）唯一標識，這就是拉鏈法，適用于經常插入和洗掉的情況，

哈希表查找效率

平均查找長度（ASL-Average Search Length），可衡量哈希表的查找效率，

ASL依賴于哈希表的「裝填因子（負載因子）」
$$
裝填因子的定義：α = \frac{哈希表中的元素個數}{哈希表的長度}?
$$
裝填因子越大，那么沖突的可能就越大，反之亦然，

1.7 版 HashMap

1.7 的HashMap

現在知道什么是哈希表了，那么接下來就看看 Java 中對哈希表的實作——HashMap

再次初識 1.7 的 HashMap

我們先看看檔案是怎樣說的，同時我進行了大體的翻譯，（這些說明可以從原始碼的開頭找到）

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

哈希表是通過實作 Map 介面實作的，因為 Map 介面提供了所有的映射操作，并且允許空值和空鍵（HashMap這個類可以簡單的看作是 HashTable 類，與之不同是，HashMap 是非同步且允許存盤空資料的），HashMap 這個類不保證映射的順序，特別是不保證這個順序會隨著時間的改變而保持不變，

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

當哈希函式恰當地將元素映射到哈希桶（the buckets）中，那么就具有常量時間里的基本操作（get 和 put）性能，遍歷 HashMap 這個集合的時候，遍歷的時間與 HashMap 實體的容量（哈希桶的數量）加上它的大小（Key和Value的映射數量，即鍵值對的數量）成正比，因此，不要設定初始的容量太高，或者負載因子太低，這是非常重要的，

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

HashMap 的實體，有兩個引數會影響它的性能：初始容量和負載因子，

初始容量就是哈希表中的哈希桶的數量，所謂哈希桶，就是一個個的陣列元素所占的坑位，我們可以稱整個陣列為 table 陣列，然后里面的一個個元素位置（table[i]）就是哈希桶，你給定一個初始容量，那么這個容量就會在 table 陣列創建的時候，作為這個 table 陣列的容量，即其長度、大小，

負載因子是衡量在當前 HashMap 自動擴容前，有多少個哈希桶是可以被獲取到的，當哈希表中的 Entry 物件（鍵值對）的數量超過了負載因子和當前容量的乘積時（load factor × capacity），那么哈希表就會進行重新哈希（rehashed，重構整個哈希表），table 陣列就變為原來的兩倍大，即擴容兩倍，

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

通常來說，默認的負載因子是 0.75，它是一個很好的平衡，平衡了時間以及空間，這個值過高，雖然會降低空間的開銷，但是會增加更多的時間來查找，當設定 HashMap 的初始容量時，應該，考慮好預期的 Entry 數量以及負載因子，以此減少 rehash 的次數，如果哈希表的初始容量（table 陣列的長度）大于 Entry 數量除以負載因子，則不會發生 rehash 操作，

If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table. Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.

如果需要使用 HashMap 實體來存盤許多的映射，那么就需要創建一個夠大容量的 HashMap 實體，這樣效率是最大的，比起你搞一個小容量的 HashMap，然后讓它自己 rehash、table 陣列翻倍，注意，使用許多有著相同 hashCode() 的 Key 的話，那肯定是會降低哈希表的性能的，因為沖突多了，為了降低這種影響，當這些 Key 是可比較的情況下，那么哈希表舊可以使用比較的方式去解決，

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:
Map m = Collections.synchronizedMap(new HashMap(...));

上面的意思就是說，需要注意 HashMap 是不同步的，也就是非執行緒安全的，在多執行緒并發的情況下對 HashMap 進行操作（添加、洗掉、映射），就會發生執行緒安全問題，導致資料不一致，如果想在多執行緒的情況下使用 HashMap，那么可以使用 Collections.synchronizedMap 方法將普通的 HashMap 包裝成同步的 HashMap，不過不推薦這樣使用，我們推薦使用 ConcurrentHashMap，

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

迭代器快速失敗（fail-fast）：如果 Map 在迭代器進行迭代的時候，Map 中的資料被修改了，那么迭代器就會拋出一個例外：ConcurrentModificationException，因為怕有不確定的行為風險，主要來說就是怕資料不一致，怕執行緒不安全，

看完了檔案的說明，現在可以知道，HashMap 大概有這樣的東西

哈希表的鍵值對（Entry）是存盤在一個名為 table 的陣列中的，Entry 的話，是把 Key、Value、hash 值，封裝為 Entry 物件，
table 陣列里面的一個個元素位置（table[i]）就是哈希桶，
哈希桶存盤的就是 Entry，也就是說一個個的哈希桶，存盤著一個個的 Entry 物件，
哈希表的初始容量指的就是 table 陣列的長度，
哈希表的容量指的是 table 陣列的長度；哈希表的大小指的是 Key 和 Value 映射的數量，即鍵值對的數量，這個很重要，需要搞清楚哈希表的「容量」和「容量」，別搞混了，
當 Entry 物件的數量 > load factor × capacity 時，就會自動擴容，table 陣列擴容為原來的兩倍，
哈希表是執行緒不安全的，

看到這里，可能還是有些抽象，沒事，接下來我們看下原始碼，

HashMap 中的成員變數

首先先看看 HashMap 定義的成員變數：

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    /**
     * The default initial capacity - MUST be a power of two.
     * 默認的初始化容量大小為16，這個大小必須為2次冪
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    
    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     * 最大的容量，如果任意帶參建構式傳入的值大于這個最大容量，就使用這個最大容量
     * 1 左移 30位，即 2的30次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
     * The load factor used when none specified in constructor.
     * 默認負載因子 0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     * table 陣列，必要時就可以重置大小，長度必須總是2次冪，注意這里的陣列型別的 Entry
     * Entry 是一個內部類，下面就可以看到了
     */
    transient Entry[] table;
    ... 
    /**
     * Entry 類，主要作為一個存盤 Key 和 Value 的節點，同時保存當前的通過哈希函式計算出來的 hash
     * next 指標，主要用于發生沖突時，使用拉鏈法解決沖突，指向鏈表下一個 Entry 節點的
     */
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;	 // 鍵
        V value;		 // 值
        Entry<K,V> next; // 指向下一個節點 ，從而形成解決沖突的鏈表
        final int hash;  // 哈希值
        ...
    }
    
    /**
     * The number of key-value mappings contained in this map.
     * size 代表的就是當前存盤在 map 中的 Key-Value 映射的數量，即 Entry 的數量
     */
    transient int size;
    
    /**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     * table 重置大小的閾值，這個閾值就是之前說的 load factor * capacity
     */
    int threshold;
    
    /**
     * The load factor for the hash table.
     *
     * @serial
     * 負載因子
     */
    final float loadFactor;
    
     /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     * 這個變數主要與 fail-fast 快速失敗 有關，后面再說，先留個印象，
     */
    transient int modCount;
    ...
}

所以說，在 JDK 1.7 及以前，HashMap 的底層資料結構是「陣列+鏈表」，這里的陣列指的就是 Entry 型別的 table 陣列，同時使用 Entry 作為鏈表的節點，

上圖說話！

hashmap 1.7 示意圖

4 個構造方法

接下來看看構造方法，HashMap 中有 4 個構造方法，按原始碼中的出現順序如下：

public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map<? extends K, ? extends V> m)

第一個構造方法，兩個引數，一個初始容量，另一個負載因子，很明顯，就是構造一個有著確切初始容量和確切負載因子的 HashMap 實體，原始碼是這樣的，

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     * 
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        // 下面3個if，是保證代碼的健壯性，不是主要內容
        // 初始容量小于0，那么拋出非法引數例外
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 初始容量大于最大容量（2^30），直接將2^30作為初始容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 如果負載因子小于等于0，或者負載因子有問題，拋出例外
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
		// 主要內容在這里
        // Find a power of 2 >= initialCapacity
        // 找到一個二次冪的數，如果當前輸入的初始容量剛好的二次冪，就不用找了
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
		
        this.loadFactor = loadFactor;				// 初始化，賦值
        threshold = (int)(capacity * loadFactor);	// 自動擴容的閾值
        table = new Entry[capacity];				// 創建大小為capacity的Entry陣列
        init();	// 一個空方法，有什么用？這個先不管，之后再說，目前知道上面的就足夠了，
    }

實際上，搞定上面第一個構造方法，后面的構造方法就輕而易舉了，第二個構造方法，只是輸入了一個初始化容量，直接呼叫第一個構造方法，而負載因子就是默認的 0.75，

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

第三個無參的構造方法，直接使用默認 0.75 的負載因子以及默認的初始化容量為 16 的 Entry 型別的 table 陣列，然后默認的閾值就是 0.75 × 16 = 12，即當 Entry 個數超過 12，存盤第 13 個 Entry 的時候，就會進行 resize、rehash，

	public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

第四個構造方法，接收一個確切的 Map，用 HashMap 包裝這個確切的 Map

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }

以上，就是 HashMap 的 4 個構造方法，看來還是可以搞定的嘛！

擾動/哈希函式

接著看原始碼，發現就是 hash() 了，我們知道，在 Object 中，已經有一個 hashCode() 方法了，這個 hashCode() 可以說是一個哈希函式，那為什么在 HashMap 中，又還需要另一個 hash() 方法呢？

在原始碼注釋里已經說明了，就是抵御低質量的哈希函式，讓 hashCode() 計算出來的哈希碼再次擾動（再次哈希），這是非常重要的，因為 HashMap 使用二次冪長度的 table 陣列，不進行再次哈希的話，就會遇到 hashCode 在較低位沒有差異的沖突，所以需要使用這個 hash() 方法，總而言之，就是再次擾動，降低沖突發生的概率，

有小伙伴可能有疑惑，「低質量的哈希函式」？hashCode() 不是 Java 固定實作好的嗎？為什么怕有低質量的 hashCode() ?

這個問題問得好，實際上，我們可以發現 hashCode() 是一個本地方法（Native Method）

public native int hashCode();

這就意味著，hashCode() 并不是由 Java 語言實作的，而是由 C 或 C++ 這些非 Java 語言是實作的，同一個 native 方法，如果用不同的 JVM 去呼叫，那么運行效率可能是不一樣的，因為不同的 JVM 對于某個 native 方法都有自己的實作，所以才需要擾動函式進行再次哈希，

hash() 方法（擾動函式）傳入的引數是 Key 的 hashCode() 計算出來的哈希碼（值），將這個哈希碼經過 hash() 方法得到最終的 hash 值，

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // 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);
    }

留個印象-indexFor

indexFor() 方法，哈希值和陣列長度減一進行與運算，

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

獲取哈希表的大小、判斷哈希表是否為空

    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }

    /**
     * Returns <tt>true</tt> if this map contains no key-value mappings.
     *
     * @return <tt>true</tt> if this map contains no key-value mappings
     */
    public boolean isEmpty() {
        return size == 0;
    }

put 的程序

HashMap 的 put() 方法：

public V put(K key, V value)

這個方法就是將某個確切的 Key 與某個確切的 Value 聯系起來，存盤到哈希表中，這樣它們之間就建立起映射的關系了，

如果當前哈希表中有了這個 Key，那么就用新的 Value 覆寫掉舊的 Value，

Key 和 Value 可以是 null，只能有一個 Key 為 null，可以有多個 Value 為 null，

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        // 將 Key 的 hashCode 再次哈希得到最終的 hash 值
        int hash = hash(key.hashCode());
        // 將 hash 值與陣列長度減一進行與運算，計算最終的哈希地址（即陣列下標）
        int i = indexFor(hash, table.length);
        // for 回圈是遍歷這個哈希桶上的鏈表，如果有鏈表的話，即 e.next != null 說明有鏈表了
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 如果該位置的 hash 值和當前要存盤的 Key 的 hash 值一樣，說明可能是同一 Key 或不同的 Key
            // 同一 Key 的話就可以覆寫，不同 Key 的話就需要解決這個沖突
            // 先是比較記憶體地址是否相等，如果記憶體地址不相等，再去使用 equals 方法判斷兩個 Key 是不是同一個，
            // 如果記憶體地址相等，說明是同一個 Key 了，不必使用 equals 了
            // equals 判斷是相等的話，那么肯定是同一個 Key 了，因為 hashCode 相等不能說明兩個物件相等
            // 但兩個物件相等的話，那么 equals 一定相等，
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 進入這里，說明是同一個 Key，那么就可以用新 Value 覆寫掉舊 Value 了
                V oldValue = https://www.cnblogs.com/god23bin/archive/2022/10/30/e.value;
                e.value = value;
                e.recordAccess(this);	// 這個先不管
                return oldValue;
            }
        }
		// 走到這里，說明 Map 中沒有這個 Key，那么就可以添加這個 Key-Value 的映射了
        modCount++;	// 說明資料發生了改變，fail-fast 會用到
        addEntry(hash, key, value, i);	// 添加這個Entry
        return null;
    }

    /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        // 判斷有沒有這個 null Key，有就新的 Value 覆寫舊的 Value
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        // 沒有，那么就添加上這個 Key 為 null 的映射
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

	static class Entry implements Map.Entry {
        ...
         /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }       
        
    }

所以，整個程序是這樣的：

將 Key 的 hashCode 再次哈希得到最終的 hash 值，然后通過這個 hash 值與陣列長度減一進行與運算，計算最終的哈希地址，接著就遍歷這個哈希桶（如果這個桶上有鏈表的話，如果這個哈希桶沒有存盤元素，那么直接存盤到當前哈希桶），判斷該位置的 hash 值和當前要存盤的 Key 的 hash 值是否一樣：

一樣說明是同一個 Key，則可以覆寫
不一樣說明不同 Key，發生哈希沖突，需要解決哈希沖突，那么先是比較這兩個 Key 的記憶體地址是否相等：
- 如果記憶體地址不相等，再去使用 equals 方法判斷兩個 Key 是不是同一個，
  - equals 判斷兩個 Key 為 true，直接新 Value 覆寫舊 Value，
  - equals 判斷兩個 Key 為 false，如果當前哈希桶有下一個節點，那么下一個節點進行回圈判斷，如果在當前鏈表節點一直判斷出 false，則將這個 Key 封裝成 Entry，頭插法插入該鏈表，
- 如果記憶體地址相等，說明是同一個 Key 了，不必使用 equals 了，此時直接新 Value 覆寫舊 Value，

那么到這里，我相信你已經看懂了 put 的程序了！

get 的程序

HashMap 的 get() 方法：

public V get(Object key)

如果 HashMap 中有這個 Key，那么就回傳這個 Key 映射的 Value，

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        // 將 Key 的 hashCode 再次哈希得到最終的 hash 值
        int hash = hash(key.hashCode());
        // indexFor(hash, table.length) 獲取 Key 所在 table 陣列中的下標
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            // for 回圈是遍歷這個哈希桶上的鏈表，如果有鏈表的話
            Object k;
            // 判斷該位置上的 Key 是否為我們需要的 Key
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

相信你搞懂了 put 的程序，那么 get 的程序也不難理解，程序是這樣的：

將 Key 的 hashCode 再次哈希得到最終的 hash 值，然后通過這個 hash 值與陣列長度減一進行與運算，計算最終的哈希地址（被封裝成 indexFor 方法了），接著還是一樣，遍歷哈希桶，判斷該位置上的 Key 是否為我們需要的 Key，

自動擴容-resize+transfer

上面我們也說了，有一個閾值，即 load factor × capacity 這個閾值，如果當前哈希表的大小超過了這個閾值，那么哈希表是需要擴容的，在 HashMap 中，它是不要手動干預，是會自動進行擴容的，那么它是怎樣自動擴容的？

回顧：

哈希表的容量：是指 table 陣列的長度，
哈希表的大小：是指存盤在哈希表中的元素（Entry 型別的元素）的個數，
capacity（容量）：默認16
load factor（負載因子）：默認0.75
threshold（閾值）：默認 0.75 × 16 = 12，即哈希表大小超過12就會自動擴容

我們回去看下 put 操作，可以看到倒數第二行代碼有個 addEntry() 方法

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = https://www.cnblogs.com/god23bin/archive/2022/10/30/e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);	// 就是這里，添加 Entry 物件
        return null;
    }

看 addEntry() 的原始碼，是這樣的：

存盤 Key、Value、hash 值到指定的哈希桶中，
判斷當前哈希表大小加一后，有沒有超出閾值，超過閾值則進行哈希表容量的 resize() 操作，

所以這個擴容就是通過 addEntry() 方法里的 size++ >= threshold 進行判斷是否需要擴容，進而呼叫擴容方法 resize() 實作所謂的自動擴容，

    /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

我們可以看到 resize() 的時候，引數是兩倍的陣列長度，也就是說將哈希表的容量擴大成原來的兩倍，

resize(2 * table.length);

那下面我們看看擴容是怎樣子的，看看 resize() 原始碼：

原始碼注釋也說了，將會對 HashMap 實體存盤的 Entry 進行 rehash（再次哈希）到一個擴容后的新陣列，如果當前容量是最大容量（MAXIMUM_CAPACITY，1 <<< 30，即$2^{30}$）了，那么就不會進行擴容，同時設定閾值為 Integer.MAX_VALUE，

    /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
    void resize(int newCapacity) {
        Entry[] oldTable = table;			// 原陣列
        int oldCapacity = oldTable.length;	// 原陣列長度 = 原容量
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        // 創建一個比原陣列長度大兩倍的新陣列
        Entry[] newTable = new Entry[newCapacity];
        // 轉移原陣列中的元素（Entry 物件）到新陣列中
        transfer(newTable);
        // 原陣列參考指向新陣列
        table = newTable;
        // 重新計算閾值
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = https://www.cnblogs.com/god23bin/archive/2022/10/30/table;	// 原陣列
        int newCapacity = newTable.length;
        // 遍歷原陣列
        for (int j = 0; j < src.length; j++) {
            // e 可以看成一個指標，指向第j個哈希桶上的Entry節點
            Entry e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    // 看當前位置上的 Entry 有沒有 next，有則說明是鏈表
                    // next 是 null，說明沒有鏈表，那么就不會執行下面的 while
                    Entry next = e.next;
                    // 計算當前 Entry 在新陣列中的位置
                    int i = indexFor(e.hash, newCapacity);
                    // e 的下一個節點指向新的哈希桶，可以把哈希桶當作表頭，這樣方便頭插法插入元素
                    e.next = newTable[i];
                    // 新的哈希桶存盤這個節點
                    newTable[i] = e;
                    // 移動指標 e 指向下一節點
                    e = next;
                } while (e != null);
            }
        }
    }

所以，總的來說，擴容的程序是這樣的：

我們 put 一個元素到哈希表，這個程序會呼叫 addEntry() 方法，在實際插入一個元素后，判斷當前 size 是否大于閾值，大于的話就會擴容，擴容的話，會傳入一個兩倍原陣列大小的引數，然后創建一個新的陣列，這個陣列的長度是原陣列的兩倍，再通過一個 transfer() 方法，將原陣列中的 Entry 重新哈希（rehash）到新陣列中，最后將原陣列參考指向新陣列，同時計算下新的閾值，

1.7 總結

1.7 的 HashMap，底層是 Entry 型別的陣列 + Entry 型別的鏈表，

這個陣列稱為 table 陣列（也有的人稱為桶陣列），陣列上的每個位置，可以稱為哈希桶，每一個哈希桶都是存盤 Entry 型別的元素的，同時可以知道每個哈希桶位置上都可以對應著一個解決沖突的鏈表的位置，

如果當要存盤的 Key-Value 的 Key 與當前位置上的 Key 發生沖突，那么就需要進行頭插法，將該 Key 插入當前哈希桶對應的鏈表，

如果當前存儲的元素的個數超過了閾值（threshold = load factor × capacity），那么就會進行擴容，創建一個兩倍原陣列大小的新陣列，然后將原陣列中的元素重新哈希到新陣列中，最后原陣列參考指向新陣列，進而完成擴容，

1.8 版 HashMap

1.8 的HashMap

在 JDK 1.8 開始，就變成了「陣列+鏈表/紅黑樹」

看看原始碼與1.7有什么區別

看看區別

DEFAULT_INITIAL_CAPACITY 寫法變高級了，從 16 直接改成 1 << 4

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

出現一個TREEIFY_THRESHOLD，樹化閾值，即鏈表轉成紅黑樹的閾值，默認為 8，

static final int TREEIFY_THRESHOLD = 8;

出現一個UNTREEIFY_THRESHOLD，解除樹化的閾值，即紅黑樹中的 Entry 數量小于 6，那么就從紅黑樹退化成鏈表，

static final int UNTREEIFY_THRESHOLD = 6;

出現一個MIN_TREEIFY_CAPACITY，最小樹化容量，即 table 陣列的長度最小需要 64，才有機會樹化，

static final int MIN_TREEIFY_CAPACITY = 64;

Node

接著，我們看到這里定義了一個 Node 節點，通過對比 1.7 版的，可以發現這個把 1.7 中的 Entry 換了個名，定義成 Node 節點，也就是說，在 1.8 中的 table 陣列，其型別不再是 Entry 型別，而是 Node 型別，即 Node 型別的 table 陣列，

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    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 = https://www.cnblogs.com/god23bin/archive/2022/10/30/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 = https://www.cnblogs.com/god23bin/archive/2022/10/30/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 陣列

transient Node<K,V>[] table;

擾動函式

hash()，擾動函式發生了變化，1.8 原始碼是這樣的：

讓 Key 的 hashCode 與上 hashCode 無符號右移 16 位，最終與運算的結果就是最終的 hash 值，

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

而 1.7 的是這樣的：

    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

構造方法

構造方法也有變化，但是主要的程序還是一樣的，主要的區別就是，此時的 table 陣列還沒有被創建出來，

    /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

	public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

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

可以說在 1.8 這里，HashMap 屬于懶加載的了，那么 table 陣列何時加載（創建）呢？沒錯，就是在 put 的時候才創建的，下面我們來看看，

put 的變化

put 多了一層封裝，需要在 putVal() 方法中理解

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
hash：Key 通過擾動函式得到最終 hash 值，
key、value：鍵和值，
onlyIfAbsent：如果為 true，那么不會改變已存在的值，
evict：如果為 false，說明 table 陣列正在創建中，

put 的思路還是一樣的：根據 Key 計算出哈希地址，判斷這個地址上有沒有沖突，沒有則直接插入這個 Node，有則需要解決沖突，變化大的就是代碼的實作（紅黑樹、尾插法），

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab-> table 陣列
        // p-> node 指標，指向哈希桶中第一個節點，可以說是鏈表表頭節點
        // n-> 代表 table 陣列的長度
        // i-> 代表 table 陣列的下標
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 第一次 put 就會進入這個判斷，進行陣列的創建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果 put 的這個 Key，找到的位置不會沖突，那么直接創建一個 Node 節點存盤這個鍵值對
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 發生沖突進入這里
            Node<K,V> e; K k;
            // 判斷是否是同一個Key，是就把指標 e 指向這個節點 p，然后直接走下面的 e 是否為空的判斷了
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)	// Key 不同，走這里，如果這個節點 p 是一個樹節點
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {	// Key 不同，沒有樹化，需要遍歷鏈表
                for (int binCount = 0; ; ++binCount) {
                    // e 指向的 p 的下一個節點，如果為空，說明是鏈表尾部了
                    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 相同與否，相同就跳出回圈，走下面的判斷
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 移動指標
                    p = e;
                }
            }
            // 這里就是，如果是同一個 Key ，就會走這里的覆寫
            if (e != null) { // existing mapping for key
                V oldValue = https://www.cnblogs.com/god23bin/archive/2022/10/30/e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)	// 判斷是否需要擴容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

get 的變化

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;
        // 判斷當前哈希表是否存在、是否有元素、得到的哈希地址上是否有元素（演算法的健壯性）
        // 判斷為 false 的話，自然說明沒有任何元素，還 get 個 p？
        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 的擴容機制，變化就大了！在 1.7 的時候，主要是通過 resize() 和 transfer() 相互配合完成擴容及元素轉移的，在 1.8 的時候，直接把 transfer() 也搞到 resize() 中了，而且 transfer 的 rehash 的演算法很美妙，不過擴容時機還是一樣，超過閾值就會擴容，

我們看看原始碼是這樣的：

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;	// 一開始 table 還沒創建，所以第一次這里的 oldTab 為空
        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;
            }
            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
            newCap = oldThr;
        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 陣列（當然，第一次創建陣列也是在這里創建）
        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) {	// 判斷第j個哈希桶是否為空
                    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);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { 
                            // 新位置：所在的原陣列位置下標加上原陣列容量（長度）
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        // 第一次不會走上面的 if，直接回傳新創建默認容量和閾值的陣列
        return newTab;
    }

這里面最難理解的就是 (e.hash & oldCap) == 0

運算結果為 0 的話，那么放入新陣列的位置和原陣列的位置是一樣的
運算結果不為 0 的話，那么就需要重新計算位置（新位置：所在的原陣列位置下標加上原陣列容量（長度））

理解 (e.hash & oldCap) == 0

需要知道的是：

e.hash： e 可以看成一個指標，是一個指向當前遍歷到的 Node 節點的指標，hash 指的是該 Node 節點存盤的 Key 的 hash 值，即 hash 值是通過 hash(key.hashCode()) 得到的最終存盤的 hash 值，
oldCap：表示原陣列的容量，即原陣列長度，同時這個長度是 2 次方冪，比如 $2^4 = 16$

何時這個操作等于 0 ？

我們可以從 oldCap 入手，假設 oldCap 是 16，那么其二進制為 10000

如果我們想 e.hash & oldCap 等于 0，那么該 Key 的 hash 值的二進制最高位必須為 0，剩下的二進制位可以不管，這樣進行與運算后的結果肯定是等于 0 的，

舉個例子，假設此時 hash 值對應的二進制為 01111，那么和 oldCap 進行與運算：

``e.hash & oldCap=10000 & 01111` = 00000 = 0

顯而易見，當 hash 值二進制的最高位為 0 的時候，和 oldCap 進行與運算后，結果必定為0

但是這個和擴容后位置有什么關系呢？我們知道，擴容是擴為原來的兩倍的，所以我們可以看下，計算擴容后該Node 節點應該在哪個新位置，

計算擴容后的位置，我們知道是這樣的，「hash 值 & 陣列長度減一」的運算結果，就是我們需要的陣列下標，

擴容后的應該在的位置（oldCap 是 16，2 倍就是32，32 對應二進制 100000，減一操作后為 011111）：

hash & 2 × oldCap - 1 = 01111 & 011111 = 01111

那沒擴容之前的位置在那里？我們計算下：

hash & oldCap - 1 = 01111 & 01111 = 01111

所以，我們可以發現，此時擴容后和擴容前，該元素的位置沒有發生變化，因此，才有這個結論：運算結果為 0 的話，那么放入新陣列的位置和原陣列的位置是一樣的，

何時這個操作不等于 0 ？

同樣，從 oldCap 入手，假設此時 oldCap 是16，對應二進制為 10000

如果我們想 e.hash & oldCap 不等于 0，那么該 Key 的 hash 值的二進制最高位必須為 1，剩下的二進制位可以不管，這樣進行與運算后的結果肯定是不等于 0 的，

還是一樣，舉例子，假設 hash 值對應的二進制為 10001，那么和 oldCap 進行與運算：

e.hash & oldCap = 10001 & 10000 = 10000 = 16 ≠ 0

顯而易見，hash 值二進制的最高位為 1，那么該結果必定不為 0

同理，來看下擴容前后的位置關系，

擴容前的位置：

hash & oldCap - 1 = 10001 & 01111 = 00001 = 1

擴容后的位置：

hash & 2 × oldCap - 1 = 10001 & 011111 = 10001 = 17

它們之間有一種巧妙的關系，就是：「擴容后的位置」會等于「擴容前的位置」加上「擴容前的陣列容量」，也就是說 10001(擴容后的位置) = 1(擴容前的位置) + 10000(擴容前的陣列容量，16)

所以，才有這個結論：運算結果不為 0 的話，那么就需要重新計算位置（新位置：所在的原陣列位置下標加上原陣列容量（長度）），

關于紅黑樹

待完善，等著填坑，

1.8 總結

在 1.8 的 HashMap中，底層是 Node 型別的陣列 + Node 型別的鏈表或者 + Node 型別的紅黑樹，

比起 1.7 來說，變化還是挺多的，原始碼的寫法也變得更加高級，當然效率也變得更高了，引入了紅黑樹提高查找效率，因為引入了紅黑樹，所以解決沖突的時候，就有些區別了，

如果當要存盤的 Key-Value 的 Key 與當前位置上的 Key 發生沖突，那么就需要進行尾插法（1.7 就是頭插法），將該 Key 插入當前哈希桶對應的鏈表，當這個鏈表的長度大于 8 且陣列長度大于等于 64 時，當前鏈表就會樹化，轉成紅黑樹，當紅黑樹中的元素小于 6 時，那么就會退化回來成為鏈表，如果僅僅鏈表長度大于 8，但是陣列長度小于 64，那么就只會進行擴容，不會把鏈表樹化（這部分的原始碼在 treeifyBin() 方法中），

結語

以上，就是淺入淺出 1.7 和 1.8 的 HashMap！

最后的最后

由本人水平所限，難免有錯誤以及不足之處， 螢屏前的靚仔靚女們 如有發現，懇請指出！

最后，謝謝你看到這里，謝謝你認真對待我的努力，希望這篇博客對你有所幫助！

你輕輕地點了個贊，那將在我的心里世界增添一顆明亮而耀眼的星！

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

標籤：其他

上一篇：SpringBoot 階段測驗 1

下一篇：Spring Boot入坑-1-入坑準備&Spring簡介