天天看點
傳回

我的入門學習

我們知道在Java 8中對于HashMap引入了紅黑樹進而提高操作性能，由于在上一節我們已經通過圖解方式分析了紅黑樹原理，是以在接下來我們将更多精力投入到解析原理而不是算法本身，HashMap在Java中是使用比較頻繁的鍵值對資料類型，是以我們非常有必要詳細去分析背後的具體實作原理，無論是C#還是Java原了解析，從不打算一行行代碼解釋，我認為最重要的是設計思路，重要的地方可能會多啰嗦兩句。

HashMap原理分析

我們由淺入深，循序漸進，首先了解下在HashMap中定義的幾個屬性，稍後會進一步講解為何要定義這個值，難道是靠拍腦袋嗎。

public class HashMap extends AbstractMap

implements Map, Cloneable, Serializable {

//預設初始化容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

//預設負載因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//連結清單轉紅黑樹門檻值

static final int TREEIFY_THRESHOLD = 8;

//取消門檻值

static final int UNTREEIFY_THRESHOLD = 6;

//最小樹容量

static final int MIN_TREEIFY_CAPACITY = 64;

}

構造函數分析

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR;

當執行個體化HashMap時，我們不指定任何參數，此時定義負載因子為0.75f

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

當執行個體化HashMap時，我們也可以指定初始化容量，此時預設負載因子仍為0.75f。

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

當執行個體化HashMap時，我們既指定預設初始化容量，也可指定負載因子，很顯然初始化容量不能小于0，否則抛出異常，若初始化容量超過定義的最大容量，則将定義的最大容量指派與初始化容量，對于負載因子不能小于或等于0，否則抛出異常。接下來根據提供的初始化容量設定門檻值，我們接下來看看上述tableSizeFor方法實作。

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;

這個方法是在做什麼處理呢？門檻值 = 2的次幂大于初始化容量的最小值。 到學習java目前為止，我們接觸到了模運算【%】、按位左移【<<】、按位右移【>>】，這裡我們将學習到按位或運算【|】、無符号按位右移【>>>】。按位或運算就是二進制有1，結果就為1，否則為0，而無符号按位右移隻是高位無正負之分而已。不要看到上述【n | = n >>> 1】一臉懵，實際上就是【n = n | n >>> 1】，和我們正常進行四則運算一個道理，隻不過是邏輯運算和位運算符号不同而已罷了。我們通過如下例子來說明上述結論，假設初始化容量為5，接下來我們進行如上運算。

0000 0000 0000 0000 0000 0000 0000 0101 cap = 5

0000 0000 0000 0000 0000 0000 0000 0100 n = cap - 1

　　　　0000 0000 0000 0000 0000 0000 0000 0010 n >>> 1

　　　　0000 0000 0000 0000 0000 0000 0000 0110 n |= n >>> 1

　　　　0000 0000 0000 0000 0000 0000 0000 0001 n >>> 2

　　　　0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 2

　　　　0000 0000 0000 0000 0000 0000 0000 0000 n >>> 4

　　　　0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 4

　　　　0000 0000 0000 0000 0000 0000 0000 0000 n >>> 8

　　　　0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 8

　　　　0000 0000 0000 0000 0000 0000 0000 0000 n >>> 16

　　　　0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 16

如上最終算出來結果為7，然後加上最初計算時減去的1，是以對于初始化容量為5的最小2次幂為8，也就是門檻值為8，要是初始化容量為8，那麼門檻值也為8。接下來到了我們的重點插入操作。

插入原理分析

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

上述插入操作簡短一行代碼，隻不過是調用了putVal方法，但是我們注意到首先計算了鍵的哈希值，我們看看該方法實作。

static final int hash(Object key) {

int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

直接了解方法大意是：若傳入的鍵為空，則哈希值為0，否則直接調用鍵的本地hashCode方法擷取哈希值，然後對其按位向右移16位，最後進行按位異或（隻要不同結果就為1）操作。好像還是不懂，我們暫且擱置一下，我們繼續看看插入方法具體實作。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {
Node[] tab; Node p; int n, i;

// 步驟【1】：tab為空擴容
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    
// 步驟【2】：計算index，并對null做處理     
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node e; K k;
    
    // 步驟【3】：鍵存在，直接覆寫值    
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
        
    // 步驟【4】：若為紅黑樹    
    else if (p instanceof TreeNode)
        e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    else {
        
        // 步驟【5】：若為連結清單
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                
                //若連結清單長度大于8則轉換為紅黑樹進行處理
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    if (e != null) {
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
++modCount;

// 步驟【6】：超過最大容量進行擴容
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

我們首先來看來步驟【2】，我們待會再來看步驟【1】實作，我們首先摘抄上述擷取鍵的索引邏輯

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

上述通過計算出鍵的哈希值并與數組的長度按位與運算，雜湊演算法直接決定鍵的存儲是否分布均勻，否則會發生沖突或碰撞，嚴重影響性能，是以上述【 (n - 1) & hash 】是發生碰撞的關鍵所在，難道我們直接調用鍵的本地hashCode方法擷取哈希值不就可以了嗎，肯定是不可以的，我們來看一個例子。假設我們通過調用本地的hashCode方法，擷取幾個鍵的哈希值為31、63、95，同時預設初始化容量為16。然後調用（n-1 & hash），計算如下：

0000 0000 0000 0000 0000 0000 0001 1111 hash = 31

0000 0000 0000 0000 0000 0000 0000 1111 n - 1

0000 0000 0000 0000 0000 0000 0000 1111 => 15

0000 0000 0000 0000 0000 0000 0011 1111 hash = 63

0000 0000 0000 0000 0000 0000 0111 1111 hash = 95

因為（2 ^ n-1）的低位始終都是1，再按照按位運算（0-1始終為0）所有最終結果都有1111，這就是為什麼傳回相同索引的原因，是以，盡管我們具有不同的哈希值，但結果卻是存儲到哈希桶數組相同索引位置。是以為了解決低位根本就沒有參與到運算中的問題：通過調用上述hash方法，按位右移16位并異或，解決因低位沒有參與運算導緻沖突，提高性能。我們繼續回到上述步驟【1】，當數組為空，内部是如何進行擴容的呢？我們來看看resize方法實作。

final Node[] resize() {

Node[] oldTab = table;
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;
}
else if (oldThr > 0) 
    newCap = oldThr;
else {               
    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;
......

由上可知：當執行個體化HashMap并無參時，此時預設初始化容量為16，預設門檻值為12，負載因子為0.75f，當指定參數（初始化容量比如為5），此時初始化容量為8，門檻值為8，負載因子為0.75f。否則也指定了負載因子，則以指定負載因子為準。同時當超過容量時，擴容後的容量為原容量的2倍。到這裡我們發現一個問題：hashTable中的容量可為奇或偶數，而HashMap中的容量永遠都為2的次幂即偶數，為何要這樣設計呢？

int index = (n - 1) & hash;

如上為HashMap計算在哈希桶數組中的索引位置，若HashMap中的容量不為2的次幂，此時通過按與運算，索引隻能為16或0，這也就意味着将發生更多沖突，也将導緻性能很差，本可通過O(1)進行檢索，現在需要O(log n)，因為發生沖突時，給定存儲桶中的所有節點都将存儲在紅黑樹中，若容量為2的次幂，此時按與運算符将和hashTable中計算索引存儲位置的方式等同，如下：

int index = (hash & 0x7FFFFFFF) % tab.length;

按照HashMap計算索引的方式，當我們從2的次幂中減去1時，得到的是一個二進制末位全為1的數字，例如預設初始化容量為16，如果從中減去1，則得到15，其二進制表示形式是1111，此時如果對1111進行任意數字的按位與運算，我們将得到整數的最後4位，換句話說，等價于對16取模，但是除法運算通常是昂貴的運算，也就是說按位運算比取模運算效率更高。到此我們知道HashMap中容量為2的次幂的原因在于：哈希桶數組索引存儲采取按位運算而非取模運算，因其效率比取模運算更高。進行完上述擴容後容量、門檻值重新計算後，接下來則需要對哈希桶數組重新哈希(rehash)，請繼續往下看。

影響HashMap性能因素分析

在講解上述重新哈希之前，我們需要重頭開始進行叙述，直到這裡，我們知道HashMap預設初始化容量為16，假如我們有16個元素放入到HashMap中，如果實作了很好的雜湊演算法，那麼在哈希桶數組中将在每個存儲桶中放入1個元素，在此種情況下，查找元素僅需要1次，如果是HashMap中有256元素，如果實作了很好的雜湊演算法，那麼在哈希桶數組中将在每個存儲桶中放入16個元素，同理，在此種情況下，查找任何一個元素，最多也隻需要16次，到這裡我們可以知道，如果HashMap中的哈希桶數組存儲的元素增加一倍或幾倍，那麼在每個存儲桶中查找元素的最大時間成本并不會很大，但是，如果持續維持預設容量即16不變，如果每個存儲桶中有大量元素，此時，HashMap的映射性能将開始下降。比如現在HashMap中有一千六百萬條資料，如果實作了很好的雜湊演算法，将在每個存儲桶中配置設定一百萬個元素，也就是說，查找任意元素，最多需要查找一百萬次。很顯然，我們将存儲的元素放大後，将嚴重影響HashMap性能，那麼對此我們有何解決方案呢？讓我們回到最初的話題，因為預設存儲桶大小為16且當存儲的元素條目少時，HashMap性能并未有什麼改變，但是當存儲桶的數量持續增加時，将影響HashMap性能，這是由于什麼原因導緻的呢？主要是我們一直在維持容量固定不變，我們卻一直增加HashMap中哈希桶數組中存儲元素的大小，這完全影響到了時間複雜度。如果我們增加存儲桶大小，則當每個存儲桶中的總項開始增加時，我們将能夠使得每個存儲桶中的元素個數保持恒定，并對于查詢和插入操作保持O(1)的時間複雜度。那麼增加存儲桶大小也就是容量的時機是什麼時候呢？存儲桶的大小（容量）由負載因子決定，負載因子是一種度量，它決定着何時增加存儲桶的大小（容量），以便針對查詢和插入操作保持O(1)的時間複雜度，是以，何時增加容量的大小取決于乘積（初始化容量 負載因子），是以容量和負載因子是影響HashMap性能的根本因素。我們知道預設負載因子是0.75，也就是百分之75，是以增加容量大小的值為（16 0.75）= 12，這個值我們稱之為門檻值，也就意味着，在HashMap中存儲直到第12個鍵值對時，都将保持容量為16，等到第13個鍵值對插入到HashMap中時，其容量大小将由預設的16變為（ 16 * 2）= 32。通過上述計算增加容量大小即門檻值的公式，我們從反向角度思考：負載因子比率 = 哈希桶數組中元素個數 / 哈希桶數組桶大小，舉個栗子，若預設桶大小為16，當插入第一個元素時，其負載因子比率 = 1 / 16 = 0.0625 > 0.75 嗎？若為否無需增加容量，當插入第13個元素時，其負載因子比率 = 13 / 16 = 0.81 > 0.75嗎？若為是則需增加容量。講完這裡，我們再來看看重哈希，在講解為什麼要進行重哈希之前，我們需要了解重哈希的概念：重新計算已存儲在哈希桶數組中元素的哈希碼的過程，當達到門檻值時，将其移動到另外一個更大的哈希桶數組中。當存儲到哈希桶數組中的元素超過了負載因子的限制時，此時将容量增加一倍并進行重哈希。那麼為何要進行重哈希呢？因為容量增加一倍後，如若不處理已存在于哈希桶數組中鍵值對，那麼将容量增加一倍則沒有任何意義，同時呢，也是為了保持每一個存儲桶中元素保持均勻分布，因為隻有将元素均勻的分布到每一個存儲桶中才能實作O(1)時間複雜度。接下來我們繼續進行重哈希源碼分析

總結

本節我們詳細講解了HashMap實作原理細節，一些比較簡單的地方就沒有再一一分析，文中若有叙述不當或了解錯誤之處，還望指正，感謝您的閱讀

存儲 機器學習/深度學習 算法 java c# 索引 .js入門學習 入門學習教程 學習入門教程 arcpy學習入門 基礎入門學習
上一篇: MaxCompute中使用OSS外部表讀取JSON資料
下一篇: 淺談JavaScript事件循環機制EventLoop

繼續閱讀