在 HashMap 中，通過(guò)對(duì)鍵的哈希值進(jìn)行處理，能夠?qū)⑸傻墓４a映射到 HashMap 內(nèi)部數(shù)組（桶）中的索引位置。

如下圖所示：

這一過(guò)程可以通過(guò)以下步驟認(rèn)真分析：

想了解更多map數(shù)據(jù)結(jié)構(gòu)更多的可參考：HashMap的擴(kuò)容機(jī)制

1、哈希值的生成與處理

如我們之前討論的，第一次會(huì)調(diào)用 hashCode() 方法來(lái)生成一個(gè)完整的 32 位整數(shù)哈希碼。然后，使用以下代碼對(duì)哈希值進(jìn)行處理：

int h = key.hashCode();
h ^= (h >>> 16);

2、計(jì)算桶的索引

經(jīng)過(guò)處理后，哈希值可能會(huì)更分散，最后會(huì)用于計(jì)算桶的索引位置：

int index = h & (n - 1);

2.1 這里的計(jì)算方法：

• n 是當(dāng)前 HashMap 內(nèi)部數(shù)組的長(zhǎng)度（即桶的數(shù)量）。為了更高效地計(jì)算數(shù)組索引，我們通常選擇 n 為 2 的冪（例如 16、32、64 等），這允許高效的位操作。
• n - 1 的計(jì)算是為了確保采用位與運(yùn)算來(lái)進(jìn)行取模操作。例如，如果 n 為 16（即 10000），那么 n - 1 為 15（即 01111）。這樣做的好處是通過(guò)位與運(yùn)算能夠快速計(jì)算出在數(shù)組中的有效索引。

2.2 示例

假設(shè)生成的哈希值 h 為 0b11010110110101101010011000111101（即 32 位二進(jìn)制數(shù)），并且 HashMap 的桶數(shù)量 n 為 16（也即 index = h & 15）。

計(jì)算過(guò)程：

• 二進(jìn)制示例哈希值：11010110110101101010011000111101
• n-1：00000000000000000000000000001111 （即 15 的二進(jìn)制表示）

進(jìn)行位與操作：

        11010110110101101010011000111101
  &     00000000000000000000000000001111
  ------------------------------------------
        00000000000000000000000000000101  （結(jié)果即為 index）

• 結(jié)果 index 是 5，表示該鍵值對(duì)應(yīng)的元素存放在 HashMap 的第 5 個(gè)桶（數(shù)組索引為 5 的位置）。

3、哈希值總結(jié)

• 哈希值處理：通過(guò)對(duì)原始哈希碼的處理（即與高位信息進(jìn)行異或），可以確保更均勻的哈希分布，從而減少碰撞的機(jī)會(huì)。
• 桶的索引計(jì)算：使用 h & (n - 1) 技巧使得計(jì)算過(guò)程高效，將生成的哈希值直接映射到 HashMap 內(nèi)部數(shù)組的有效索引，從而實(shí)現(xiàn)快速的鍵值對(duì)存儲(chǔ)和檢索。
• 效率：以上步驟都是為了確保在 O(1) 平均情況下能快速訪問(wèn) HashMap 中的元素，同時(shí)減少由于哈希沖突引起的性能損失。

4、哈希沖突解決方案

拉鏈法（Separate Chaining）和開(kāi)放尋址法（Open Addressing）是兩種常用的哈希表沖突解決策略。

它們?cè)谔幚韮蓚€(gè)或多個(gè)鍵沖突（即哈希函數(shù)返回相同索引）時(shí)采取不同的策略。

下面是對(duì)這兩種方法的詳細(xì)介紹及示例：

4.1. 拉鏈法（Separate Chaining）

1.原理

基本思路是為每個(gè)哈希表的桶（數(shù)組索引）維護(hù)一個(gè)鏈表（或其他數(shù)據(jù)結(jié)構(gòu)），用來(lái)存儲(chǔ)所有哈希到同一索引位置的鍵值對(duì)。當(dāng)發(fā)生沖突時(shí)，新的鍵值對(duì)會(huì)被追加到這個(gè)鏈表中。

2.特點(diǎn)

• 沖突分離：拉鏈法可以有效處理沖突，因?yàn)槊總€(gè)桶可以容納多個(gè)元素。
• 空間利用率：空間利用率較高，尤其在負(fù)載因子較大時(shí)。

3.示例

設(shè)想一個(gè)簡(jiǎn)單的哈希表，哈希函數(shù)為 h(key) = key mod 5，并且存在以下鍵值對(duì)：

• (3, "A")
• (8, "B")
• (13, "C")
• (9, "D")

哈希表的桶數(shù)組將如下所示（使用鏈表處理沖突）：

Index: 0  -> null
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") -> null
Index: 4  -> (8, "B") -> null

當(dāng)插入鍵 13，計(jì)算得到 h(13) = 3，這個(gè)鍵會(huì)追加到索引 3 的鏈表中：

Index: 0  -> null
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") -> (13, "C") -> null
Index: 4  -> (8, "B") -> null

4.2. 開(kāi)放尋址法（Open Addressing）

1.原理

開(kāi)放尋址法在發(fā)生哈希沖突時(shí)，會(huì)在哈希表的數(shù)組中尋找下一個(gè)可用的桶來(lái)存儲(chǔ)沖突的元素。

常用的方法包括線性探測(cè)、二次探測(cè)和雙重哈希等。

2.特點(diǎn)

• 使用數(shù)組存儲(chǔ)數(shù)據(jù)：所有數(shù)據(jù)都存儲(chǔ)在哈希表的原始數(shù)組中，不需要額外的鏈表或其他數(shù)據(jù)結(jié)構(gòu)。
• 查找時(shí)間：在平均情況下，查找時(shí)間復(fù)雜度與負(fù)載因子密切相關(guān)，負(fù)載因子過(guò)高可能導(dǎo)致性能下降。

3.示例

仍然使用相同的哈希函數(shù) h(key) = key mod 5，并且存在以下鍵值對(duì)：

• (3, "A")
• (8, "B")
• (9, "D")

假設(shè)當(dāng)前哈希表的索引結(jié)構(gòu)如下：

Index: 0  -> null
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") 
Index: 4  -> (8, "B") 

當(dāng)插入鍵 9 時(shí)，計(jì)算得到 h(9) = 4，但索引 4 已經(jīng)被占用，因此會(huì)采取開(kāi)放尋址法策略查找下一個(gè)可用位置。這個(gè)位置是索引 0（線性探測(cè)），最終得到如下數(shù)據(jù)結(jié)構(gòu)：

Index: 0  -> (9, "D")
Index: 1  -> null
Index: 2  -> null
Index: 3  -> (3, "A") 
Index: 4  -> (8, "B") 

常用的探測(cè)方法

1、線性探測(cè)（Linear Probing）

• 當(dāng)發(fā)生沖突時(shí)，逐個(gè)檢查下一個(gè)可用的桶。通過(guò)簡(jiǎn)單地向后移動(dòng)（對(duì)當(dāng)前索引加 1）來(lái)查找下一個(gè)位置。
• 例如，如果索引 ii 已經(jīng)被占用，就檢查 (i+1)(i+1)， (i+2)(i+2)，...直到找到空桶。

這種方法的實(shí)現(xiàn)如下：

public int linearProbe(int hash, int i) {
    return (hash + i) % table.length;
}

2、二次探測(cè)（Quadratic Probing）

• 對(duì)于每次沖突，使用二次函數(shù)（例如，i2i2）的方式查找下一個(gè)位置。這有助于減少碰撞和聚集問(wèn)題。
• 例如，如果索引 ii 已經(jīng)被占用，就檢查 (i+12)(i+12)，(i+22)(i+22)，(i+32)(i+32)，...直到找到空桶。

實(shí)現(xiàn)類似于：

public int quadraticProbe(int hash, int i) {
    return (hash + i * i) % table.length;
}

3、雙重哈希（Double Hashing）

• 兩個(gè)不同的哈希函數(shù)同時(shí)使用，第一次利用主哈希函數(shù)獲取初步的索引，若發(fā)生沖突，則根據(jù)第二個(gè)哈希函數(shù)計(jì)算步長(zhǎng)。這種方法能夠減小聚集問(wèn)題。
• 例如，如果主哈希函數(shù)返回的索引 h1h1，而第二個(gè)哈希函數(shù)返回 h2h2，那么如果發(fā)生沖突，查找下一個(gè)位置的方法為：

public int doubleHash(int hash, int i) {
    return (hash + i * secondHash(key)) % table.length;
}

心得

在開(kāi)放尋址法中，探測(cè)的基礎(chǔ)是通過(guò)某種方式計(jì)算下一個(gè)桶的索引，從而避免沖突并正確處理數(shù)據(jù)。

每種探測(cè)方法（線性、二次、雙重）各有優(yōu)缺點(diǎn)，實(shí)際使用時(shí)可以根據(jù)應(yīng)用需求、性能和負(fù)載因子來(lái)選擇合適的探測(cè)方式。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論