摘要：注意這里我說的是一般情況下，因為哈希算法需要兼顧性能與準確性，是有一定概率出現重復的情況的。哈希算法實際上是數學家和計算機基礎科學家研究的領域。

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

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

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

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

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

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

示例:

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

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

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

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

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

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

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

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

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

注：以下內容基于JDK 1.8進行講解

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

什么是哈希表呢？

哈希表是根據鍵（Key）而直接訪問在內存存儲位置的數據結構

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

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

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

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

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

/**
     * 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;
    }

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

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

注意這里我說的是一般情況下，因為哈希算法需要兼顧性能與準確性，是有一定概率出現重復的情況的。我們可以看到上文getNode方法，有一段遍歷的代碼：

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

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

Tips：

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

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

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

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

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

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

為了更好地理解 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;
}

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

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

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

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

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

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