散列表：java.util.HashMap源碼要點淺析

2019-11-17 04:08:55

字體：大中小

來源：轉載

供稿：網友

1、散列表要解決的一個問題就是散列值的沖突問題，通常是兩種方法：鏈表法和開放地址法。鏈表法就是將相同hash值的對象組織成一個鏈表放在hash值對應的槽位；開放地址法是通過一個探測算法，當某個槽位已經被占據的情況下繼續查找下一個可以使用的槽位。java.util.HashMap采用的鏈表法的方式，鏈表是單向鏈表，因此在刪除過程中要自己維持PRev節點，我想不采用雙向鏈表是從節省空間考慮。一個典型的查找過程：

for　(Entry<K,V>　e　=　table[indexFor(hash,　table.length)]; e　!=　null; e　=　e.next)
        Object　k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                return　e;
}

HashMap采用鏈表法而不是開放地址法，猜想可能的原因是從實用角度出發，對空間和時間效率做出的折中選擇。采用開放地址法，無論是線性探測或者二次探測都可能造成群集現象，而雙重散列會要求散列表的裝填程度比較低的情況下會有比較好的查找效率，容易造成空間的浪費。

2、什么是負載因子？負載因子a定義為

a=散列表的實際元素數目（n）/ 散列表的容量（m）

負載因子衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均次數是（1+a）次，因此如果負載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負載因子太小，那么散列表的數據將過于稀疏，對空間造成嚴重浪費。

回到HashMap的實現，HashMap中的loadFactor其實定義的就是該map對象允許的最大的負載因子，如果超過這個系數將重新resize.這個是通過threshold字段來判斷，看threshold的計算：

threshold　=　(int)(capacity　*　loadFactor);

結合上面的負載因子的定義公式可知，threshold就是在此loadFactor和 capacity對應下允許的最大元素數目，超過這個數目就重新resize，以降低實際的負載因子。默認的的負載因子0.75是對空間和時間效率的一個平衡選擇。注意到的一點是resize的規模是現有 capacity的兩倍：

if　(size++　>=　threshold)
　　resize(2　*　table.length);

3、可能你也注意到了，java.util.HashMap對key的hash值多做了一步處理，而不是直接使用hashCode：

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

這個處理的原因在于HashMap的容量總是采用2的p次冪，而取index（槽位）的方法是

static　int　indexFor(int　h,　int　length)
{
　　　return　h　&　(length-1);
}

這一運算等價于對length取模，也就是

h % 2^p

返回的將是h的p個最低位組成的數字，我們假設hash輸入是符合簡單一致散列，然而這一假設并不能推論出hash的p個最低位也會符合簡單一致散列，也許h的這p個最低位相同的幾率很大，那么沖突的幾率就非常大了。優秀的散列函數應該需要考慮所有的位。

上一篇：硬回車、軟回車、java轉義字符

下一篇： JAVA的前世今生