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

HashMap是Java中常用的Map接口的實(shí)現(xiàn)類，因?yàn)樵谌粘９ぷ髦蟹浅ｎl繁的出現(xiàn)，所以在大部分的Java面試中都會(huì)問幾個(gè)關(guān)于HashMap的問題。掌握HashMap的實(shí)現(xiàn)原理，已經(jīng)是Java程序員的基礎(chǔ)操作了。

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

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

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

根據(jù)散列表的定義我們知道，想要弄清楚HashMap的實(shí)現(xiàn)，我們首先需要知道HashMap的散列函數(shù)是怎么實(shí)現(xiàn)的，即HashMap是如何將一個(gè)鍵映射到數(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方法獲得一個(gè)哈希值，并將這個(gè)哈希值的低16位與高16位做異或處理，高16位不變。

這里有個(gè)問題就是為什么不直接用鍵的hashcode，而要將hashcode的低16位與高16位做異或處理？這里是因?yàn)橛腥齻€(gè)前提：

int有32位

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

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

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

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)化，但是碰撞沖突還是不可避免的會(huì)出現(xiàn)。為了解決這個(gè)問題HashMap使用了拉鏈法，使用鏈表來存儲(chǔ)碰撞沖突的鍵值對。并在JDK 8中進(jìn)行了優(yōu)化，當(dāng)鏈表長度到達(dá)某個(gè)指定值時(shí)HashMap會(huì)自動(dòng)將鏈表優(yōu)化為紅黑樹。頻繁碰撞沖突還可能是因?yàn)閿?shù)組長度不夠的原因，HashMap還會(huì)根據(jù)鍵值對的數(shù)量進(jìn)行自動(dòng)擴(kuò)容。

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

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

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

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

final float loadFactor; 負(fù)載因子，用于計(jì)算threshold的值，默認(rèn)值為0.75

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

根據(jù)這些屬性可以知道，HashMap的自動(dòng)擴(kuò)容會(huì)根據(jù)數(shù)組長度和負(fù)載因子的積得到一個(gè)threshold的值，當(dāng)鍵值對的數(shù)量等于threshold時(shí)就會(huì)開始擴(kuò)容，下面是擴(kuò)容的源碼。大概過程是新建一個(gè)長度為舊數(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的實(shí)現(xiàn)原理，特別重點(diǎn)寫了很多關(guān)于散列函數(shù)的理解，并沒有按照源碼一行行的去理解。之所以這樣是因?yàn)閷戇@篇的動(dòng)力主要來源于面試……而面試則只要講下原理就可以了，并不需要把源碼背下來。之前看HashMap的時(shí)候?qū)ι⒘泻瘮?shù)都是跳過去的，只知道是用來計(jì)算鍵的hash，不知道里面的原理。其實(shí)還有鏈表轉(zhuǎn)紅黑樹的地方?jīng)]有弄清楚，主要是紅黑樹不怎么理解，基礎(chǔ)的重要性體現(xiàn)了出來。

我的博客