217：JavaHashMap的中key的哈希值是如何计算的，为何这么计算？

coding

首先，我们知道 HashMap 的底层实现是开放地址法 + 链地址法的方式来实现。

即数组 + 链表的实现方式，通过计算哈希值，找到数组对应的位置，如果已存在元素，就加到这个位置的链表上。在 Java 8 之后，链表过长还会转化为红黑树。

这个数组并不是一开始就很大，而是随着 HashMap 里面的值变多，达到 LoadFactor 的界限之后，就会扩容。刚开始的数组很小，默认只有 16。

这个数组大小一定是 2 的 n 次方，因为找到数组对应的位置需要通过取余计算，取余计算是一个很耗费性能的计算，而对 2 的 n 次方取余就是对 2 的 n 次方减一取与运算。所以保持数组大小为 2 的 n 次方，这样就可以保证计算位置高效。

那么这个哈希值究竟是怎么计算的呢？假设就是用 Key 的哈希值直接计算。假设有如下两个 key，哈希值分别是：

key1:

0000 0000 0010 1111 1001 0000 0110 1101

key2:

0000 0000 0010 0000 1001 0000 0110 1101

如果直接使用数组默认大小，取余之后 key1 与 key2 就会到数组同一个下标。其实 key1 和 key2 的高位是不一样的。

由于数组是从小到达扩容的，为了优化高位被忽略这个问题，HashMap 源码中对于计算哈希值做了优化，采用高位16位组成的数字与源哈希值取异或而生成的哈希值作为用来计算 HashMap 的数组位置的哈希值：

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

为什么要用异或？首先，对于一个数字，转换成二进制之后，其中为的 1 的位置代表这个数字的特性.对于异或运算，如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。0与0异或是0，0与1异或是1，这样相当于让高位的特性在低位得以体现，所以采用这种算法，减少碰撞。

微信搜索“我的编程喵”关注公众号，每日一刷，轻松提升技术，斩获各种offer：