HashMap解读

• HashMap的数组长度n为啥要取2的整数幂?

  • 当n为2的整数幂时，n % hash = （n-1）& hash。可以使用位运算，更快速的计算出数组下标。
    当n = 16是，HashMap计算数组索引的过程如下：
    n-1=15， 对应的二进制为 00000000 00000000 00000000 00001111
    hash值=100，对应的二进制为 00000000 00000000 00000000 01100100
    (n-1）& hash, 对应的二进制为 00000000 00000000 00000000 00000100 = 4
    100 % 16 = 4，通过位运算得到的值的就是取模后的值。

• hash方法为啥要做扰动?

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

因为HashMap是通过上面的位运算计算数组下标的，可以看到hash值的高位都被归零，只有低位参与了运算，为了让计算出来的下标更均匀，尽量的减少碰撞，所以通过扰动函数将高位的值也反应到低位的运算上。原理如下：
例如 h = key.hashCode() 对应的二进制编码为 00000000 00110110 01000100 10010010
h >>> 16 对应的二进制编码为 00000000 00000000 00000000 00110110
h ^ (h >>> 16) 对应的二进制编码为 00000000 00110110 01000100 10110110
通过移位再或运算，就将默认的hashCode的高位和低位都反映到了低位上，扰动之后得到的hash再进行下标计算，得到的值相等来说就更随机，从而尽量减少碰撞。

• HashMap resize方法

  • 负载因子loadFactor，DEFAULT_LOAD_FACTOR = 0.75
  • 数组的大小（容量） capacity（2的倍数），MAXIMUM_CAPACITY = 1 << 30
  • threshold，map中能存放的元素最大值。 threshold = capacity * loadFactor
  • 扩容机制
    当size > threshold时，如果capacity<MAXIMUM_CAPACITY, 会将capacity扩大2倍，相应的threshold也会扩大2倍；如果capacity >= MAXIMUM_CAPACITY 时，不扩容，但会将threshold设置为Integer.MAX_VALUE；然后将旧数组中的数据，拷贝到新的数组中。

• HashMap put方法
  

  image.png