HashMap的Hash算法

HashMap定位

1. 取key的HashCode值
2. 高位运算
3. 计算索引

求HashCode值

1. Integer: value

public static int hashCode(int value) {
      return value;
}

2. Long: 于高位做异或

public static int hashCode(long value) {
      return (int)(value ^ (value >>> 32));
}

3. Double： 变成long型，按long取HashCode

public static int hashCode(double value) {
     long bits = doubleToLongBits(value);
     return (int)(bits ^ (bits >>> 32));
}

4. String: h = 31 * h + val[i];

public int hashCode() {
      int h = hash;
      if (h == 0 && value.length > 0) {
          char val[] = value;
          for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
}

• 为什么是 31 呢？
  因为 31 是一个素数。（素数又称质数：指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。）
  根据素数的特性，与素数相乘得到的结果比其他方式更容易产生唯一性，也就是说产生 hash 值重复的概率比较小。
  Java 中如果相乘的数字太大会导致内存溢出问题，从而导致数据丢失。

高位运算

高16位异或低16位

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

计算索引

• 定位table：
  取模计算慢
  用 hash&(table.length-1) （eg: 1111取‘&与’）
  table.length为2的幂次方时，相当于对length取模
• 有值转为链表
• 超过8个转为红黑树

扩容

超过capacity * 0.75扩容
扩为2 * capacity