HashMap索引与扩容那些事

一. key索引的计算

方法一：
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

上面这段代码就是hashmap中计算一个key的哈希槽过程：

1. 计算这个key的哈希值
2. 通过位运算进行取模操作 相比较与传统的通过除法取余数的计算方式，位运算的效率是远远高于除法运算的。

上面的这段代码第一眼看下来有两个迷惑的地方：

1. 为什么计算完这个key的哈希值以后，还要(h = key.hashCode()) ^ (h >>> 16),这是什么意思？
2. 要想某一个数字m,映射到一个准确长度n范围内，我们通常会使用这个数字除以这个长度范围取余数,就是m%n取模操作。为什么通过位运算h & (length-1)也能保证这个数字地落在这个长度范围内？

1.1 为什么hash算法中对key做了哈希后，还要与高16位做亦或运算

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

|              值与计算过程                |       说明            |
    11001110 11001111 11011101 00111110     a = Object.hash(key)
^   00000000 00000000 11001110 11001111     a >>> 16
------------------------------------------------
    11001110 11001111 00010011 11110001     HashMap.hash(key)

1. 计算元素索引的算法为 ：HashMap.hash(key) & (HashMap.length -1)
2. 当HashMap.length小于0000 0000 0000 0000 1111 1111 1111 1111的时候，计算元素索引的时候，由于length的高16位都是0，所以索引运算相当于只和低16位做运算
3. 假如一些key的原始哈希值，低16位相同，高16位不一样， 则在计算key索引的时候就会产生大量的冲突。
4. 为了解决上面的这种情况，怎么使低16位的hash值产生变化，于是就再和自己的高16位做一次亦或运算，于是低16位便带上了高16位的特征了。

1.2 为什么当容量n为2的n次幂，hash & (n-1) 等价于 hash%n?

1. 由于$n=2^n$， n的二进制表现形似 0000 1000或者0100 0000
2. n - 1的二进制表现形似 0000 0111或者0011 1111
3. 于是hash&(n-1)返回的二进制位肯定是在n的范围内的。

回到问题，

为什么容量n要是2的n次幂？因为当$n=2^n$时，n-1时的二进制形式保证了与运算的不溢出。

为什么hash & (n-1) 等价于 hash%n？因为n-1的二进制位全部为1了，做与运算的时候就可以看出

二.扩容计算

由于上面的哈希索引计算的位运算算法原因，要求Hashmap的容量必须为2的幂次方。 问题：于是hashmap在每次扩容的时候都必须计算出大于等于当前容量的，最近的2的幂次方作为扩容容量。 一般我们会怎么做？ 可以通过穷举2的幂次方值，从最小的值开始与容量比较大小，第一个大于等于它的值就是解。netty中的时间轮算法中就是这样子实现的

那JDK的Hashmap是如何做这件事情的，请看下面。

2.1 如何计算当前容量最近的2的n次幂

逻辑过程：

1. 因为 ：$2^n$ 二进制形似 0001 0000 都是其中的一位是1， 其他都为0。
2. 因为 ：$2^n-1$二进制形似0000 1111 n之前的位都是1， 加1时进位。
3. 所以 ：获取一个数字最近的二次幂，即可以通过先获取这个二次幂的$2^n-1$的二进制，然后再+1就是这个最近的$2^n$了

实现逻辑：

如何获取这个$2^n-1$的二进制的值呢， 实现思路就是将最高位的1复制到后面的所有的位中。

static final int tableSizeFor(int cap) {
  int n = cap -1;
  n |= n>>>1;   //将最高位的1复制1个，得到2个1
  n |= n>>>2;		//将上面得到的2个1复制，得到4个1
  n |= n>>>4;		//将上面得到的4个1复制，得到8个1
  n |= n>>>8;		//将上面得到的8个1复制，得到16个1
  n |= n>>>16;	//将上阿敏得到的16个1复制，得到32个1
  return cap
}

为什么n要用cap-1, 而不直接用cap呢， 因为这个算法里面要获取的时候大于等于原值的最近的二次幂。如果直接用cap的话， 就是获取大于原值的最近的二次幂。0000 1000, 直接使用cap计算出来就是0001 0000, 而不是原值。