HashMap 浅析 —— LeetCode Two Sum 刷题总结

背景

做了几年 CRUD 工程师，深感自己的计算机基础薄弱，在看了几篇大牛的分享文章之后，发现很多人都是通过刷 LeetCode 来提高自己的算法水平。的确，通过分析解决实际的问题，比自己潜心研究书本效率还是要高一些。

一直以来遇到底层自己无法解决的问题，都是通过在 Google、GitHub 上搜索组件、博客来进行解决。这样虽然挺快，但是也让自己成为了一个“Ctrl+C/Ctrl+V”程序员。从来不花时间思考技术的内在原理。

直到我刷了 Leetcode 第一道题目 Two Sum，接触到了 HashMap 的妙用，才激发起我去了解 HashMap 原理的兴趣。

Two Sum（两数之和）

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<Integer, Integer> 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。

HashMap

注：以下内容基于 JDK 1.8 进行讲解

在了解 map.containsKey() 这个方法之前，我们还是得补习一下基础，毕竟笔者在看到这里得时候，对于哈希表、哈希值得概念也都忘得一干二净了。

什么是哈希表呢？

哈希表是根据键（Key）而直接访问在内存存储位置的数据结构

维基上的解释比较抽象。我们可以把一张哈希表理解成一个数组。数组中可以存储 Object ，当我们要保存一个 Object 到数组中时，我们通过一定的算法，计算出来 Object 的哈希值（Hash Code），然后把哈希值作为下标， Object 作为值保存到数组中。我们就得到了一张哈希表。

看到这里，我们前文中说到的 哈希表可以保持数组中每个元素与其索引相互对应 ，应该就很好理解了吧。

回到 Leetcode 的代示例， map.containsKey() 中显然是通过获取 Key 的哈希值，然后判断哈希值是否存在，间接判断 Key 是否已经存在的。

到了这里，如果我们仅仅是想要能够明白 HashMap 的使用原理，基本上已经足够了。但是相信有不少朋友对 hash 算法感兴趣。下面我详细解释一下。

map.containsKey() 解析

我们查看 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<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> 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<K,V>)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）相等，他们一定是同一个对象吗？相信你一定有答案了。（如果两个对象不同，但哈希值相等，这种情况叫哈希冲突）

哈希算法

通过前文我们可以发现，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 算法 ，讲得非常好，建议大家感兴趣的话通篇阅读。