背景

文章不聊HashMap的源码实现，主要聊一聊几个细节的问题。

HashMap处理冲突的方式是通过链表法来解决冲突，其核心在于散列函数的均匀随机。因此我们就来看一看HashMap是怎样计算index的。

源码很直接：

// capacity等于HashMap的length
int index = hash(key) & (capacity - 1)

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

上述代码就是HashMap计算index的方式。那么这里展开两个问题：

1. hash()之后的值，为什么要& (capacity - 1)
2. hash()这个函数是为了什么？

问题1：

首先，我们需要得到一个小于length的index。一个比较简单的方式就是对当前的length进行取余，也就是hash(key) % (capacity)

这里有一个优化，那就是把%换成&。其原理就是：a%(2^n) == a&(2^n-1)。

这也是为什么length需要是2的倍数的原因

因此也就变成了hash(key) & (capacity - 1)

补充：为什么a%(2^n) == a&(2^n-1)

通过一个例子来看一下：18 % 16 = 2

image image

• 大于16的1肯定是16的整数倍，可以直接约掉
• 剩下&出来的值就是余数

问题2：

hash()函数一共做了两件事：

1. 将hashCode右移16位
2. 将第一步的结果与hashCode进行一个异或

为什么做这两件事，咱们来展开一下。先看一种case，假设我们有一个对象，hashCode为下图：

image

这个hashCode有个特点：有几位都是0

如果我们直接用这个HashCode与(capacity - 1)进行与(&)操作，如果与的HashCode低位都是0，那么无论(capacity - 1)是什么，得到的值永远是0。

因此会出现：当满足这种case，无论怎么计算index都是0。一个稳定复现的冲突。

所以我们需要考虑如何解决这种情况。这里我们套用HashMap的方案“也就是右移，然后异或。

这里就会发现得到的index的确不是0了：

image

其原理也比较好理解：

先右移16位，那么原HashCode的低16位就变成了高的16位，高16位全部变成0。

将右移后的结果与原HashCode进行异或，得到的结果：高16位还是原样，低16位进行了混合。因此之前为0的低位，变得不一定为0了。

套用HashMap的方案，我们的确解决了低位为0的情况

那么问题来了，如果高位是0怎么办？

怎么办？不需要办呀...因为我们通过&求index，先从低位计算。 如果我们index需要计算高位，那就意味着我们的HashMap已经非常非常巨大了...