第1章-003节

hash()与indexFor()
1.1 hash()⽅法
在get和put的过程中，计算下标时，先对hashCode进⾏hash操作，然后再通过hash值进⼀步计
算下标，如下图所示：


在对hashCode()计算hash时具体实现是这样的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
按位取并，作⽤上相当于取模mod或者取余%。这意味着数组下标相同，并不表示hashCode相
同。
可以看到这个函数⼤概的作⽤就是：⾼16bit不变，低16bit和⾼16bit做了⼀个异或。其中代码注
释是这样写的：
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.
1.2 indexFor()⽅法
在设计hash函数时，因为⽬前的table⻓度length n为2的幂，⽽计算下标的时候，是这样实现的
(使⽤&位操作，⽽⾮%求余)：
static int indexFor(int h, int n) {
return h & (n-1);
}
设计者认为这⽅法很容易发⽣碰撞。为什么这么说呢？不妨思考⼀下，在n - 1为15(0x1111)时，
其实散列真正⽣效的只是低4bit的有效位，当然容易碰撞了。
因此，设计者想了⼀个顾全⼤局的⽅法(综合考虑了速度、作⽤、质量)，就是把⾼16bit和低16bit
异或了⼀下。设计者还解释到因为现在⼤多数的hashCode的分布已经很不错了，就算是发⽣了
碰撞也⽤O(logn)的tree去做了。仅仅异或⼀下，既减少了系统的开销，也不会造成的因为⾼位没
有参与下标的计算(table⻓度⽐较⼩时)，从⽽引起的碰撞。
如果还是产⽣了频繁的碰撞，会发⽣什么问题呢？作者注释说，他们使⽤树来处理频繁的碰撞
(we use trees to handle large sets of collisions in bins)，在JEP-180中，描述了这个问题：
Improve the performance of java.util.HashMap under high hash-collision conditions by
using balanced trees rather than linked lists to store map entries. Implement the same
improvement in the LinkedHashMap class.
之前已经提过，在获取HashMap的元素时，基本分两步：

• ⾸先根据hashCode()做hash，然后确定bucket的index；
• 如果bucket的节点的key不是我们需要的，则通过keys.equals()在链中找。
  在Java 8之前的实现中是⽤链表解决冲突的，在产⽣碰撞的情况下，进⾏get时，两步的时间复
  杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很⼤，O(n)的速度显然是影响速度的。
  因此在Java 8中，利⽤红⿊树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很⼤的时
  候，能够⽐较理想的解决这个问题，在Java 8：HashMap的性能提升⼀⽂中有性能测试的结果。
  大家一起学习丫~