高效取模运算（&）与扰动函数
前一段时间听到有人问HashMap是用链表数组还是用红黑树数组实现的，所以博主今天阅读了一下HashMap的源码。
在阅读HashMap源码时，发现了一个用的很少的表达式，经过网上查阅资料还有一些计算机组成原理的一些相关知识搞懂了这个表达式意义和优点。
接下来我来分享一下我追源代码的过程和对HashMap源码以及这个高效取模运算的理解。
1.测试的准备工作
因为是要对HashMap进行测试，所以我们自定义一个学生类，并覆盖hashCode（）和equals（）方法。这两个方法可以自己定义，也可以用IDEA自动生成，这里为了方便，我们用IDEA自动生成的即可。否则我们需要自己设计散列函数，并且这个函数需要将不同的对象均匀的散列在数组中。而仅仅是为了阅读源代码，我们目前还不需要这么麻烦。
import java.util.Objects;
public class Student {
private String stuNum;
private String name;
private boolean isMale;
private int age;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return isMale == student.isMale &&
age == student.age &&
Objects.equals(stuNum, student.stuNum) &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(stuNum, name, isMale, age);
}
public Student() {
}
public Student(String stuNum, String name, boolean isMale, int age) {
this.stuNum = stuNum;
this.name = name;
this.isMale = isMale;
this.age = age;
}
}
2.写测试方法，打断点。
3.进入断点内部
先安利一波巨人（故乡三人组）
当debug模式运行到断点处时，会显示到这个界面。标记的部分是进入方法内部。
我们来一步一步看看程序到底怎么运行的。
点击标记的小红箭头进入下一个界面：
此处只是将100.0进行了自动装箱成Double类型。后续几步都是创建Double类是进行的操作，在此我们并不重点了解。我们只关注最重要的put方法，我们看下张图。
我们看到：put方法知识调用了putVal（）方法，并且这个这个方法对传进来的参数key做了hash（key）的处理。我们继续点击红色小按钮，进入hash()方法内部。
key使我们的Student对象，这段代码调用了我们覆盖后的hashCode方法，得到了一个int类型的hashcode值。并且对这个值进行了移位和异或操作（^）
这里不得不介绍的是：扰动函数
(h = key.hashCode()) ^ (h >>> 16)这段代码即为扰动函数，那么为什么要进行这个操作呢？在我们接下来说到高效取模运算时候，我们会说到它的作用。先简单提一下：这个操作在jdk1.8之前是另外一段代码，但它们的功能一样，都是为了对hashcode进行低位和高位的混合。我们先看下一步。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
点击之后回到了我们的put方法，再点击红色小箭头，就进入到了我们的putVal()方法：
这个方法里面维护了一个Node类型的数组tab,还有一个Node类型的变量p。
tab实际上就是我们的HashMap
这段代码先将HashMap类中维护的table属性赋值给tab，如果table是空，那么则调用resize()方法。那么我们进入resize方法看看这个方法做了什么。
这个方法无非就是初始化了一系列table中的属性：
容量cap（记住这个容量，之后分配到桶中会用到这个值）
数组扩容时候的阈值：threshold（thr）
这里的阈值是根据装填因子（loadfactor）和容量来确定的。
这些常量我们都可以在HashMap中找到,HashMap中已经帮我们维护了这些常量。当然这些属性值都有什么意义，我们需要一些数据结构的知识。
下面的1左移4位就变成16 了。这里需要一点计算机组成原理的知识：
十进制中，我们通常移动的是小数点，例如将1变成10，我们只需要将1的小数点往右移动一位，相对的，我们的数字1就相对于小数点左移了移位。效果就是1变成了原来的10倍，即1*10。（这是针对于我们经常用的十进制来说的）。
同理，在计算机中，用的是二进制，计算机中的移位运算针对的是数字相对于小数点的移动。当1左移4位时，我们就相当于给1乘了4次2，因此它就变成了16。
最后它将初始化后的数组返回。我们点击红色小按钮回到putVal()方法中。
注意此时的n等于tab的长度，也就是容量16。
注意看蓝条中的将hashcode分配到桶中的方法，就是我们这次要着重介绍的高效取模运算，我们将它抽离出来。单独介绍。
高效取模运算
我们得到的hashcode可能是一个非常大的数，但我们的数组容量只有16，那么怎么将这个hashcode分配到我们的桶（数组中的某个元素）中呢。很简单的方法，那就是对我们的数组容量取模运算，即hashcode%16。但是java中为什么要表示成下面这种形式呢？这是因为在计算机中 & 的效率比 % 高很多，那么如何将 % 转换为 & 运算呢？
我们先给出结论：
当数组容量为2的n次幂时，即length=2n时
hashcode% 2n =hashcode&（2n-1）。
举个例子：
10%4=2
10=1010
4-1=0011
1010&0011=0010=2 两次结果显然相同。
那么我们试试10%3
10%3=1
3-1=2=0010
1010&0010=0010=2结果显然不同。
接下来我们证明这个公式：h%2n=h&（2n-1）
2n-1与某个数的&运算的意义
3=22-1=0011
7=23-1=0111
15=24-1=1111
我们让这些数都与13（1101）做&运算得到的结果分别是：
01=1（13对应的二进制数的后2位）
101=6（13对应的二进制数的后3位）
1101=13（13对应的二进制数的后4位）
即我们分别取得了13的后2,3,4位。而我们知道，在计算机组成原理中，这就对应着13分别对22,23,24,取模运算。即h%2n。
这样的数（3,7,15,31）正好相当于一个低位的掩码 ， 与操作（&）的作用就是将hashcode值得高位归0，只保留低位的值。
更严谨的数学证明请参考YSOcean的证明
但是，此时更加蛋疼的问题来了：即使我们的hashcode值散列的再稀疏，我们只取低4位的话，我们处理碰撞冲突也会大大增加。如果再加上hashCode()方法设计不好的情况（分布上成等差数列），就正好使低位呈现规律性重复。
这时候我们之前提到的扰动函数的作用就体现出来了！
借鉴一下这张著名的图：
hashcode经过右移16位，再与初始值做异或（^）操作，这样hashcode值的低位就掺杂了高位的特征，这样更有利于加大低位的随机性。
当然这个结果也是有人做过实验证明的：
在数组长度为232长度时，不经过扰动和经过扰动之后均没有发生碰撞，
216时，不经过扰动，碰撞次数为1次，经过扰动碰撞次数为3次
214时，不经过扰动，碰撞次数为6次，经过扰动碰撞次数为6次
212时，不经过扰动，碰撞次数为17次，经过扰动碰撞次数为15次
29时，不经过扰动，碰撞次数为103次，经过扰动碰撞次数为92次
我们发现，随着数组长度的越来越小，不经过扰动与经过扰动的碰撞次数之差，会越来越大。也就是说，数组容量越小，两种分配方式的效果相差会越来越大。
因此我们的HashMap采用了先将hashcode扰动之后，在取低位进行桶（数组的每个元素的地址）的分配。
桶分配完了，那么我们接下来看看下一步HashMap是怎么做的吧。
首先他对桶中有没有元素进行了判断：
如果桶是空的，则让此桶指向一个新节点（new Node），并把此节点中维护的一系列属性化为我们的key和value。
当然这是我们第一次添加Student对象，当然桶肯定是空的。
为了探究我们的桶中到底是用链表实现还是用红黑树实现，我们可以到下面的putTreeNode方法中看一下（其实通过这个名字就已经可以知道是用树结构来实现的了）
if ((p = tab[i = (n - 1) & hash]) == null)//桶是空的，则创建新Node节点添加进桶中
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
putTreeVal方法
我们可以发现，这个方法是维护在一个TreeNode的静态内部类中的，这个内部类在HashMap中。
很明显我们可以看到这个静态内部类中有一个boolean red属性，他是用来标记节点Node的父链接的颜色。很明显是红黑树了（红黑树实际上是基于2-3树产生的）。
通过大概浏览内部类中的最具树结构特点的方法（树结构的两个操作）：
（左旋）rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p)
（右旋）rotateRight(TreeNode<K,V> root,TreeNode<K,V> p)
此外，还有很重要的方法：（更新根节点）moveRootToFront和（平衡插入）balanceInsertion等一系列方法，博主没有全部展示出来。
我们可以知道JDK10版本中的HashMap是用红黑树数组来实现的。
下面是内部类中的部分代码：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;//用来标记父链接的颜色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/* ------------------------------------------------------------ */
// Red-black tree methods, all adapted from CLR
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
/**
* Recursive invariant check
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
}
至此，HashMap的put()方法算是告一段落