共计 4336 个字符，预计需要花费 11 分钟才能阅读完成。
前言
某日，囧辉和共事二狗决定就谁是“￥* 大厦 11 楼 11 室（只有囧辉和二狗两人）HashMap 最强者”开展一番较量。画面过于血腥，成年人 请在未成年人陪同下观看。
注释
二狗：天天听你这憨逼吹牛，是时候让你晓得什么叫仁慈了。
囧辉：二狗子，这屎能够乱吃，这话不能乱说哦。
二狗：先来点简略的，介绍下 HashMap 的底层数据结构吧。
囧辉：咱们当初用的都是 JDK 1.8，底层是由“数组 + 链表 + 红黑树”组成，如下图，而在 JDK 1.8 之前是由“数组 + 链表”组成。
二狗：为什么要改成“数组 + 链表 + 红黑树”？
囧辉：次要是为了晋升在 hash 抵触重大时（链表过长）的查找性能，应用链表的查找性能是 O(n)，而应用红黑树是 O(logn)。
二狗：那在什么时候用链表？什么时候用红黑树？
囧辉：对于插入，默认状况下是应用链表节点。当同一个索引地位的节点在新增后达到 9 个（阈值 8）：如果此时数组长度大于等于 64，则会触发链表节点转红黑树节点（treeifyBin）；而如果数组长度小于 64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比拟小。
对于移除，当同一个索引地位的节点在移除后达到 6 个，并且该索引地位的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。
二狗：为什么链表转红黑树的阈值是 8？
囧辉：咱们平时在进行方案设计时，必须思考的两个很重要的因素是：工夫和空间。对于 HashMap 也是同样的情理，简略来说，阈值为 8 是在工夫和空间上衡量的后果（这 B 我装定了）。
红黑树节点大小约为链表节点的 2 倍，在节点太少时，红黑树的查找性能劣势并不显著，付出 2 倍空间的代价作者感觉不值得。
现实状况下，应用随机的哈希码，节点散布在 hash 桶中的频率遵循泊松散布，依照泊松散布的公式计算，链表中节点个数为 8 时的概率为 0.00000006（跟大乐透一等奖差不多，中大乐透？不存在的），这个概率足够低了，并且到 8 个节点时，红黑树的性能劣势也会开始展示进去，因而 8 是一个较正当的数字。
二狗：（呦呦呦，工夫和空间上衡量的后果，还装起 B 来了）那为什么转回链表节点是用的 6 而不是复用 8？
囧辉：如果咱们设置节点多于 8 个转红黑树，少于 8 个就马上转链表，当节点个数在 8 彷徨时，就会频繁进行红黑树和链表的转换，造成性能的损耗。
二狗：（小菜鸡，懂得还不少）那 HashMap 有哪些重要属性？别离用于做什么的？
囧辉：除了用来存储咱们的节点 table 数组外，HashMap 还有以下几个重要属性：1）size：HashMap 曾经存储的节点个数；2）threshold：扩容阈值，当 HashMap 的个数达到该值，触发扩容。3）loadFactor：负载因子，扩容阈值 = 容量 * 负载因子。
二狗：threshold 除了用于寄存扩容阈值还有其余作用吗？
囧辉：在咱们新建 HashMap 对象时，threshold 还会被用来存初始化时的容量。HashMap 直到咱们第一次插入节点时，才会对 table 进行初始化，防止不必要的空间节约。
二狗：HashMap 的默认初始容量是多少？HashMap 的容量有什么限度吗？
囧辉：默认初始容量是 16。HashMap 的容量必须是 2 的 N 次方，HashMap 会依据咱们传入的容量计算一个大于等于该容量的最小的 2 的 N 次方，例如传 9，容量为 16。
二狗：（你他娘的是在绕口令吧）你这个 *@%￥#& 的 N 次方是怎么算的？
囧辉：Talk is cheap. Show you the code。
static final int tableSizeFor(int cap) {二狗：卧槽，还彪英文，来来来，这代码你给我解释下。
囧辉：咱们先不看第一行“int n = cap – 1”，先看上面的 5 行计算。
|=（或等于）：这个符号比拟少见，然而“+=”应该都见过，看到这你应该明确了。例如：a |= b，能够转成：a = a | b。
>>>（无符号右移）：例如 a >>> b 指的是将 a 向右挪动 b 指定的位数，右移后右边空出的位用零来填充，移出左边的位被抛弃。
假如 n 的值为 0010 0001，则该计算如下图：
置信你应该看进去，这 5 个公式会通过最高位的 1，拿到 2 个 1、4 个 1、8 个 1、16 个 1、32 个 1。当然，有多少个 1，取决于咱们的入参有多大，但咱们必定的是通过这 5 个计算，失去的值是一个低位全是 1 的值，最初返回的时候 +1，则会失去 1 个比 n 大的 2 的 N 次方。
这时再看结尾的 cap – 1 就很简略了，这是为了解决 cap 自身就是 2 的 N 次方的状况。
计算机底层是二进制的，移位和或运算是十分快的，所以这个办法的效率很高。
PS：这是 HashMap 中我集体最喜爱的设计，十分奇妙，真想给作者一个么么哒（不小心裸露了）。
二狗：（这叼毛讲的还对付啊，连我都听懂了）你说 HashMap 的容量必须是 2 的 N 次方，这是为什么？
囧辉：计算索引地位的公式为：(n – 1) & hash，当 n 为 2 的 N 次方时，n – 1 为低位全是 1 的值，此时任何值跟 n – 1 进行 & 运算会等于其自身，达到了和取模同样的成果，实现了均匀分布。实际上，这个设计就是基于公式：x mod 2^n = x & (2^n – 1)，因为 & 运算比 mod 具备更高的效率。
如下图，当 n 不为 2 的 N 次方时，hash 抵触的概率显著增大。
二狗：你说 HashMap 的默认初始容量是 16，为什么是 16 而不是其余的？
囧辉：（这是什么煞笔问题）我认为是 16 的起因次要是：16 是 2 的 N 次方，并且是一个较正当的大小。如果用 8 或 32，我感觉也是 OK 的。实际上，咱们在新建 HashMap 时，最好是依据本人应用状况设置初始容量，这才是最正当的计划。
二狗：方才说的负载因子默认初始值又是多少？
囧辉：负载因子默认值是 0.75。
二狗：为什么是 0.75 而不是其余的？
囧辉：（又问这种憨逼问题）这个也是在工夫和空间上衡量的后果。如果值较高，例如 1，此时会缩小空间开销，然而 hash 抵触的概率会增大，减少查找老本；而如果值较低，例如 0.5，此时 hash 抵触会升高，然而有一半的空间会被节约，所以折衷思考 0.75 仿佛是一个正当的值。
二狗：为什么不是 0.74 或 0.76？
囧辉：
二狗：那咱们换个问题问吧，HashMap 的插入流程是怎么样的？
囧辉：Talk is cheap. Show you the picture。
二狗：图里刚开始有个计算 key 的 hash 值，是怎么设计的？
囧辉：拿到 key 的 hashCode，并将 hashCode 的高 16 位和 hashCode 进行异或（XOR）运算，失去最终的 hash 值。
static final int hash(Object key) {二狗：为什么要将 hashCode 的高 16 位参加运算？
囧辉：次要是为了在 table 的长度较小的时候，让高位也参加运算，并且不会有太大的开销。
例如下图，如果不退出高位运算，因为 n – 1 是 0000 0111，所以后果只取决于 hash 值的低 3 位，无论高位怎么变动，后果都是一样的。
如果咱们将高位参加运算，则索引计算结果就不会仅取决于低位。
二狗：扩容（resize）流程介绍下？
囧辉：
二狗：红黑树和链表都是通过 e.hash & oldCap == 0 来定位在新表的索引地位，这是为什么？
囧辉：请看对上面的例子。
扩容前 table 的容量为 16，a 节点和 b 节点在扩容前处于同一索引地位。
扩容后，table 长度为 32，新表的 n – 1 只比老表的 n – 1 在高位多了一个 1（图中标红）。
因为 2 个节点在老表是同一个索引地位，因而计算新表的索引地位时，只取决于新表在高位多进去的这一位（图中标红），而这一位的值刚好等于 oldCap。
因为只取决于这一位，所以只会存在两种状况：1）(e.hash & oldCap) == 0，则新表索引地位为“原索引地位”；2）(e.hash & oldCap) == 1，则新表索引地位为“原索引 + oldCap 地位”。
二狗：HashMap 是线程平安的吗？
囧辉：不是。HashMap 在并发下存在数据笼罩、遍历的同时进行批改会抛出 ConcurrentModificationException 异样等问题，JDK 1.8 之前还存在死循环问题。
二狗：介绍一下死循环问题？
囧辉：导致死循环的根本原因是 JDK 1.7 扩容采纳的是“头插法”，会导致同一索引地位的节点在扩容后程序反掉。而 JDK 1.8 之后采纳的是“尾插法”，扩容后节点程序不会反掉，不存在死循环问题。
JDK 1.7.0 的扩容代码如下，用例子来看会好了解点。
void transfer(Entry[] newTable) {PS：这个流程较难了解，倡议对着代码本人模仿走一遍。
例子：咱们有 1 个容量为 2 的 HashMap，loadFactor=0.75，此时线程 1 和线程 2 同时往该 HashMap 插入一个数据，都触发了扩容流程，接着有以下流程。
1）在 2 个线程都插入节点，触发扩容流程之前，此时的构造如下图。
2）线程 1 进行扩容，执行到代码：Entry<K,V> next = e.next 后被调度挂起，此时的构造如下图。
3）线程 1 被挂起后，线程 2 进入扩容流程，并走残缺个扩容流程，此时的构造如下图。
因为两个线程操作的是同一个 table，所以该图又能够画成如下图。
4）线程 1 复原后，持续走完第一次的循环流程，此时的构造如下图。
5）线程 1 持续走完第二次循环，此时的构造如下图。
6）线程 1 继续执行第三次循环，执行到 e.next = newTable[i] 时造成环，执行完第三次循环的构造如下图。
如果此时线程 1 调用 map.get(11)，喜剧就呈现了——Infinite Loop。
二狗：（尼玛，没听懂，难堪了）那总结下 JDK 1.8 次要进行了哪些优化？
囧辉：JDK 1.8 的次要优化方才咱们都聊过了，次要有以下几点：
1）底层数据结构从“数组 + 链表”改成“数组 + 链表 + 红黑树”，次要是优化了 hash 抵触较重大时，链表过长的查找性能：O(n) -> O(logn)。
2）计算 table 初始容量的形式产生了扭转，老的形式是从 1 开始一直向左进行移位运算，直到找到大于等于入参容量的值；新的形式则是通过“5 个移位 + 或等于运算”来计算。
// JDK 1.7.03）优化了 hash 值的计算形式，老的通过一顿瞎 JB 操作，新的只是简略的让高 16 位参加了运算。
// JDK 1.7.04）扩容时插入方式从“头插法”改成“尾插法”，防止了并发下的死循环。
5）扩容时计算节点在新表的索引地位形式从“h & (length-1)”改成“hash & oldCap”，性能可能晋升不大，但设计更奇妙、更优雅。
二狗：除了 HashMap，还用过哪些 Map，在应用时怎么抉择？
囧辉：
二狗：（不妙，这个 B HashMap 懂得比我还多，得连忙溜）到工夫和女朋友吃饭了，咱们之后再分输赢。
囧辉：