HashMap是Java中非常重要且被廣泛使用的數(shù)據(jù)結(jié)構(gòu)，其內(nèi)部實現(xiàn)充滿了有趣而復(fù)雜的算法。我們研究下HashMap內(nèi)部的一些核心算法，包括哈希沖突的解決、擴容策略、樹化與樹退化等。

1. 容量計算方法

即tableSizeFor方法。其主要目的是確保HashMap的容量始終是2的冪次方，這一特性對HashMap的哈希算法和擴容策略都至關(guān)重要。

// cap為用戶傳入的map初始化大小，將返回一個大于該數(shù)的，距離最近的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;
}

• Integer.numberOfLeadingZeros(cap - 1): 這個方法返回參數(shù)cap - 1的二進制表示中，從最高位開始連續(xù)的零的個數(shù)。這個值實際上表示了cap的二進制表示中，最高位的位置（不包括符號位）。
• -1 >>> Integer.numberOfLeadingZeros(cap - 1): 這一步通過將-1右移numberOfLeadingZeros位，實際上將最高位至numberOfLeadingZeros位之間的所有位都置為1，其余位為0。這樣做的目的是為了確保在后續(xù)的計算中，得到的值是一個2的冪次方減1的形式。
• (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1: 這一步對上述得到的值進行判斷和修正。如果計算結(jié)果小于0，說明cap為0，因此將容量設(shè)為1；如果計算結(jié)果超過了MAXIMUM_CAPACITY，即HashMap的最大容量限制，將容量設(shè)為MAXIMUM_CAPACITY；否則，將容量設(shè)為n + 1。這里的n + 1保證了返回的容量是2的冪次方。

總的來說，tableSizeFor方法確保了HashMap的容量始終是2的冪次方。這種容量設(shè)置的方式有助于提高哈希算法的性能，同時與HashMap的擴容策略密切相關(guān)。這樣的設(shè)計使得HashMap在進行哈希計算時，可以通過位運算，取代一些昂貴的除法運算，從而提高計算效率。

2. 哈希沖突：鏈表和紅黑樹

在HashMap中，哈希沖突是指不同的鍵可能映射到相同的索引位置的情況。為了解決沖突，HashMap采用了拉鏈法，即將具有相同哈希碼的鍵值對存儲在同一個數(shù)組位置，以鏈表的形式。

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

上述Node類表示HashMap中的一個節(jié)點，包含了鍵、值、哈希碼以及指向下一個節(jié)點的引用。當沖突的鏈表長度超過一定閾值（默認為8）時，HashMap會將鏈表轉(zhuǎn)換為紅黑樹，以提高查找效率。

static final int TREEIFY_THRESHOLD = 8;

// 當鏈表長度達到8時，將鏈表轉(zhuǎn)換為紅黑樹
void treeifyBin(Node<K, V>[] tab, int hash) {
    // ...
    if (n >= TREEIFY_THRESHOLD) {
        // 執(zhí)行轉(zhuǎn)換為紅黑樹的操作
        treeifyBin(tab, hash);
        // ...
    }
    // ...
}

3. 擴容：2 的冪次方擴容

當HashMap的元素數(shù)量達到一定負載因子時（默認為0.75），為了避免鏈表過長，會觸發(fā)擴容操作。在擴容時，HashMap將數(shù)組容量擴大至原來的兩倍，并重新計算所有元素的索引位置。

void resize() {
    int oldCap = table.length;
    int newCap = oldCap << 1;
    // 創(chuàng)建新的數(shù)組，大小為原來的兩倍
    Node<K, V>[] newTab = new Node[newCap];
    // 重新計算元素在新數(shù)組中的位置
    // ...
    table = newTab;
}

oldCap表示原數(shù)組的容量，newCap表示新數(shù)組的容量，通過位運算將原容量左移一位實現(xiàn)擴容。

4. 哈希碼計算：擾動函數(shù)

為了減小哈希沖突的概率，HashMap采用了擾動函數(shù)，將鍵的哈希碼進行“擾動”。

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

這里的hash方法通過異或運算和無符號右移等位運算，將鍵的哈希碼進行擾動，增加哈希碼的隨機性。

5. 樹化與樹退化

為了提高查找效率，當鏈表長度超過一定閾值（默認為8）時，HashMap會將鏈表轉(zhuǎn)化成紅黑樹。而在刪除或鏈表長度過短時，紅黑樹又可能退化成鏈表。

static final int UNTREEIFY_THRESHOLD = 6;

// 將紅黑樹退化為鏈表
void untreeify(Node<K, V>[] tab) {
    // ...
    if ((n <= UNTREEIFY_THRESHOLD) && (first instanceof TreeNode))
        // 執(zhí)行退化為鏈表的操作
        untreeify(tab);
    // ...
}

UNTREEIFY_THRESHOLD是一個閾值，表示當紅黑樹的節(jié)點數(shù)小于等于6時，將紅黑樹退化為鏈表。

6. 負載因子和重新哈希

負載因子是HashMap決定是否需要進行擴容的一個關(guān)鍵參數(shù)。當HashMap中的元素數(shù)量達到容量與負載因子的乘積時，就會觸發(fā)擴容。在擴容時，HashMap會重新計算所有元素的索引位置，這個過程稱為重新哈希。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

void addEntry(int hash, K key, V value, int bucketIndex) {
    // ...
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 執(zhí)行重新哈希的操作
        resize();
        // ...
    }
    // ...
}

DEFAULT_LOAD_FACTOR是一個默認的負載因子，表示當元素數(shù)量達到容量的75%時，觸發(fā)擴容。

通過這些代碼示例，我們可以稍微了解到HashMap內(nèi)部的一些核心算法。這些算法保證了HashMap在面對不同場景時能夠保持高效的性能，同時保證了數(shù)據(jù)結(jié)構(gòu)的穩(wěn)定性。深入了解這些算法不僅有助于我們理解HashMap的內(nèi)部工作原理，還能夠在需要的情況下更好地優(yōu)化我們的代碼。希望通過這次的有趣之旅，大家對HashMap內(nèi)部的奧秘有了更深層次的理解。