#### 1.1 HashMap为什么不是线程安全？

##### 1.1.1 以JDK1.8的HashMap为例

![](3.png)

上图为HashMap的PUT方法的详细过程.其中造成线程不安全的方法主要是resize(扩容)方法.

##### 1.1.2情况一:

假设现在有线程A 和线程B 共同对同一个HashMap进行PU操作,假设A和B插入的Key-Value中key的hashcode是相同的,这说明该键值对将会插入到Table的同一个下标的,也就是会发生哈希碰撞,此时HashMap按照平时的做法是形成一个链表(若超过八个节点则是红黑树),现在我们插入的下标为null(Table[i]==null)则进行正常的插入,此时线程A进行到了这一步正准备插入,这时候线程A堵塞,线程B获得运行时间,进行同样操作,也是Table[i]==null , 此时它直接运行完整个PUT方法,成功将元素插入. 随后线程A获得运行时间接上上面的判断继续运行,进行了Table[i]==null的插入(此时其实应该是Table[i]!=null的操作,因为前面线程B已经插入了一个元素了),这样就会直接把原来线程B插入的数据直接覆盖了,



如此一来就造成了线程不安全问题.

##### 1.1.3情况二:

![](4.png)这种情况是resize的时候造成的.现在假设HashMap中的Table情况如下:

线程A和线程B要对同一个HashMap进行PUT操作.插入后Table变为:

![](5.png)

此时,线程A和B都需要对HashMap进行扩容.
假设线程A没有堵塞过,顺利完成resize后Table如下(这里的元素位置都是假设的):

![](6.png)

如果线程B的resize是在Entry3的时候堵塞的,那么当它再次执行的时候就会造成处形成一个循环链表,当进行get操作时候可能陷入死循环,原因是:

![](7.png)线程B获得CPU时e = Entry3 ,next = Entry 2 ;正常赋值,然后进行下一次循环遍历时要注意,此时HashMap已经被线程A resize 过得了,那么就有 e = Entry 2 , next = Entry3 ; 头插法插入此时:,接着循环,e = Entry 3 ,next = Entry3.next = null (看图) ![](7.png),此时再时候头插法就会形成循环链表了.,附上头插法代码:![](9.png)

 

#### 1.2 红黑树

##### 1.2.1为什么需要红黑树？

搜索

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树。

**1.2.2红黑树的特性有哪些？**  原则==》  我们数据排列

首先，红黑树是一个搜索树，它同时满足以下特性：

(1) 每个节点要么是黑色，要么是红色

(2) 根节点是黑色

(3) 如果节点是红色的，那么它的子节点必须是黑色的（反之，不一定需要成立）

(4) 从根节点到叶节点或空子节点的每条路径，都包含相同数目的黑色节

通过看图来理解以上四个特性

![img](https://images2018.cnblogs.com/blog/1418442/201807/1418442-20180718090056127-465723908.png)

 

##### 1.2.3.红黑树的效率

红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。查找操作时，它和普通的相对平衡的二叉搜索树的效率相同，都是通过相同的方式来查找的，没有用到红黑树特有的特性。但，如果插入的时候是有序数据，那么红黑树的查询效率就比二叉搜索树要高了，因为此时二叉搜索树不是平衡树，它的时间复杂度O(N)。插入和删除操作时，由于红黑树的每次操作平均要旋转一次和变换颜色，所以它比普通的二叉搜索树效率要低一点，不过时间复杂度仍然是O(logN)。总之，红黑树的优点就是对有序数据的查询操作不会慢到O(logN)的时间复杂度。

##### 1.2.4.对旋转的理解

在红黑树中，插入或者删除数据时，为了保持红黑树的那五个特性，需要进行旋转和变换颜色的操作。旋转必须要一次性做两件事情：

\* 使一些节点上升，一些节点下降，帮助树平衡

\* 保证不破坏二叉搜索树的特征

旋转分为左旋转和右旋转，那么我们就看下左旋转和右旋转是怎么回事。

##### 1.2.5左旋转

此处，以50为支点进行逆时针旋转，然后75成为了顶点，50成为了75的左子节点，65成为了50的右子节点，这个操作就是左旋转。

![img](https://images2018.cnblogs.com/blog/1418442/201807/1418442-20180718091227152-868125214.png)

##### 1.2.6 右旋转

此处，以75为支点顺时针旋转，然后50成为了顶点，75成为了50的右子节点，65成为了75的左子节点，这就是右旋转操作。

![img](https://images2018.cnblogs.com/blog/1418442/201807/1418442-20180718091758420-1134513730.png)

##### 1.2.7插入操作

在介绍插入操作前，先约定一下各个节点的名称。看图：
![img](https://images2018.cnblogs.com/blog/1418442/201807/1418442-20180717141154291-1380532486.png)

在红黑树中，插入一个节点，都执行了哪些操作呢？

首先，查找要插入节点的位置，然后给予颜色（红色或者黑色），但是为了保证红黑树的特性，需要进行旋转或者更改颜色，需要注意的是，在旋转前和旋转后，红黑树一直都是一个二叉搜索树，二叉搜索树的特征从未改变过。

这里，对于新插入的节点，我们给予的颜色是红色，是因为为了和红黑树的第（4）条特性不冲突： 从根节点到叶节点或空子节点的每条路径，都包含相同数目的黑色节点。这样就少了很多操作。然后看其它几个特性

\* 对于(1)特性：每个节点要么是黑色，要么是红色，不冲突。

\* 对于(2)特性：根节点是黑色，如果插入的节点不是根节点，也不冲突。如果是根节点，那么直接给予颜色黑色

那么，唯一需要满足的特性就是（3）：如果节点是红色的，那么它的子节点必须是黑色的。这里，当我们给予新插入的节点颜色是红色时，需要根据父节点的不同情况做不同的处理，以满足这个特性。有以下几种情况：