前言

關(guān)于HashMap，是Java程序員和Android程序員日常使用頻率相當(dāng)高的一種集合類型了，熟悉的掌握它的使用方式還是很有必要的，要是能做到知其所以然那就更好了。本文參照JDK1.8的源碼進行講解。

1.介紹

關(guān)于HashMap，它是一種通過鍵值對映射來存儲對象的集合，繼承于AbstractMap，實現(xiàn)了Map、Cloneable、java.io.Serializable接口，它的內(nèi)部實現(xiàn)原理所包含的知識點還是非常的多的。要想更好的理解HashMap，首先還要對其內(nèi)部的幾個變量的含義有一定的了解。

1.size: 集合的大小。
2.loadFactor: 負載因子，默認為0.75(對空間和時間效率的一種平衡值，最好不要自己修改)。
3.threshold: 臨界值，當(dāng)HashMap的大小達到臨界值時，就需要重新分配大小。
4.table: 存儲鍵值對數(shù)據(jù)的哈希桶數(shù)組(即HashMap中的數(shù)據(jù)實際是存儲在此數(shù)組中的)。
5.Node<K, V>: table中每一個元素的實體類，由hash值，key值，value值，以及next(Node類型)元素組成；
              Node實現(xiàn)了Map中的Entry接口，其本身是一個單向鏈表。
6.TreeNode<K, V>: 紅黑樹節(jié)點實現(xiàn)類，繼承自LinkedHashMap.Entry<K,V>類

另外，在JDK1.8以后，HashMap對底層的實現(xiàn)以及擴容機制等進行了優(yōu)化，采用數(shù)組+鏈表/紅黑樹的方式存儲數(shù)據(jù)。因為即使負載因子的值和Hash算法設(shè)計的再合理也是不會百分之百的避免哈希碰撞的發(fā)生，而這樣就有可能造成某個位桶下的鏈表長度過長，當(dāng)鏈表的長度超過8的時候，這個鏈表就將轉(zhuǎn)換成紅黑樹，因為如果鏈表的長度過長，就會嚴重降低HashMap的數(shù)據(jù)訪問速度，而轉(zhuǎn)化成紅黑樹就是利用了紅黑樹快速增刪改查的特點來提高HashMap的性能。具體結(jié)構(gòu)如下：

hashbody.png

有了一些基本的了解之后，我們正式學(xué)習(xí)下它的源碼。

2.構(gòu)造方法

1.無參構(gòu)造，通常我們都用這個構(gòu)造方法創(chuàng)建一個HashMap，該構(gòu)造方法初始化默認的負載因子值為0.75。

public HashMap() {
    this.loadFactor = 0.75F;
}

2.指定“容量大小”和“負載因子”的構(gòu)造函數(shù)：

public HashMap(int var1, float var2) {
    // 如果指定的容量值小于0，則拋出異常
    if (var1 < 0) {
        throw new IllegalArgumentException("Illegal initial capacity: " + var1);
    } else {
        // 如果指定的容量大小超過了1073741824，那么就讓容量值為1073741824
        if (var1 > 1073741824) {
            var1 = 1073741824;
        }
        /**
         * 如果指定的負載因子值大于0并且是一個合法數(shù)字時，將指定的值賦值給loadFactor變量，
         * 同時根據(jù)指定的容量大小來計算臨界值的大小，否則拋出異常。
         */
        if (var2 > 0.0F && !Float.isNaN(var2)) {
            this.loadFactor = var2;
            this.threshold = tableSizeFor(var1); // 此方法為計算臨界值的方法，詳解見下
        } else {
            throw new IllegalArgumentException("Illegal load factor: " + var2);
        }
    }
}

/**
 * 此方法為計算當(dāng)前HashMap中臨界值的方法，方法中涉及到了按位或操作以及邏輯運算符操作，這里面運算符的使用方式還請自行科普，
 * 總之該方法返回的值一定是大于或者等于var0的2的整數(shù)次方，并且是最接近傳入的var0的值的2的整數(shù)次方。
 * 例如：傳入了12，返回的為16；傳入的16，返回的16；傳入的17，返回的32。
 */
static final int tableSizeFor(int var0) {
    int var1 = var0 - 1;
    var1 |= var1 >>> 1;
    var1 |= var1 >>> 2;
    var1 |= var1 >>> 4;
    var1 |= var1 >>> 8;
    var1 |= var1 >>> 16;
    return var1 < 0 ? 1 : (var1 >= 1073741824 ? 1073741824 : var1 + 1);
}

3.指定“容量大小”的構(gòu)造函數(shù)，不多說，都懂，只是內(nèi)部再調(diào)用上面的構(gòu)造方法

public HashMap(int var1) {
    this(var1, 0.75F);
}

4.傳入一個Map類型參數(shù)的構(gòu)造函數(shù)：

public HashMap(Map<? extends K, ? extends V> var1) {
    this.loadFactor = 0.75F; ，// 賦值負載因子的值為默認值0.75
    this.putMapEntries(var1, false); // 將傳入的集合中的數(shù)據(jù)逐個添加到HashMap中
}

3.常用方法：

1.put(K var1, V var2)：向集合中添加key為var1，value為var2的鍵值對數(shù)據(jù)。

/**
 * 方法內(nèi)部調(diào)用putVal方法，其中第一個參數(shù)又調(diào)用了hash()方法
 */
public V put(K var1, V var2) {
    return this.putVal(hash(var1), var1, var2, false, true);
}

/**
 * 此方法返回根據(jù)var0(put方法中傳入的key值)得到一個哈希值，首先判斷var0是否為空，
 * 如果為空，則直接返回0，如果不為空，返回var0的hashCode()方法返回的值的高16位異或低16位后所得到的值。
 */
static final int hash(Object var0) {
    int var1;
    return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}

/**
 * 此方法才是真正的添加操作，方法內(nèi)部可以分為幾個步驟
 */
final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) {
    /**
     * 1.創(chuàng)建臨時變量var6并指向當(dāng)前集合中的table，創(chuàng)建臨時變量var8并讓其等于var6的長度；
     *   如果table為空或者table的長度為0，那么就調(diào)用resize()方法進行初始化相關(guān)操作。
     */
    HashMap.Node[] var6;
    int var8;
    if ((var6 = this.table) == null || (var8 = var6.length) == 0) {
        var8 = (var6 = this.resize()).length;
    }
    /**
     * 2.創(chuàng)建臨時變量var7，并讓其指向var6[(var8 - 1) & var1]，同時var9為計算出的數(shù)組索引值；
     *   如果var7為空，說明在此索引上沒有發(fā)生哈希碰撞直接調(diào)用newNode方法創(chuàng)建一個Node元素并指向table的第var9個索引上。
     */
    Object var7;
    int var9;
    if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
        var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
    } else {
        /**
         * 3.如果var7不為空，說明此時發(fā)生了碰撞。首先，創(chuàng)建兩個臨時變量var10和var11;
         *   如果var7的hash值等于var1并且var7的key與var2相等(說明已經(jīng)存在這個key)，此時直接將var10指向var7(其實就是覆蓋之前的值)
         */
        Object var10;
        Object var11;
        if (((HashMap.Node)var7).hash == var1 && ((var11 = ((HashMap.Node)var7).key) == var2 || var2 != null && var2.equals(var11))) {
            var10 = var7;
        } else if (var7 instanceof HashMap.TreeNode) {
            /**
             * 如果不存在這個key，此時判斷var7是不是TreeNode(紅黑樹)類型；
             * 如果是紅黑樹類型，那么調(diào)用putTreeVal方法給樹(var7)插入樹節(jié)點
             */
            var10 = ((HashMap.TreeNode)var7).putTreeVal(this, var6, var1, var2, var3);
        } else {
            /**
             * 進入到這里，說明此時var7還是鏈表，此時創(chuàng)建int類型臨時變量var12并賦值為0(用于記錄遍歷的次數(shù))；
             */
            int var12 = 0;
            while(true) {
                /**
                 * 進入循環(huán)，遍歷鏈表中的元素，當(dāng)發(fā)現(xiàn)某個元素的next為null時，
                 * 說明該元素為鏈表中最后一個元素，此時將鏈表的next指向新的Node節(jié)點
                 */
                if ((var10 = ((HashMap.Node)var7).next) == null) {
                    ((HashMap.Node)var7).next = this.newNode(var1, var2, var3, (HashMap.Node)null);
                    // 如果鏈表的長度大于或者等于8(var12是從0開始的)，將鏈表轉(zhuǎn)化成紅黑樹(具體實現(xiàn)在treeifyBin方法中)
                    if (var12 >= 7) {
                        this.treeifyBin(var6, var1);
                    }
                    break;
                }
                // 遍歷過程中若發(fā)現(xiàn)當(dāng)前元素的hash值和var1相同并且key也和var2相同，會跳出當(dāng)前循環(huán)，并將value更新
                if (((HashMap.Node)var10).hash == var1 && ((var11 = ((HashMap.Node)var10).key) == var2 || var2 != null && var2.equals(var11))) {
                    break;
                }
                var7 = var10;
                ++var12;
            }
        }
        // 對已經(jīng)存在的key對應(yīng)的value進行更新
        if (var10 != null) {
            Object var13 = ((HashMap.Node)var10).value;
            if (!var4 || var13 == null) {
                ((HashMap.Node)var10).value = var3;
            }
            this.afterNodeAccess((HashMap.Node)var10);
            return var13;
        }
    }
    ++this.modCount;
    // 如果當(dāng)前集合的大小大于臨界值threshold，那么就調(diào)用resize()方法重新擴容
    if (++this.size > this.threshold) {
        this.resize();
    }
    this.afterNodeInsertion(var5);
    return null;
}

以上，就是HashMap在put數(shù)據(jù)的時候的實現(xiàn)原理，用一張圖概括如下：

hashput.png

2.get(Object var1)：根據(jù)key值從集合中獲取value

/**
 * 方法內(nèi)部創(chuàng)建一個Node類型臨時變量，然后調(diào)用getNode方法獲取對應(yīng)的Node對象；
 * 如果Node對象為空直接返回null，反之返回Node的value
 */
public V get(Object var1) {
    HashMap.Node var2;
    return (var2 = this.getNode(hash(var1), var1)) == null ? null : var2.value;
}

/**
 * 根據(jù)var1(get方法中傳入的key的hash值)和var2(get方法中傳入的key)來返回一個Node對象
 */
final HashMap.Node<K, V> getNode(int var1, Object var2) {
    // 首先，創(chuàng)建三個臨時變量var3(指向table)，var4(指向var3[var6 - 1 & var1])，var6(table的length)；
    HashMap.Node[] var3;
    HashMap.Node var4;
    int var6;
    // 當(dāng)table不為空并且table的長度大于0時，判斷var3[var6 - 1 & var1]是否為空(這里和put的時候插入的索引運算規(guī)則保持一致)
    if ((var3 = this.table) != null && (var6 = var3.length) > 0 && (var4 = var3[var6 - 1 & var1]) != null) {
        // 當(dāng)var4的hash值和key與入?yún)⒌膆ash值和key都相等時，直接返回var4
        Object var7;
        if (var4.hash == var1 && ((var7 = var4.key) == var2 || var2 != null && var2.equals(var7))) {
            return var4;
        }
        // 遍歷鏈表
        HashMap.Node var5;
        if ((var5 = var4.next) != null) {
            // 如果為紅黑樹類型，就通過getTreeNode方法獲取對應(yīng)的TreeNode
            if (var4 instanceof HashMap.TreeNode) {
                return ((HashMap.TreeNode)var4).getTreeNode(var1, var2);
            }
            // 不是紅黑樹，就為鏈表，遍歷鏈表，當(dāng)元素的hash值和key值與傳入的相等時返回對應(yīng)的Node
            do {
                if (var5.hash == var1 && ((var7 = var5.key) == var2 || var2 != null && var2.equals(var7))) {
                    return var5;
                }
            } while((var5 = var5.next) != null);
        }
    }
    return null;
}

其實，在把put方法讀懂之后，get方法理解起來特別容易了，一個存，一個取，取的時候按照存時的規(guī)則去取就可以了。
3.clear()：清空集合數(shù)據(jù)的方法

/**
 * 方法內(nèi)其實就做了兩件事，一個是將集合的size置為0，另一個就是遍歷table，將里面的元素全部置為null
 */
public void clear() {
    ++this.modCount;
    HashMap.Node[] var1;
    if ((var1 = this.table) != null && this.size > 0) {
        this.size = 0;
        for(int var2 = 0; var2 < var1.length; ++var2) {
            var1[var2] = null;
        }
    }
}

4.containsKey(Object var1):判斷集合中是否存在var1這個key

/**
 * 方法內(nèi)部也是調(diào)用了getNode方法，只要getNode方法返回不為空，就說明已經(jīng)存在這個key值了
 */
public boolean containsKey(Object var1) {
    return this.getNode(hash(var1), var1) != null;
}

還有幾個常用的方法，比如remove(Object var1)，containsValue(Object var1)等，其內(nèi)部的實現(xiàn)其實都是調(diào)用上面講解過的幾個方法，只要把上面的put方法能真正的讀懂，其他的方法相信你肯定也能明白。

5.重量級方法resize()：
此函數(shù)有兩種調(diào)用時機：1.初始化操作(put操作如果table為null時) 2.當(dāng)前數(shù)組容量過小時，需擴容操作。

final HashMap.Node<K, V>[] resize() {
        HashMap.Node[] var1 = this.table; // 創(chuàng)建var1并指向當(dāng)前數(shù)組table
        int var2 = var1 == null ? 0 : var1.length; // 創(chuàng)建var2使其等于table的長度
        int var3 = this.threshold; // 創(chuàng)建var3使其等于擴容前的臨界值
        int var5 = 0;
        int var4;
        if (var2 > 0) { // 當(dāng)前table長度大于0
            if (var2 >= 1073741824) {
                // 如果table的長度大于最大容量，那么將threshold置為2147483647，返回當(dāng)前table，并未做擴容操作
                this.threshold = 2147483647;
                return var1;
            }
            // 如果table長度的2倍小于最大容量并且table的長度大于初始的容量16時，進行擴容操作，擴大為原來的2倍(移位運算自行科普)。
            if ((var4 = var2 << 1) < 1073741824 && var2 >= 16) {
                var5 = var3 << 1; // 新的臨界值變?yōu)橹暗?倍
            }
        } else if (var3 > 0) { // 此時老的臨界值已被設(shè)置，table還為null
            var4 = var3; // 讓新的table數(shù)組的容量直接等于老的的臨界值
        } else { // 此時臨界值未被設(shè)置，table也為null
            var4 = 16; // 新的table數(shù)組的容量設(shè)置成默認值16
            var5 = 12; // 新的臨界值設(shè)置為12(16 * 0.75)
        }
        // 如果臨界值為0，重新計算臨界值的大小
        if (var5 == 0) {
            float var6 = (float)var4 * this.loadFactor;
            var5 = var4 < 1073741824 && var6 < 1.07374182E9F ? (int)var6 : 2147483647;
        }
        this.threshold = var5; // 將最終得到的臨界值大小賦值給threshold
        // 創(chuàng)建新的Node類型數(shù)組并讓table指向剛創(chuàng)建的數(shù)組var14(新的table數(shù)組)
        HashMap.Node[] var14 = (HashMap.Node[])(new HashMap.Node[var4]);
        this.table = var14;
        if (var1 != null) {
            // 把之前的table中的元素一個個的移動到新的table中去(for循環(huán)中的移動邏輯這里就不闡述了)
            for(int var7 = 0; var7 < var2; ++var7) {
                HashMap.Node var8;
                if ((var8 = var1[var7]) != null) {
                    var1[var7] = null;
                    if (var8.next == null) {
                        var14[var8.hash & var4 - 1] = var8;
                    } else if (var8 instanceof HashMap.TreeNode) {
                        ((HashMap.TreeNode)var8).split(this, var14, var7, var2);
                    } else {
                        HashMap.Node var9 = null;
                        HashMap.Node var10 = null;
                        HashMap.Node var11 = null;
                        HashMap.Node var12 = null;
                        HashMap.Node var13;
                        do {
                            var13 = var8.next;
                            if ((var8.hash & var2) == 0) {
                                if (var10 == null) {
                                    var9 = var8;
                                } else {
                                    var10.next = var8;
                                }
                                var10 = var8;
                            } else {
                                if (var12 == null) {
                                    var11 = var8;
                                } else {
                                    var12.next = var8;
                                }
                                var12 = var8;
                            }
                            var8 = var13;
                        } while(var13 != null);

                        if (var10 != null) {
                            var10.next = null;
                            var14[var7] = var9;
                        }
                        if (var12 != null) {
                            var12.next = null;
                            var14[var7 + var2] = var11;
                        }
                    }
                }
            }
        }
        return var14;
    }

關(guān)于擴容的邏輯確實有些復(fù)雜，方法本身也很長，但其實靜下心來一步一步的看，也是可以看懂的。

總結(jié)

以上，通過閱讀源碼對HashMap有了更深入一層的了解，其實關(guān)于HashMap還有很多需要掌握的知識點的，譬如HashMap是否是線程安全的，它的key是否可以為其他類型，它的key是否可以為null以及它的value是否可以為null等等。單純就上面講到的方法來說，我們還需要掌握java的異或，移位，邏輯運算符操作，以及鏈表和紅黑樹的知識點。所以，個人認為，一個小小的HashMap還是很考驗一個人的水平的，因此真的有必要好好掌握以下。

寫在最后

PS：沒有啥太深的技術(shù)功底，只能憑自己的理解再參考一些前輩的文章，有寫的不正確的地方還望指出。