文章首发于：clawhub.club

hash算法的优略直接影响到HashMap的性能。

扰动函数源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
   * Computes key.hashCode() and spreads (XORs) higher bits of hash
   * to lower.  Because the table uses power-of-two masking, sets of
   * hashes that vary only in bits above the current mask will
   * always collide. (Among known examples are sets of Float keys
   * holding consecutive whole numbers in small tables.)  So we
   * apply a transform that spreads the impact of higher bits
   * downward. There is a tradeoff between speed, utility, and
   * quality of bit-spreading. Because many common sets of hashes
   * are already reasonably distributed (so don't benefit from
   * spreading), and because we use trees to handle large sets of
   * collisions in bins, we just XOR some shifted bits in the
   * cheapest possible way to reduce systematic lossage, as well as
   * to incorporate impact of the highest bits that would otherwise
   * never be used in index calculations because of table bounds.
   * 由于该表使用了2的幂掩码，因此仅在当前掩码之上以位为单位变化的散列集总是会发生冲突。
   * (已知的例子包括在小表中保存连续整数的浮点键集。)因此，我们应用一个转换，将更高位的影响向下传播。
   * 位扩展的速度、实用性和质量之间存在权衡。
   * <p>
   * 因为许多常见的散列集已经合理分布(所以不要受益于传播),
   * 在桶中我们用树来处理大型的碰撞,通过异或一些位的改变以最优的的方式来减少系统lossage,纳入最高位的影响,
   * 否则，由于表范围，将永远不会在索引计算中使用它。
   * <p>
   * 计算key的hashCode值h
   * h无符号右移16位，得到h的高16位
   * h与其高16位异或。
   */
  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。直接用这个结果去映射键值对的时候，大概有40亿的映射空间。
h ^ (h >>> 16)：让hash值高位参与计算，增加扰动，优化散列值的分布。

异或运算符（^）
参与运算的两个值，如果两个相应位相同，则结果为0，否则为1。即：0^0=0， 1^0=1， 0^1=1， 1^1=0

取模运算：

计算出key在数组中的位置

1
(length - 1) & hash

这个算法的由来也是数学的奇妙之处，一般取模直接用hash%length就好了，但是性能不好。当length总是2的n次方时，hash& (length-1)运算等价于对length取模，也就是hash%length，但是&比%具有更高的效率。
这也正好解释了为什么HashMap的数组长度要取2的整次幂。

与操作符（&）
运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;
即：两位同时为1，结果才为1，否则为0
例如：3&5 即 0000 0011 & 0000 0101 = 0000 0001 因此，3&5的值得1。

综合例子：

1
2
3
4
5
6
7
8
9
10
11
12

    h = key.hashCode()： 1111 1111 1111 1111 1100 0000 1111 1110
-----------------------------------------------------------------	
              h >>> 16： 0000 0000 0000 0000 1111 1111 1111 1111
			   
 hash = h ^ (h >>> 16)： 1111 1111 1111 1111 0011 1111 0000 0001
-----------------------------------------------------------------	
                length:  0000 0000 0000 0000 0000 0000 0000 1100    12 
	      (length - 1):  0000 0000 0000 0000 0000 0000 0000 1011    11
   (length - 1) & hash:	 0000 0000 0000 0000 0000 0000 0000 0001     1
  
即放在第一个位置。

学习记录可能会有错误，欢迎交流。