深入探究HashMap二次Hash原因

1. 前言

HashMap对于Java程序员来说一定不陌生，除了平时开发会经常使用外，它也是面试官非常喜欢问的一个知识点。HashMap是哈希表的一个经典实现，底层数据结构是数组+链表，在JDK8中还引入了红黑树，以解决链表线性查找的效率问题。HashMap设计的非常优秀，源码两千多行，有很多可以拿出来讨论的点，本篇文章主要分析HashMap二次哈希的目的。

2. 哈希码的作用

首先，我们得先了解哈希码的作用是什么？HashMap底层采用数组+链表/红黑树的数据结构来存储键值对的映射关系，数组就是若干个哈希槽Solt，HashMap会通过Key算出的哈希码来计算下标Index，Index决定了键值对应该落在哪个槽里。不同的哈希码算出相同的下标Index，就会导致哈希碰撞，一旦发生哈希碰撞，HashMap的查找效率就会从O(1)退化成O(n)或者O(logn)。所以，一个好的哈希函数应该要尽可能的分散，否则就会影响到HashMap的效率。

3. 二次Hash

我们已经知道，HashMap会根据哈希码计算下标，哈希码的分散性越好，HashMap的效率也就越高。我们先看一下HashMap计算下标的过程，就知道它为啥要做二次Hash了。

static int indexFor(int h, int length) {
    return h & (length-1);
}

上面是HashMap根据二次Hash计算出的哈希码，计算键值对下标的代码，length是底层数组的长度。HashMap采用了位运算，而非我们常见的取模运算，这里你可以先略过，它俩的效果是一样的。

我们先来看看如果不做二次Hash的情况下，会出现什么问题。现在，我假设数组长度为16，那么当哈希码为5时，下标Index结果是5。

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

当哈希码为65541时，下标Index结果依然是5，不同的哈希码算出相同的下标，哈希碰撞了。

 00000000000000010000000000000101
&00000000000000000000000000001111
=00000000000000000000000000001101
=5

从这个与运算的过程，大家肯定也都发现了，就是哈希码的高位压根就没有参与运算，全部被丢弃了。不管哈希码的高位是多少，都不会影响最终Index的计算结果，因为只有低位才参与了运算，这样的哈希函数我们认为是不好的，它会带来更多的冲突，影响HashMap的效率。

如何解决这个问题呢？最简单的办法就是让高位也参与到运算，高位不一样也会导致最终的Index结果不一样，减少哈希碰撞的概率。事实上，HashMap也就是这么做的，下面是HashMap做二次Hash的源码：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap通过将哈希码的高16位与低16位进行异或运算，得到一个新的哈希码，这样就可以让高位也参与到运算，这个函数也被称作「扰动函数」。

我们用同样的哈希码，来看看经过二次Hash后的哈希码，是否会带来不一样的效果。
仍然假设数组长度为16，那么当哈希码为5时，下标Index是5，结果不变。

 0000000000000101
^0000000000000000
=0000000000000101

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

当哈希码为65541时，下标Index结果是4，竟然没有发生哈希碰撞。

 0000000000000101
^0000000000000001
=0000000000000100

 00000000000000010000000000000100
&00000000000000000000000000001111
=00000000000000000000000000000100
=4

可以看到，HashMap通过加入一个扰动函数，让原本会发生碰撞的两个哈希码，不再冲突。

4. 为啥右移16位

HashMap的扰动函数，是拿高16位和低16位做异或运算，把高位的特征和地位的特征组合起来，以此来降低哈希碰撞的概率。为啥是16位？而不是8位或24位或其它位？

根据哈希码计算下标Index的过程，大家也发现了。实际上，只有数组长度以内的低位才会参与运算。例如数组长度是16，那么只有低4位会参与计算；如果数组长度是256，那么只有低8位会参与计算；如果数组长度是65536，那么只有低16位会参与计算。HashMap取16位是一个折中的数字，绝大部分情况下，HashMap数组的长度都不会超过65536。

5. 总结

HashMap底层采用数组+链表/红黑树来存储键值对，会根据Key的哈希码来计算键值对落在数组的哪个下标。如果不同的哈希码算出相同的下标，就会导致哈希碰撞，影响HashMap的性能。HashMap要做的，就是尽量避免哈希碰撞，所以加入了扰动函数。扰动函数会将哈希码的高16位与低16位做异或运算，让高位也参与到下标的计算过程中来，从而影响最终下标的计算结果，减少哈希碰撞的概率。至于为啥是16位，这是因为哪些位会参与到下标的计算，取决于HashMap数组的长度，在绝大部分情况下，数组的长度都不会超过65536，16位是一个折中的数字。