摘要：注意這里我說的是一般情況下，因為哈希算法需要兼顧性能與準確性，是有一定概率出現(xiàn)重復(fù)的情況的。哈希算法實際上是數(shù)學(xué)家和計算機基礎(chǔ)科學(xué)家研究的領(lǐng)域。

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

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

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

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

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

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

示例:

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

因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

初看這道題的時候，我當然是使用最簡單的array遍歷來解決了：

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

這個解法在官方稱為“暴力法”。

通過這個“暴力法”我們可以看到里面有個我們在編程中經(jīng)常遇到的一個場景：檢查數(shù)組中是否存在某元素。

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

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

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

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

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

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

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

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

什么是哈希表呢？

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

維基上的解釋比較抽象。我們可以把一張哈希表理解成一個數(shù)組。數(shù)組中可以存儲Object，當我們要保存一個Object到數(shù)組中時，我們通過一定的算法，計算出來Object的哈希值（Hash Code），然后把哈希值作為下標，Object作為值保存到數(shù)組中。我們就得到了一張哈希表。

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

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

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

我們查看 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;
    }

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

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

注意這里我說的是一般情況下，因為哈希算法需要兼顧性能與準確性，是有一定概率出現(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);

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

Tips：

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

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

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

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

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

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

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

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 再疊加最后返回，因此，每個不同的字符串，返回的 hashCode 肯定不一樣。那么為什么使用 31 呢？

在名著 《Effective Java》第 42 頁就有對 hashCode 為什么采用 31 做了說明：

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

可以看到，使用 31 最主要的還是為了性能。當然用 63 也可以。但是 63 的溢出風險就更大了。那么15 呢？仔細想想也可以。

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

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