摘要：注意這里我說(shuō)的是一般情況下，因?yàn)楣Ｋ惴ㄐ枰骖櫺阅芘c準(zhǔn)確性，是有一定概率出現(xiàn)重復(fù)的情況的。哈希算法實(shí)際上是數(shù)學(xué)家和計(jì)算機(jī)基礎(chǔ)科學(xué)家研究的領(lǐng)域。

做了幾年 CRUD 工程師，深感自己的計(jì)算機(jī)基礎(chǔ)薄弱，在看了幾篇大牛的分享文章之后，發(fā)現(xiàn)很多人都是通過(guò)刷 LeetCode 來(lái)提高自己的算法水平。的確，通過(guò)分析解決實(shí)際的問(wèn)題，比自己潛心研究書(shū)本效率還是要高一些。

一直以來(lái)遇到底層自己無(wú)法解決的問(wèn)題，都是通過(guò)在 Google、GitHub 上搜索組件、博客來(lái)進(jìn)行解決。這樣雖然挺快，但是也讓自己成為了一個(gè)“Ctrl+C/Ctrl+V”程序員。從來(lái)不花時(shí)間思考技術(shù)的內(nèi)在原理。

直到我刷了 Leetcode 第一道題目 Two Sum，接觸到了 HashMap 的妙用，才激發(fā)起我去了解 HashMap 原理的興趣。

TwoSum 是 Leetcode 中的第一道題，題干如下：

給定一個(gè)整數(shù)數(shù)組nums和一個(gè)目標(biāo)值target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

初看這道題的時(shí)候，我當(dāng)然是使用最簡(jiǎn)單的array遍歷來(lái)解決了：

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

這個(gè)解法在官方稱為“暴力法”。

通過(guò)這個(gè)“暴力法”我們可以看到里面有個(gè)我們?cè)诰幊讨薪?jīng)常遇到的一個(gè)場(chǎng)景：檢查數(shù)組中是否存在某元素。

官方的解析中提到，哈希表可以保持?jǐn)?shù)組中每個(gè)元素與其索引相互對(duì)應(yīng)，所以如果我們使用哈希表來(lái)解決這個(gè)問(wèn)題，可以有效地降低算法的時(shí)間復(fù)雜度。（不了解哈希表和時(shí)間復(fù)雜度的的朋友別急，下文會(huì)詳細(xì)說(shuō)明）

使用哈希表的解法是這樣的：

public int[] twoSum(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

即使我們不是很會(huì)算時(shí)間復(fù)雜度，也能夠明顯看到，原來(lái)的雙重循環(huán)，在哈希表解法里，變成了單重循環(huán)，代碼的效率很明顯提升了。

但是令人好奇的是map.containsKey()到底是用了什么樣的魔力，實(shí)現(xiàn)快速判斷元素complement是否存在呢？

這里就要引出本篇文章的主角 —— HashMap。

注：以下內(nèi)容基于JDK 1.8進(jìn)行講解

在了解map.containsKey()這個(gè)方法之前，我們還是得補(bǔ)習(xí)一下基礎(chǔ)，畢竟筆者在看到這里得時(shí)候，對(duì)于哈希表、哈希值得概念也都忘得一干二凈了。

什么是哈希表呢？

哈希表是根據(jù)鍵（Key）而直接訪問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)

維基上的解釋比較抽象。我們可以把一張哈希表理解成一個(gè)數(shù)組。數(shù)組中可以存儲(chǔ)Object，當(dāng)我們要保存一個(gè)Object到數(shù)組中時(shí)，我們通過(guò)一定的算法，計(jì)算出來(lái)Object的哈希值（Hash Code），然后把哈希值作為下標(biāo)，Object作為值保存到數(shù)組中。我們就得到了一張哈希表。

看到這里，我們前文中說(shuō)到的哈希表可以保持?jǐn)?shù)組中每個(gè)元素與其索引相互對(duì)應(yīng)，應(yīng)該就很好理解了吧。

回到 Leetcode 的代示例，map.containsKey()中顯然是通過(guò)獲取 Key 的哈希值，然后判斷哈希值是否存在，間接判斷 Key 是否已經(jīng)存在的。

到了這里，如果我們僅僅是想要能夠明白 HashMap 的使用原理，基本上已經(jīng)足夠了。但是相信有不少朋友對(duì)它的哈希算法感興趣。下面我詳細(xì)解釋一下。

我們查看 JDK 的源碼，可以看到map.containsKey()中最關(guān)鍵的代碼是這段：

/**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

一上來(lái)看不懂沒(méi)關(guān)系，其實(shí)這段代碼最關(guān)鍵的部分就只有這一句：first = tab[(n - 1) & hash]) != null。

其中tab是 HashMap 的 Node 數(shù)組（每個(gè) Node 是一個(gè) Key&value 鍵值對(duì)，用來(lái)存在 HashMap的數(shù)據(jù)），這里對(duì)數(shù)組的長(zhǎng)度n和hash值，做&運(yùn)算（至于為什么要進(jìn)行這樣的&運(yùn)算，是與 HashMap 的哈希算法有關(guān)的，具體要看java.util.HashMap.hash()這個(gè)方法，哈希算法是數(shù)學(xué)家和計(jì)算機(jī)基礎(chǔ)科學(xué)家研究的領(lǐng)域，這里不做深入研究），得到一個(gè)數(shù)組下標(biāo)，這個(gè)下標(biāo)對(duì)應(yīng)的數(shù)組數(shù)據(jù)，一般情況下就是我們要找的節(jié)點(diǎn)。

注意這里我說(shuō)的是一般情況下，因?yàn)楣Ｋ惴ㄐ枰骖櫺阅芘c準(zhǔn)確性，是有一定概率出現(xiàn)重復(fù)的情況的。我們可以看到上文getNode方法，有一段遍歷的代碼：

do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);

就是為了處理極端情況下哈希算法得到的哈希值沒(méi)有命中，需要進(jìn)行遍歷的情況。在這個(gè)時(shí)候，時(shí)間復(fù)雜度是O(n)，而在這種極端情況以外，時(shí)間復(fù)雜度是O(1)，這也就是map.containsKey()效率比遍歷高的奧秘。

Tips：

看到這里，如果有人問(wèn)你：兩個(gè)對(duì)象，其哈希值（hash code）相等，他們一定是同一個(gè)對(duì)象嗎？相信你一定有答案了。（如果兩個(gè)對(duì)象不同，但哈希值相等，這種情況叫哈希沖突）

組合兩個(gè) List 的數(shù)據(jù)是編程中常見(jiàn)的一個(gè)場(chǎng)景。為什么不直接使用 SQL JOIN 呢？在當(dāng)下流行的微服務(wù)架構(gòu)下，每個(gè)微服務(wù)可能有一個(gè)多帶帶的數(shù)據(jù)庫(kù)，各個(gè)微服務(wù)之間的數(shù)據(jù)庫(kù)是不允許進(jìn)行 SQL JOIN 的。例如：一個(gè)訂單查詢的需求，我們需要查詢訂單中心，用戶中心，支付中心，合并各個(gè)中心返回的結(jié)果形成一個(gè)表單。

一個(gè)高效實(shí)現(xiàn) SQL JOIN 的方法就是使用 HashMap，這里我更新在了另一篇文章里，歡迎各位點(diǎn)擊查看：HashMap 常見(jiàn)應(yīng)用：實(shí)現(xiàn) SQL JOIN

通過(guò)前文我們可以發(fā)現(xiàn)，HashMap 之所以能夠高效地根據(jù)元素找到其索引，是借助了哈希表的魔力，而哈希算法是 哈希表的靈魂。

哈希算法實(shí)際上是數(shù)學(xué)家和計(jì)算機(jī)基礎(chǔ)科學(xué)家研究的領(lǐng)域。對(duì)于我們普通程序員來(lái)說(shuō)，并不需要研究太透徹。但是如果我們能夠搞清楚其實(shí)現(xiàn)原理，相信對(duì)于今后的程序涉及大有裨益。

按筆者的理解，哈希算法是為了給對(duì)象生成一個(gè)盡可能獨(dú)特的Code，以方便內(nèi)存尋址。此外其作為一個(gè)底層的算法，需要同時(shí)兼顧性能與準(zhǔn)確性。

為了更好地理解 hash 算法，我們拿java.lang.String的hash 算法來(lái)舉例。

java.lang.String hashCode方法：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

相信這段代碼大家應(yīng)該都看得懂，使用 String 的 char 數(shù)組的數(shù)字每次乘以 31 再疊加最后返回，因此，每個(gè)不同的字符串，返回的 hashCode 肯定不一樣。那么為什么使用 31 呢？

在名著 《Effective Java》第 42 頁(yè)就有對(duì) hashCode 為什么采用 31 做了說(shuō)明：

之所以使用 31， 是因?yàn)樗且粋€(gè)奇素?cái)?shù)。如果乘數(shù)是偶數(shù)，并且乘法溢出的話，信息就會(huì)丟失，因?yàn)榕c2相乘等價(jià)于移位運(yùn)算（低位補(bǔ)0）。使用素?cái)?shù)的好處并不很明顯，但是習(xí)慣上使用素?cái)?shù)來(lái)計(jì)算散列結(jié)果。 31 有個(gè)很好的性能，即用移位和減法來(lái)代替乘法，可以得到更好的性能： 31 * i == (i << 5） - i， 現(xiàn)代的 VM 可以自動(dòng)完成這種優(yōu)化。這個(gè)公式可以很簡(jiǎn)單的推導(dǎo)出來(lái)。

可以看到，使用 31 最主要的還是為了性能。當(dāng)然用 63 也可以。但是 63 的溢出風(fēng)險(xiǎn)就更大了。那么15 呢？仔細(xì)想想也可以。

在《Effective Java》也說(shuō)道：編寫(xiě)這種散列函數(shù)是個(gè)研究課題，最好留給數(shù)學(xué)家和理論方面的計(jì)算機(jī)科學(xué)家來(lái)完成。我們此次最重要的是知道了為什么使用 31。

java.util.HashMap hash 算法實(shí)現(xiàn)原理相對(duì)復(fù)雜一些，這篇文章：深入理解 hashcode 和 hash 算法，講得非常好，建議大家感興趣的話通篇閱讀。