2022 最新 JDK 17 HashMap 源碼解讀 (一)

目錄

• ​​HashMap簡介​​

HashMap簡介

Map 接口的基于哈希表的實作。此實作提供所有可選的映射操作，并允許空值和空鍵。 （HashMap 類大緻相當于 Hashtable，除了它是不同步的并且允許空值。）這個類不保證映射的順序；特别是，它不保證訂單會随着時間的推移保持不變。

此實作為基本操作（get 和 put）提供恒定時間性能，假設哈希函數将元素正确地分散在桶中。對集合視圖的疊代需要的時間與 HashMap 執行個體的“容量”（桶的數量）加上它的大小（鍵值映射的數量）成正比。是以，如果疊代性能很重要，則不要将初始容量設定得太高（或負載因子太低），這一點非常重要。

HashMap 的執行個體有兩個影響其性能的參數：初始容量和負載因子。容量是哈希表中的桶數，初始容量隻是哈希表建立時的容量。負載因子是哈希表在其容量自動增加之前允許達到的程度的度量。當哈希表中的條目數超過負載因子和目前容量的乘積時，對哈希表進行重新哈希（即重建内部資料結構），使哈希表的桶數大約增加一倍。

作為一般規則，預設負載因子 (.75) 在時間和空間成本之間提供了良好的折衷。較高的值會減少空間開銷，但會增加查找成本（反映在 HashMap 類的大多數操作中，包括 get 和 put）。在設定其初始容量時，應考慮映射中的預期條目數及其負載因子，以盡量減少重新哈希操作的次數。如果初始容量大于最大條目數除以負載因子，則不會發生重新哈希操作。

如果要在一個 HashMap 執行個體中存儲許多映射，則建立具有足夠大容量的映射将比讓它根據需要執行自動重新散列以增加表來更有效地存儲映射。請注意，使用具有相同 hashCode() 的多個鍵是降低任何哈希表性能的可靠方法。為了改善影響，當鍵是 Comparable 時，此類可以使用鍵之間的比較順序來幫助打破平局。

請注意，此實作不同步。如果多個線程同時通路一個哈希映射，并且至少有一個線程在結構上修改了映射，則必須在外部進行同步。 （結構修改是添加或删除一個或多個映射的任何操作；僅更改與執行個體已包含的鍵關聯的值不是結構修改。）這通常通過在自然封裝映射的某個對象上同步來完成.如果不存在這樣的對象，則應使用 Collections.synchronizedMap 方法“包裝”Map。

這最好在建立時完成，以防止對Map的意外不同步通路： Map m = Collections.synchronizedMap(new HashMap(…));所有此類的“集合視圖方法”傳回的疊代器都是快速失敗的：如果在建立疊代器後的任何時間對映射進行結構修改，除了通過疊代器自己的 remove 方法之外，疊代器将抛出 ConcurrentModificationException .是以，面對并發修改，疊代器快速而幹淨地失敗，而不是在未來不确定的時間冒任意的、非确定性的行為。

請注意，不能保證疊代器的快速失敗行為，因為一般來說，在存在不同步的并發修改的情況下，不可能做出任何硬保證。快速失敗的疊代器會盡最大努力抛出 ConcurrentModificationException。是以，編寫一個依賴于這個異常的正确性的程式是錯誤的：疊代器的快速失敗行為應該隻用于檢測錯誤。

此類是 Java 集合架構的成員。從以下版本開始：1.2 另請參見：Object.hashCode()、Collection、Map、TreeMap、Hashtable 作者：Doug Lea、Josh Bloch、Arthur van Hoff、Neal Gafter 類型參數： – 此映射維護的鍵的類型 – 映射值的類型

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    @java.io.Serial
    private static final long serialVersionUID = 362498820763181265L;      

實施說明。此映射通常充當分箱（分桶）哈希表，但當箱變得太大時，它們将轉換為 TreeNode 的箱，每個結構類似于 java.util.TreeMap 中的結構。大多數方法嘗試使用正常的 bin，但在适用時中繼到 TreeNode 方法（隻需檢查節點的執行個體）。 TreeNode 的 bin 可以像任何其他 bin 一樣被周遊和使用，但在填充過多時還支援更快的查找。然而，由于絕大多數正常使用的 bin 并沒有被過度填充，是以在 table 方法的過程中檢查樹 bin 的存在可能會被延遲。

樹箱（即元素都是 TreeNodes 的箱）主要按 hashCode 排序，但在 ties 的情況下，如果兩個元素屬于相同的“C 類實作 Comparable”，則 type 然後它們的 compareTo 方法用于訂購。 （我們保守地通過反射檢查泛型類型來驗證這一點——參見方法 compatibleClassFor）。當鍵具有不同的哈希值或可排序時，樹箱增加的複雜性在提供最壞情況 O(log n) 操作時是值得的，是以，在 hashCode() 方法傳回的值很差的意外或惡意使用下，性能會優雅地下降分布式的，以及許多鍵共享一個 hashCode 的，隻要它們也是 Comparable 的。 （如果這些都不适用，與不采取預防措施相比，我們可能會浪費大約兩倍的時間和空間。但唯一已知的案例源于糟糕的使用者程式設計實踐，這些實踐已經很慢，以至于這沒什麼差別。）

因為 TreeNode 的大小大約是正常節點的兩倍，是以我們僅在 bin 包含足夠的節點以保證使用時才使用它們（請參閱 TREEIFY_THRESHOLD）。當它們變得太小（由于移除或調整大小）時，它們會被轉換回普通垃圾箱。在具有良好分布的使用者哈希碼的使用中，很少使用樹箱。理想情況下，在随機 hashCodes 下，bin 中節點的頻率遵循泊松分布 (http:en.wikipedia.orgwikiPoisson_distribution)，預設調整大小門檻值為 0.75，平均參數約為 0.5，盡管由于調整大小粒度而存在很大差異.忽略方差，清單大小 k 的預期出現是 (exp(-0.5) pow(0.5, k) factorial(k))。第一個值是：

0: 0.60653066

1: 0.30326533

2: 0.07581633

3: 0.01263606

4: 0.00157952

5: 0.00015795

6: 0.00001316

7: 0.00000094

8: 0.00000006

更多：小于千萬分之一 樹箱的根通常是它的第一個節點。然而，有時（目前僅在 Iterator.remove 上），根可能在其他地方，但可以在父連結之後恢複（方法 TreeNode.root()）。

所有适用的内部方法都接受哈希碼作為參數（通常由公共方法提供），允許它們互相調用而無需重新計算使用者哈希碼。大多數内部方法還接受“tab”參數，通常是目前表，但在調整大小或轉換時可能是新表或舊表。

當 bin 清單被樹化、拆分或未樹化時，我們将它們保持在相同的相對通路周遊順序（即字段 Node.next）中，以更好地保留局部性，并稍微簡化調用 iterator.remove 的拆分和周遊的處理。在插入時使用比較器時，為了在重新平衡之間保持總排序（或此處要求的接近），我們将類和 identityHashCodes 比較為決勝局。

由于子類 LinkedHashMap 的存在，普通模式與樹模式之間的使用和轉換變得複雜。請參閱下面定義為在插入、删除和通路時調用的鈎子方法，這些方法允許 LinkedHashMap 内部保持獨立于這些機制。 （這還需要将映射執行個體傳遞給可能建立新節點的某些實用程式方法。）類似并發程式設計的基于 SSA 的編碼風格有助于避免在所有曲折的指針操作中出現别名錯誤。

預設初始容量 - 必須是 2 的幂。

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

最大容量，如果一個更高的值由任何一個帶參數的構造函數隐式指定時使用。必須是 2 <= 1<<30 的幂

static final int MAXIMUM_CAPACITY = 1 << 30;

構造函數中未指定時使用的負載因子。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

使用樹而不是清單的 bin 計數門檻值。将元素添加到至少具有這麼多節點的 bin 時，bin 将轉換為樹。該值必須大于 2 并且應至少為 8 以與樹木移除中關于在收縮時轉換回普通 bin 的假設相吻合

static final int TREEIFY_THRESHOLD = 8;

在調整大小操作期間 untreeifying（拆分）bin 的 bin 計數門檻值。應小于 TREEIFY_THRESHOLD，并且最多 6 以在移除時進行收縮檢測。

static final int UNTREEIFY_THRESHOLD = 6;

可對其進行樹化的 bin 的最小表容量。 （否則，如果 bin 中有太多節點，則調整表的大小。）應至少為 4 TREEIFY_THRESHOLD 以避免調整大小和樹化門檻值之間的沖突。

static final int MIN_TREEIFY_CAPACITY = 64;

基本哈希 bin 節點，用于大多數條目。 （參見下面的 TreeNode 子類，以及 LinkedHashMap 中的 Entry 子類。）

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;

            return o instanceof Map.Entry<?, ?> e
                    && Objects.equals(key, e.getKey())
                    && Objects.equals(value, e.getValue());
        }
    }      

計算 key.hashCode() 并将哈希的較高位傳播（XOR）到較低位。由于該表使用二次幂掩碼，是以僅在目前掩碼之上位變化的散列集将始終發生沖突。 （已知的例子是在小表中儲存連續整數的 Float 鍵集。）是以，我們應用了一種變換，将高位的影響向下傳播。在位擴充的速度、實用性和品質之間存在折衷。因為許多常見的散列集已經合理分布（是以不要從傳播中受益），并且因為我們使用樹來處理 bin 中的大量沖突，我們隻是以最便宜的方式對一些移位的位進行異或，以減少系統損失，以及合并最高位的影響，否則由于表邊界，這些最高位将永遠不會用于索引計算。

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

如果 x 的 Class 是“class C implements Comparable”的形式，則傳回 x 的 Class，否則傳回 null。

static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (Type t : ts) {
                    if ((t instanceof ParameterizedType) &&
                        ((p = (ParameterizedType) t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }      

如果 x 比對 kc（k 的篩選可比類），則傳回 k.compareTo(x)，否則傳回 0。

@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }      

/**
 * 傳回給定目标容量的 2 次方。
 */      

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}      

該表在首次使用時初始化，并根據需要調整大小。配置設定時，長度始終是 2 的幂。 （我們還在某些操作中允許長度為零，以允許目前不需要的引導機制。

transient Node<K,V>[] table;

儲存緩存的 entrySet()。請注意，AbstractMap 字段用于 keySet() 和 values()。

transient Set<Map.Entry<K,V>> entrySet;

此映射中包含的鍵值映射的數量

transient int size;

此 HashMap 已在結構上修改的次數 結構修改是指更改 HashMap 中的映射數量或以其他方式修改其内部結構（例如，重新散列）的那些。該字段用于使 HashMap 的 Collection-views 上的疊代器快速失敗。 （請參閱 ConcurrentModificationException）

transient int modCount;      

要調整大小的下一個大小值（容量負載因子）。

（javadoc 描述在序列化時為真。此外，如果尚未配置設定表數組，則此字段儲存初始數組容量，或零表示 DEFAULT_INITIAL_CAPACITY。）

int threshold;

/**
 * 哈希表的負載因子
 *
 * @serial
 */
final float loadFactor;      

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

參數：

initialCapacity - 初始容量

loadFactor – 負載因子

抛出：

IllegalArgumentException – 如果初始容量為負或負載因子為非正

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

構造一個具有指定初始容量和預設加載因子 (0.75) 的空 HashMap。參數： initialCapacity - 初始容量。抛出： IllegalArgumentException – 如果初始容量為負數。

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

構造一個具有預設初始容量 (16) 和預設加載因子 (0.75) 的空HashMap 。

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

構造一個與指定Map具有相同映射的新HashMap 。 HashMap是使用預設加載因子 (0.75) 和足以容納指定Map中的映射的初始容量建立的。

參數：

m - 其映射将放置在此Map中的Map

抛出：

NullPointerException – 如果指定的Map為空

public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }      

實作 Map.putAll 和 Map 構造函數。

參數：

m – Map

evict – 最初構造此映射時為 false，否則為 true（中繼到方法 afterNodeInsertion）

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            } else {
                // Because of linked-list bucket constraints, we cannot
                // expand all at once, but can reduce total resize
                // effort by repeated doubling now vs later
                while (s > threshold && table.length < MAXIMUM_CAPACITY)
                    resize();
            }

            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }      

傳回此映射中鍵值映射的數量。

傳回：

此映射中的鍵值映射的數量

public int size() {
        return size;
    }