HashMap 中的 hash 原理

HashMap 内部是一个散列表（数组？），存放时取 key 的 hashCode 作为 index 位，如果出现了 hash 冲突，则此 index 位以链表（length = 8 时转化为 红黑树）形式存放。

• hashCode 为 int 型，默认为 -2147483648 到 2147483648，内存无法接受这么长的散列表，故使用 node 的 length - 1 做 & 运算。可以理解为低位掩码，也可以理解为截断高位吧。

    10100101 11000100 00100101
  & 00000000 00000000 00001111
  ----------------------------
    00000000 00000000 00000101
  
  
  以下位代码中的数组inedx 方法
  HashMap 中的取值皆是   ->  node = table[h & (length-1)] 
  
  static int indexFor(int h, int length) {
      return h & ( length - 1 );            
  }
  

• 而仅仅使用 hashCode，会有比较高的冲突概率，所以 JDK 引入了 扰动函数，简单来说就是 int 值的32位，保留自己的高位16位，并使用高位与低位做 按位异或 ^ 来做低位16位，使用这种形式来降低 hash 冲突。

  
  image.png