首先，我们知道 HashMap 的底层实现是开放地址法 + 链地址法的方式来实现。
image
即数组 + 链表的实现方式，通过计算哈希值，找到数组对应的位置，如果已存在元素，就加到这个位置的链表上。在 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
网友评论