前言

在讲解JDK8的HashMap之前，我们需要了解一些数据结构

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

定义
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。

以下为一个二叉排序树

二叉排序树查找步骤：

若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）：
在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数
（上图应为左子树P(3)，右子树P(2)）
P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2
∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
∴ P（n）= P（n,i）/ n <= 2(1+I/n)lnn
因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)

插入删除
与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

红黑树

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树.

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。

由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

特征
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3.所有叶子节点都是黑色。（叶子是NUIL节点）

性质4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）

性质5… 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

是性质4导致路径上不能有两个连续的红色节点确保了这个结果。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

因为红黑树是一种特化的二叉查找树，所以红黑树上的只读操行与普通二叉查找树相同。

树的旋转
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性
树的左旋
树的左旋(2张)
质。
为了保持红黑树的性质，我们可以对相关节点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。

左旋：

右旋：

1.节点插入算法
插入过程首先是根据一般二叉查找树的插入步骤， 把新节点 z 插入到 某个叶节点的位置上，然后将 z 着 为红色。 为了保证红黑树的性质能继续保 持，再对有关节点重点着色并旋转，其插入算法如下：

RB-INSERT (T,z) {
1 按二叉查找树的插入步骤将节点 z 插入到 T 中；
2 color[z]=RED；
3 while(z 不是根节点 &&color[z->parent]= =RED) {Insert-Fixup(T,z);}
4 color[root[T]]=BLACK； }

2.节点删除算法
与红黑树的的插入算法一样，对一个节点的删除算法要花 O(log n)时间，只是删 除算法略微复杂些，删除算法如下：
RB-DELETE(T,z) {
1 if (z 的左右子节点均为 NIL)
2 { NIL 节点代替 z 的位置； delete(z); }
3 else if (z 有一个子节点为 NIL)
4 {z 的非 NIL 子节点代替 z 的位置；delete(z); }
5 else
6 {将红黑树中序遍历中 z 的后继节点 s 的值赋给 z; delete(s); }
7 if (删除的节点是黑色的) Delete-Fixup(T,x); /*x 指向代替删除节点的节点 */ }

操作
在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也是二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更（这在实践中是非常快速的）并且不超过三次树旋转（对于插入是两次）。这允许插入和删除保持为 O（log n)）次，但是它导致了非常复杂的操作。

数组

数组
在java中当创建数组时会在内存中划分出一块连续的内存，然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。当需要读取数组中的数据时，需要提供数组中的索引，然后数组根据索引将内存中的数据取出来，返回给读取程序。在Java中并不是所有的数据都能存储到数组中，只有相同类型的数据才可以一起存储到数组中。

数组在存储数据时是按顺序存储的，存储数据的内存也是连续的，所以他的特点就是寻址读取数据比较容易，插入和删除比较困难。简单解释一下为什么，在读取数据时，只需要告诉数组要从哪个位置（索引）取数据就可以了，数组会直接把你想要的位置的数据取出来给你。插入和删除比较困难是因为这些存储数据的内存是连续的，要插入和删除就需要变更整个数组中的数据的位置。举个例子：一个数组中编号0->1->2->3->4这五个内存地址中都存了数组的数据，但现在你需要往4中插入一个数据，那就代表着从4开始，后面的所有内存中的数据都要往后移一个位置。这可是很耗时的。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

特点
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如概述旁的图所示），表示线性表中一个数据元素。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。

其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

由分别表示,，…，的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。

以下为一个单链表：

数组与链表的比较
1.插入、删除和随机访问的时间复杂度
数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2.数组缺点
1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

3.链表缺点
1）内存空间消耗更大，因为需要额外的空间存储指针信息。
2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

HashMap解析

在jdk1.8之前，HashMap 的实现是 数组+链表。但是即使哈希函数取得再好，也很难做到所有元素均匀分布。

当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

所以，在jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中（查找时间复杂度为 O(logn)），以加快检索速度。

以下为jdk8的HashMap源码的一些讲解

在jdk8的HashMap中，新增了一中节点：TreeNode，它就是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;
}
可以看到，里面有父节点、左右孩子节点、前一个元素的节点，还有个颜色值。

另外由于它继承自 LinkedHashMap.Entry ，而 LinkedHashMap.Entry 继承自 HashMap.Node ，因此还有额外的 6 个属性：

static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}

static class Node<K,V> implements Map.Entry<K,V> {
//哈希值
final int hash;
//键
final K key;
//值
V value;
//指向下一个节点的指针
Node<K,V> next;
}

HashMap 中有三个关于红黑树的关键参数:

TREEIFY_THRESHOLD
UNTREEIFY_THRESHOLD
MIN_TREEIFY_CAPACITY

/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*树化阈值,只有当元素个数超过这个值时，才会使用红黑树节点替换链表节点。这个值为 8，因为频繁转换效率也不高
*/
static final int TREEIFY_THRESHOLD = 8;

/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.*一个树的链表还原阈值，当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构*/
static final int UNTREEIFY_THRESHOLD = 6;/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.*哈希表的最小树形化容量，当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化，为了避免进行扩容、            树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD*/
static final int MIN_TREEIFY_CAPACITY = 64;

HashMap 在 JDK 1.8 中新增的操作：桶的树形化 treeifyBin()
在Java 8 中，如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 )，就使用红黑树来替换链表，从而提高速度。

这个替换的方法叫 treeifyBin() 即树形化。

在putVal使用

 for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}

treeifyBin源码

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//如果当前哈希表为空，或者哈希表中元素的个数小于进行树形化的阈值(默认为 64)，就去扩容if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();//如果哈希表中的元素个数超过了 树形化阈值，进行树形化// e 是哈希表中指定位置桶里的链表节点，从第一个开始else if ((e = tab[index = (n - 1) & hash]) != null) {//hd为头节点，tl为尾节点TreeNode<K,V> hd = null, tl = null;do {//新建一个树形节点TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);//让桶的第一个元素指向新建的红黑树头结点，这样桶里的结构就变成红黑树if ((tab[index] = hd) != null)hd.treeify(tab);}}//创建新的TreeNodeTreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {return new TreeNode<>(p.hash, p.key, p.value, next);}

上述操作做了这些事:

根据哈希表中元素个数确定是扩容还是树形化
如果是树形化
遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系
然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容
但是我们发现，之前的操作并没有设置红黑树的颜色值，现在得到的只能算是个二叉树。在 最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树，来看看代码：

final void treeify(Node<K,V>[] tab) {TreeNode<K,V> root = null;for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;x.left = x.right = null;//给头节点进行赋值if (root == null) {x.parent = null;x.red = false;root = x;}//其他节点的循环else {K k = x.key;int h = x.hash;Class<?> kc = null;//从头节点root开始遍历比较for (TreeNode<K,V> p = root;;) {int dir, ph;K pk = p.key;//当比较节点的哈希值比 x 大时， dir 为 -1if ((ph = p.hash) > h)dir = -1;//当比较节点的哈希值比 x 小时， dir 为 1else if (ph < h)dir = 1;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)dir = tieBreakOrder(k, pk);TreeNode<K,V> xp = p;//如果当前节点的孩子节点为null，把 当前节点变成 x 的父亲if ((p = (dir <= 0) ? p.left : p.right) == null) {x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;root = balanceInsertion(root, x);break;}}}}moveRootToFront(tab, root);}