摘要：掌握的實現(xiàn)原理，已經(jīng)是程序員的基礎(chǔ)操作了。后記這次主要是理解了一下的實現(xiàn)原理，特別重點寫了很多關(guān)于散列函數(shù)的理解，并沒有按照源碼一行行的去理解。之前看的時候?qū)ι⒘泻瘮?shù)都是跳過去的，只知道是用來計算鍵的，不知道里面的原理。

HashMap是Java中常用的Map接口的實現(xiàn)類，因為在日常工作中非常頻繁的出現(xiàn)，所以在大部分的Java面試中都會問幾個關(guān)于HashMap的問題。掌握HashMap的實現(xiàn)原理，已經(jīng)是Java程序員的基礎(chǔ)操作了。

映射（Map）是一種用于存放鍵/值對的數(shù)據(jù)結(jié)構(gòu)。如果提供了鍵，就能直接找到相對應(yīng)的值。HashMap（哈希映射）是Map接口的一個實現(xiàn)類，主要使用哈希來實現(xiàn)鍵與值的映射。

定義。映射是一種用于存放鍵/值對的數(shù)據(jù)結(jié)構(gòu)，主要支持兩種操作：插入（put），即將一組新的鍵值對存入映射中；查找（get），即根據(jù)給定的鍵得到相應(yīng)的值。

HashMap的底層是用散列表實現(xiàn)的，散列表是一種用數(shù)組來存儲鍵值對的數(shù)據(jù)結(jié)構(gòu)，它使用一個散列函數(shù)將鍵轉(zhuǎn)換成數(shù)組的一個索引然后存儲值。不過會有不同的鍵被散列成同個索引的情況出現(xiàn)，這叫做碰撞沖突。HashMap用拉鏈法來解決這個問題，即散列表數(shù)組中的每個元素都指向一條鏈表，鏈表中的每個節(jié)點都存儲了被散列到這個索引的鍵值對。

根據(jù)散列表的定義我們知道，想要弄清楚HashMap的實現(xiàn)，我們首先需要知道HashMap的散列函數(shù)是怎么實現(xiàn)的，即HashMap是如何將一個鍵映射到數(shù)組的索引的。

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

上面就是HashMap的散列函數(shù)源碼了，可以看到如果鍵為null的話它的索引固定為0，即HashMap是支持使用null作為鍵的。如果鍵不為null就用Java對象都有的hashCode方法獲得一個哈希值，并將這個哈希值的低16位與高16位做異或處理，高16位不變。

這里有個問題就是為什么不直接用鍵的hashcode，而要將hashcode的低16位與高16位做異或處理？這里是因為有三個前提：

int有32位

HashMap的數(shù)組長度都是2的冪

獲取數(shù)組索引需要將鍵的哈希值和數(shù)組長度-1做一個與操作（&）得到，即tab[(n - 1) & hash]

首先因為HashMap的數(shù)組長度都是2的冪，（n - 1）的高16位都是0，所以只有鍵的低16位參與索引運算。如果直接用鍵的hashcode的話，就會有很多碰撞沖突，所以用這種方法使得hashcoede的高16位也參與到索引的運算中來。下面是字符串“1234”在數(shù)組長度為16的索引運算過程：

public static void main(String[] args) {
    int hashcode = "1234".hashCode();
    System.out.println(Integer.toBinaryString(hashcode));
    // 輸出為 10111 0000100001000010
    System.out.println(Integer.toBinaryString(hashcode >>> 16));
    // 輸出為 10111
    System.out.println(Integer.toBinaryString(hashcode ^ (hashcode >>> 16)));
    // 輸出為 10111 0000100001010101
    System.out.println(Integer.toBinaryString(16 - 1));
    // 輸出為 1111
    System.out.println(Integer.toBinaryString((16 - 1) & (hashcode ^ (hashcode >>> 16))));
    // 輸出為 101
}

雖然HashMap對散列函數(shù)做了很多優(yōu)化，但是碰撞沖突還是不可避免的會出現(xiàn)。為了解決這個問題HashMap使用了拉鏈法，使用鏈表來存儲碰撞沖突的鍵值對。并在JDK 8中進行了優(yōu)化，當(dāng)鏈表長度到達某個指定值時HashMap會自動將鏈表優(yōu)化為紅黑樹。頻繁碰撞沖突還可能是因為數(shù)組長度不夠的原因，HashMap還會根據(jù)鍵值對的數(shù)量進行自動擴容。

在講HashMap的自動擴容前，先來看看HashMap有哪些相關(guān)的屬性：

Node[] table; 存放鍵值對的數(shù)組

int size; 已存放鍵值對的數(shù)量

int threshold; 當(dāng)鍵值對的數(shù)量等于這個值的時候HashMap將進行擴容，值等于數(shù)組長度 * loadFactor

final float loadFactor; 負載因子，用于計算threshold的值，默認值為0.75

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 數(shù)組長度的默認值16

根據(jù)這些屬性可以知道，HashMap的自動擴容會根據(jù)數(shù)組長度和負載因子的積得到一個threshold的值，當(dāng)鍵值對的數(shù)量等于threshold時就會開始擴容，下面是擴容的源碼。大概過程是新建一個長度為舊數(shù)組兩倍的新數(shù)組，并將原有的鍵值對都重新映射到新數(shù)組上。

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; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            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;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

這次主要是理解了一下HashMap的實現(xiàn)原理，特別重點寫了很多關(guān)于散列函數(shù)的理解，并沒有按照源碼一行行的去理解。之所以這樣是因為寫這篇的動力主要來源于面試……而面試則只要講下原理就可以了，并不需要把源碼背下來。之前看HashMap的時候?qū)ι⒘泻瘮?shù)都是跳過去的，只知道是用來計算鍵的hash，不知道里面的原理。其實還有鏈表轉(zhuǎn)紅黑樹的地方?jīng)]有弄清楚，主要是紅黑樹不怎么理解，基礎(chǔ)的重要性體現(xiàn)了出來。

我的博客