共计 14623 个字符，预计需要花费 37 分钟才能阅读完成。
写在最后面
这个我的项目是从 20 年末就立好的 flag，通过几年的学习，回过头再去看很多知识点又有新的了解。所以趁着找实习的筹备，联合以前的学习储备，创立一个次要针对应届生和初学者的 Java 开源常识我的项目，专一 Java 后端面试题 + 解析 + 重点常识详解 + 精选文章的开源我的项目，心愿它能随同你我始终提高！
阐明：此我的项目内容参考了诸多博主（已注明出处），材料，N 本书籍，以及联合本人了解，从新绘图，从新组织语言等等所制。集体之力菲薄，或有不足之处，在劫难逃，但更新 / 欠缺会始终进行。大家的每一个 Star 都是对我的激励！心愿大家能喜爱。
注：所有波及图片未应用网络图床，文章等均开源提供给大家。
我的项目名: Java-Ideal-Interview
Github 地址：Java-Ideal-Interview – Github
Gitee 地址：Java-Ideal-Interview – Gitee（码云）
继续更新中，在线浏览将会在前期提供，若认为 Gitee 或 Github 浏览不便，可克隆到本地配合 Typora 等编辑器舒服浏览
若 Github 克隆速度过慢，可抉择应用国内 Gitee 仓库
-
三 HashMap 源码剖析
-
1. 前置常识
-
1.1 什么是 Map
- 1.1.1 概述
- 1.1.2 Map 汇合和 Collection 汇合的区别
-
1.2 什么是散列表
- 1.2.1 剖析一下为什么要用散列表
- 1.2.2 散列表工作原理
-
1.2.3 如何解决 Hash 抵触
- 1.2.3.1 JDK 1.7
- 1.2.3.1 JDK 1.8
- 1.3 什么是红黑树
-
-
2. 源码剖析
- 2.1 类成员
-
2.2 两个节点
- 2.2.1 Node 节点
- 2.2.2 TreeNode 节点
- 2.3 构造方法
-
2.4 增加办法
- 2.4.1 put()
- 2.4.2 putVal()
-
2.5 获取办法
- 2.5.1 get()
- 2.5.2 getNode
-
2.6 移除办法
- 2.6.1 remove()
-
2.7 扩容办法
- 2.7.1 resize()
-
3. 重点剖析
- 3.1 hash() 中的扰动函数如何解决 Hash 抵触 ※
-
三 HashMap 源码剖析
1. 前置常识
1.1 什么是 Map
<div align=”center”>
</div>
在理论需要中，咱们经常会遇到这样的问题，在诸多的数据中，通过其编号来寻找某一些信息，从而进行查看或者批改，例如通过学号查问学生信息。明天咱们所介绍的 Map 汇合就能够很好的帮忙咱们实现这种需要
1.1.1 概述
Map 是一种存储元素对的汇合（元素对别离称作 键 和 值 也称键值对）它将键映射到值的对象。一个映射不能蕴含反复的键，并且每个键最 多只能映射到一个值。
怎么了解呢？
键 (key)：就是你存的值的编号 值 (value)：就是你要寄存的数据
你能够近似的将键了解为下标，值根据键而存储，每个键都有其对应值。这两者是 1、1 对应的
但在之前下标是整数，然而 Map 中键能够使任意类型的对象。
1.1.2 Map 汇合和 Collection 汇合的区别
- Map 汇合存储元素是成对呈现的，Map 汇合的键是惟一的，值是可反复的
- Collection 汇合存储元素是独自呈现的，Collection 的子类 Set 是惟一的，List 是可反复的。
- Map 汇合的数据结构值针对键无效，跟值无关，Collection 汇合的数据结构是针对元素无效
1.2 什么是散列表
散列表也叫 hash 表，是依据关键码值而进行间接进行拜访的数据结构。也就是说，它通过把关键码值映射到表中一个地位来拜访记录，以放慢查找的速度。这个映射也叫散列函数，寄存记录的数组叫散列表。
一个艰深的例子是，为了查找电话簿中某人的号码，能够创立一个依照人名首字母顺序排列的表（即建设人名到首字母的一个函数关系），在首字母为 W 的表中查找“王”姓的电话号码，显然比间接查找就要快得多。这里应用人名作为关键字，“取首字母”是这个例子中散列函数的函数法令，寄存首字母的表对应散列表。关键字和函数法令实践上能够任意确定。—— 维基百科
1.2.1 剖析一下为什么要用散列表
哈希表其实就是数组的一种扩大，因为其本质上用的就是数组能够 依照下标随机拜访数据 的特点，咱们来一步一步看一下
首先创立一个数组，咱们将数组的每一个存储空间看做一个一个箱子或者一个一个桶，存储一些 key-value 的数据如，【张三，20】【李四，30】【王五，40】【赵六，50】【孙七，60】，顺次搁置于数组中。
如果依照一般程序表的查问形式，就须要从开始顺次比对查问，然而数据量越多，程序表查找消耗的工夫就越长。在大量数据的状况下，很显然不上算。
还有很多种数据结构，它们并不关怀元素的程序，可能疾速的查找元素数据，其中一种就是：散列表
上面看看散列表如何做到这么高效解决的
1.2.2 散列表工作原理
这次仍旧应用 5 个箱子（桶）空间的数组来存储数据，咱们开始存第一个数据【张三，20】，散列表会应用哈希函数（Hash 算法）计算出“张三”的键，也就是字符串“张三”的哈希值，例如返回一个 5372，将其做取余解决，除数为数组的长度，即：5372 mod 5 = 2，因而将其放在下标（index）为 2 的地位，例如 第二个数据的哈希值为 6386，持续操作 6386 mod 5 = 1，行将其放在下标（index）为 1 的地位，以此类推 …..
然而有一种状况就会呈现了，例如咱们存储第三个数据【王五，40】的时候，通过哈希函数计算，得出的后果为 5277，5277 mod 5 = 2，然而 2 这个地位曾经有【张三，20】这个数据存在了，这种存储地位反复了的状况便叫作抵触
1.2.3 如何解决 Hash 抵触
1.2.3.1 JDK 1.7
在 JDK 1.8 之前，HashMap 的底层是数组和链表。因而当呈现哈希抵触后，应用 拉链法 解决抵触。
拉链法，就是将数组的每一个格子（箱子），都看作一个链表，例如下标为 1 的格子，就是一个链表，曾经存储了【张三，20】，若仍有数据哈希值 mod 后等于 1，则间接在 1 中的这个链表中追加上这些数据就能够了。
<div align=”center”>
</div>
1.2.3.1 JDK 1.8
JDK 8 做了一些较大的调整，当数组中每个格子里的链表，长度大于阈值（默认为 8）时，将链表转化为红黑树，就能够大大的缩小搜寻工夫。
而且，如果散列表快满的状况下下，还会有机制进行再散列，上面会在源码中深入分析。
1.3 什么是红黑树
红黑树是一种简单的树形构造，这里不做过于具体的解释，讲一下其根本的构造，有一个根本的概念。对于了解，还能够参考掘金上的一篇文章（掘金 - 漫画：什么是红黑树？@程序员小灰）十分不错！
红黑树就是为了避免二叉树一些极其的状况，例如变成一条线状，或者左右不平衡，从二叉查找树，2- 3 树 等演变进去的一种树形构造。最次要的目标就是为了保持平衡。保障树的左右分支叶子等根本均衡。
具体的数据后果演变是比较复杂的，这一篇还是次要解说 HashMap，有须要当前会专篇解说一些常见的数据结构的 Java 版本
2. 源码剖析
2.1 类成员
// 序列化主动生成的一个码，用来在正反序列化中验证版本一致性。private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量 1 * 2^4 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 1 * 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的加载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶的树化阈值，当桶 (bucket) 上的结点数大于这个值时会转成红黑树，// 也就是下面提到的长度大于阈值（默认为 8）时，将链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 桶的链表还原阈值，当桶 (bucket) 上的结点数小于这个值时树转链表
// 一个情理
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树形化容量阈值，当哈希表中的容量 > 该值时，才容许树形化链表
// 否则，若桶内元素太多时，则间接扩容，而不是树形化
// 为了防止进行扩容和树形化抉择的抵触，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是 2 的幂次倍
transient Node<k,v>[] table;
// 寄存具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 寄存元素的个数（不是数组的长度）transient int size;
// 扩容和批改的计数变量
transient int modCount;
// 临界值 当理论大小 (容量 * 填充因子) 超过临界值时，会进行扩容
int threshold;
// 加载因子
final float loadFactor;其中有几个须要强调的内容
threshold 临界值
- 数组扩容的一个临界值，即当数组理论大小（容量 填充因子，即：threshold = capacity loadFactor）超过临界值时，会进行扩容。
loadFactor 加载因子
- 加载因子就是示意哈希表中元素填满的水平，当表中元素过多，超过加载因子的值时，哈希表会主动扩容，个别是一倍，这种行为能够称作 rehashing（再哈希）。
- 加载因子的值设置的越大，增加的元素就会越多，的确空间利用率的到了很大的晋升，然而毫无疑问，就面临着哈希抵触的可能性增大，反之，空间利用率造成了节约，但哈希抵触也缩小了，所以咱们心愿在空间利用率与哈希抵触之间找到一种咱们所能承受的均衡，通过一些试验，定在了 0.75f。
2.2 两个节点
因为肯定条件下会转换成红黑树这种数据后果，所以除了一般的 Node 节点，还有 树节点（TreeNode 节点）
2.2.1 Node 节点
static class Node<K,V> implements Map.Entry<K,V> {
// 哈希码，用来查找地位以及比对元素是否雷同
final int hash;
// 键
final K key;
// 值
V value;
// 指向下一个结点
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key;}
public final V getValue() { return value;}
public final String toString() { return key + "=" + value;}
// 重写了 hashCode，^ 是位异或运算符
public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重写 equals() 办法
public final boolean equals(Object o) {if (o == this)
return true;
if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}2.2.2 TreeNode 节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 父节点
TreeNode<K,V> parent;
// 左节点
TreeNode<K,V> left;
// 右节点
TreeNode<K,V> right;
TreeNode<K,V> prev;
// 判断色彩，默认红色
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);
}
// 返回根节点
final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)
return r;
r = p;
}2.3 构造方法
// 指定了具体容量大小和加载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity:" +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor:" +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 指定了具体容量大小的构造函数
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 默认无参构造函数
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;}
// 指定了 map 的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}tableSizeFor
/**
* 返回一个大于输出参数，且最靠近的，2 的整数次幂的数
* 只是一个初始化内容，创立哈希表时，会再从新赋值
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}putMapEntries
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 拿到给定 Map 的长度
int s = m.size();
if (s > 0) {
// 判断以后理论存储数据的这个 table 是否曾经初始化
if (table == null) { // pre-size
// 没初始化，就将 s 解决后设为 m 的理论元素个数
float ft = ((float)s / loadFactor) + 1.0F;
// 避免小于最小容量（阈值）int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 若大于临界值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
// table 已初始化，并且给定 Map m 元素个数大于阈值，进行扩容解决
else if (s > threshold)
resize();
// 将给定汇合 m 中的所有元素增加至 HashMap 中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();
V value = e.getValue();
// putVal 办法会在介绍增加相干办法时介绍
putVal(hash(key), key, value, false, evict);
}
}
}2.4 增加办法
2.4.1 put()
对于 HashMap，其提供给外界的公共增加办法只有 put(K key, V value) 一个，其余 put 办法都是供 put(K key, V value) 外部调用的
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}对于 putVal 的每个参数和细节上面接着说，看一下第一个参数 hash(key) 首先提一下，在 HashMap 中是如何计算 hash 值的，跳转到 3.1 可看，也能够看完最初去看也能够。
3.1 hash() 中的扰动函数如何解决 Hash 抵触 ※ 中的扰动函数如何解决 Hash 抵触 ※)
2.4.2 putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
// table 未初始化（为 null）或者长度为 0，调用 resize 进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 若桶为空，即无产生碰撞
// (n - 1) & hash 用来确定元素寄存在哪个地位，即哪个桶中
if ((p = tab[i = (n - 1) & hash]) == null)
// 新生成结点放入桶中(数组中)
tab[i] = newNode(hash, key, value, null);
// 若桶中曾经存在元素
else {
Node<K,V> e; K k;
// 若节点 key 存在，就和要插入的 key 比拟
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果 key 雷同就间接笼罩 value
e = p;
// hash 值不相等，即 key 不相等，转为红黑树结点
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;
}
// 遍历的过程中，遇到雷同 key 则笼罩 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与后面的 e = p.next 组合，能够遍历链表
p = e;
}
}
// 在桶中找到 key 值、hash 值与插入元素相等的结点
if (e != null) {
// 记录 e 的 value
V oldValue = e.value;
// onlyIfAbsent 为 false 或者旧值为 null
if (!onlyIfAbsent || oldValue == null)
// 用新值替换旧值
e.value = value;
// 拜访后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性批改
++modCount;
// 超过最大容量，扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
} 总结一下大抵流程：
- 先定位到具体的数组地位，例如叫做 A
-
若 A 处没有元素
- 就直接插入
-
若 A 处 有元素就和待插入的 key 比拟
- 若 key 雷同就间接笼罩
-
若 key 不雷同，就判断 p 是否是一个树节点
- 如果是就调用 putTreeVal 办法将元素增加进入
- 如果不是就遍历链表插入（尾插法）
2.5 获取办法
2.5.1 get()
同样 get 办法中也用到了 hash 办法计算 key 的哈希值，同样跳转到 3.1 可看，也能够看完最初去看也能够。
3.1 hash() 中的扰动函数如何解决 Hash 抵触 ※ 中的扰动函数如何解决 Hash 抵触 ※)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}2.5.2 getNode
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 保障计算出来的哈希值，确定是在哈希表上的
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 要是间接在桶的首个地位上，间接就能够返回（这个桶中只有一个元素，或者在首个）if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中不止一个节点
if ((e = first.next) != null) {
// 在树中 get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中 get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}2.6 移除办法
2.6.1 remove()
同样 get 办法中也用到了 hash 办法计算 key 的哈希值，同样跳转到 3.1 可看，也能够看完最初去看也能够。
3.1 hash() 中的扰动函数如何解决 Hash 抵触 ※ 中的扰动函数如何解决 Hash 抵触 ※)
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}2.6.2 removeNode()
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;
// 桶不为空，映射的哈希值也存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 如果在桶的首位就找到对应元素，记录下来
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 若不在首位，就去红黑树或者链表中查问了
else if ((e = p.next) != null) {if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 找到了要删除的节点和值，就分三种状况去删除，链表，红黑树，桶的首位
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}2.7 扩容办法
2.7.1 resize()
resize 在程序中是十分耗时的。要尽量避免用它。
- 其过程中会重新分配 hash，而后遍历 hash 表中所有的元素
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值，不再扩容，没方法了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就裁减为原来的 2 倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始化时，threshold 临时保留 initialCapacity 参数的值
newCap = oldThr;
else {
// signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的 resize 下限
if (newThr == 0) {float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 将旧的键值对挪动到新的哈希桶数组中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {oldTab[j] = null;
// / 无链条，也就是没有下一个，只有本人
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 拆红黑树，先拆成两个子链表，再别离按需转成红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 拆链表，拆成两个子链表并放弃原有程序
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到新的哈希桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引 +oldCap 放到新的哈希桶中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}3. 重点剖析
3.1 hash() 中的扰动函数如何解决 Hash 抵触 ※
看 HashMap 的 put 办法源码：
//HashMap 源码节选 -JDK8
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}而咱们的值在返回前须要通过 HashMap 中的 hash 办法
接着定位到 hash 办法的源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}hash 办法的返回后果中是一句三目运算符，键 (key) 为 null 即返回 0, 存在则返回后一句的内容
(h = key.hashCode()) ^ (h >>> 16)JDK8 中 HashMap——hash 办法中的这段代码叫做“扰动函数”
咱们来剖析一下：
hashCode 是 Object 类中的一个办法，在子类中个别都会重写，而依据咱们之前本人给出的程序，暂以 Integer 类型为例，咱们来看一下 Integer 中 hashCode 办法的源码：
/**
* Returns a hash code for this {@code Integer}.
*
* @return a hash code value for this object, equal to the
* primitive {@code int} value represented by this
* {@code Integer} object.
*/
@Override
public int hashCode() {return Integer.hashCode(value);
}
/**
* Returns a hash code for a {@code int} value; compatible with
* {@code Integer.hashCode()}.
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for a {@code int} value.
*/
public static int hashCode(int value) {return value;}Integer 中 hashCode 办法的返回值就是这个数自身
注：整数的值因为与整数自身一样惟一，所以它是一个足够好的散列
所以，上面的 A、B 两个式子就是等价的
// 注：key 为 hash(Object key)参数
A：(h = key.hashCode()) ^ (h >>> 16)
B：key ^ (key >>> 16)剖析到这一步，咱们的式子只剩下位运算了，先不急着算什么，咱们先理清思路
HashSet 因为底层应用 哈希表（链表联合数组）实现，存储时 key 通过一些运算后得出本人在数组中所处的地位。
咱们在 hashCoe 办法中返回到了一个等同于自身值的散列值，然而思考到 int 类型数据的范畴：-2147483648~2147483647，着很显然，这些散列值不能间接应用，因为内存是没有方法放得下，一个 40 亿长度的数组的。所以它应用了对数组长度进行 取模运算 ，得余后再作为其数组下标，indexFor() ——JDK7 中，就这样呈现了，在 JDK8 中 indexFor() 就隐没了，而全副应用上面的语句代替，原理是一样的。
//JDK8 中
(tab.length - 1) & hash； //JDK7 中
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {return h & (length - 1);
}提一句，为什么取模运算时咱们用 & 而不必 % 呢，因为位运算间接对内存数据进行操作，不须要转成十进制，因而处理速度十分快，这样就导致位运算 & 效率要比取模运算 % 高很多。
看到这里咱们就晓得了，存储时 key 须要通过 hash 办法 和indexFor()运算，来确定本人的对应下标
(取模运算，应以 JDK8 为准，但为了称说不便，还是依照 JDK7 的叫法来说，上面的例子均为此，特此提前申明)
然而先间接看与运算(&)，如同又呈现了一些问题，咱们举个例子：
HashMap 中初始长度为 16，length – 1 = 15；其二进制示意为 00000000 00000000 00000000 00001111
而与运算计算形式为：遇 0 则 0，咱们轻易举一个 key 值
1111 1111 1010 0101 1111 0000 0011 1100
& 0000 0000 0000 0000 0000 0000 0000 1111
----------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1100咱们将这 32 位从中离开，右边 16 位称作高位，左边 16 位称作低位，能够看到通过 & 运算后 后果就是高位全副归 0，剩下了低位的最初四位。然而问题就来了，咱们依照以后初始长度为默认的 16，HashCode 值为下图两个，能够看到，在不通过扰动计算时，只进行与 (&) 运算后 Index 值均为 12 这也就导致了哈希抵触
哈希抵触的简略了解：打算把一个对象插入到散列表 (哈希表) 中，然而发现这个地位曾经被别的对象所占据了
例子中，两个不同的 HashCode 值却通过运算后，失去了雷同的值，也就代表，他们都须要被放在下标为 2 的地位
一般来说，如果数据分布比拟宽泛，而且存储数据的数组长度比拟大，那么哈希抵触就会比拟少，否则很高。
然而，如果像上例中只取最初几位的时候，这可不是什么坏事，即便我的数据分布很散乱，然而哈希抵触依然会很重大。
别忘了，咱们的扰动函数还在后面搁着呢，这个时候它就要施展弱小的作用了, 还是应用下面两个产生了哈希抵触的数据，这一次咱们退出扰动函数再进行与 (&) 运算
补充：>>> 按位右移补零操作符，左操作数的值按右操作数指定的为主右移，挪动失去的空位以零填充
^ 位异或运算，雷同则 0，不同则 1
能够看到，本产生了哈希抵触的两组数据，通过扰动函数解决后，数值变得不再一样了，也就防止了抵触
其实在 扰动函数 中，将 数据右位移 16 位 ，哈希码的 高位和低位混合 了起来，这也正解决了后面所讲 高位归 0，计算只依赖低位最初几位的状况, 这使得高位的一些特色也 对低位产生了影响 ，使得 低位的随机性增强 ，能更好的 防止抵触
