大家好，又见面了，我是你们的朋友全栈君。
HashMap的实现原理可以说是面试中必问的一道面试题了，它可以考察一个程序员的数据结构功底和对技术的钻研深度。Java7中HashMap的实现就是一个数组，然后数组中的每一个元素又是一个链表，这个链表的存在是为了解决哈希冲突导致的问题，就是一个元素经过哈希计算后得到元素的存储位置，但是这个位置已经有其它元素占领，也就是占领元素和新插入元素都在这个数组中的同一个位置，此时就用链表进行维护这个存储位置。也就是说Java7中HashMap使用数组加链表的形式实现的，简单点可以用下面的图比较直观的表示：
而在Java8以后，java对HashMap做了改进，在链表长度超过8的时候，将数据的存储从链表转变为使用红黑树这种数据结构进行存储，之所以使用红黑树，是因为红黑树的检索比链表要快的多，在链表中要查找某个元素，需要使用遍历的方式实现，此时查找需要的时间复杂度是O(n)，而对于红黑树来说，它需要的时间复杂度是O(logn)，之所以是O(logn)，我们接下来分析红黑树的时候会看到。首先来看看什么是二叉搜索树和平衡二叉树。
- 二叉搜索树(BST)：对于二叉树的任意一个节点来说，这个节点的左子树都比它小，右子树都比它大，如下图所示，二叉搜索树有个不好的地方，就是当插入的节点都比前一个插入的节点大或小时，此时就会退化成了一条线性的存储结构了，比如插入的顺序是1-2-3-4-5-6，此时查询的时间复杂度就变成了O(n)了。
- 平衡二叉树(AVL)：平衡二叉树也是一个二叉搜索树，但是平衡二叉树有个约束条件，就是任意一个节点的左子树和右子树的深度差小于等于1，这样能有效避免上面提到的二叉搜索树退化成线性的情况了，平衡二叉树的搜索要么查找到当前节点就是目标节点，要么比当前节点小往左子树进行搜索，要么比当前节点大往右子树搜索，也就是说在二叉树的每一层，我们只需要跟一个节点进行比较，所以它的的时间复杂度是O(logn)。
红黑树需要满足的条件
- 每个节点要么是黑色，要么就是红色
- 根节点也就是root节点需要是黑色
- 红节点的子节点一定是黑节点(红节点肯定有父节点，且是黑节点)
- 叶子节点和null节点是黑节点(说明了红黑树中一半以上都是黑节点)
- 从红黑树的任意一个节点出发到它的叶子节点，它所经过的黑节点数都是相同的，这就是红黑树所需要实现的平衡(也就是说，当前节点的每一条分支路径，它们所包括的黑节点数是一样的，最差的情况就是红黑相间)
- 新插入的节点是红节点，可能在参与平衡操作时会变成黑节点(加入直接插入的节点就是黑节点的话，那么每插入一个节点肯定都要做旋转或者变色来达到平衡。但是如果新插入的是红节点且它的父节点是黑节点的话，那就直接插入，整棵树还是平衡的，就不需要再做平衡处理了)
红黑树的时间复杂度
从上面平衡二叉树中我们知道，平衡二叉树的任意节点的左右子树的深度相同或者差1，这个条件稍微有点苛刻了，这样会出现很多时候插入时出现不满足的情况，需要花时间去做一些变换。而从红黑树所需要的条件中可以推出，红黑树的任意节点的左右子树的深度相同，或者相差一倍，也就是某条分支路径上出现了红黑相间，从中可以看到，红黑树所需要的平衡条件相比于平衡二叉树要宽松的多，这种条件就使得我们在插入节点的变换会更少。
我们再来看看红黑树的时间复杂度，首先要知道树的搜索过程或者插入过程的复杂度是完全依赖于树的深度的，假如红黑树有N个节点，黑节点有N(b)个，红节点有N(r)个，即N = N(b) N(r)，我们可以先把红黑树的红节点盖住只看黑节点的话，那么整棵树其实就是一个平衡二叉树，此时的时间复杂度是就是O(logN(b))，而从上面的分析我们知道最差的情况就是红黑相间，也就是路径中红节点的个数是黑节点的两倍，此时，时间复杂度将是2O(logN(b))，又因为红黑树中黑节点占了一半以上，那么N(b)最大也就是逼近于N，即N(b) = N，此时时间复杂度就是2O(logN)，也即是O(logn)，到这里可以看到红黑树的时间复杂和平衡二叉树的时间复杂度都是O(logn)，但是红黑树却拥有更宽松的条件，这也是为什么红黑树用的比平衡二叉树多的重要原因。
红黑树的查找操作
红黑树其实就是一个二叉搜索树，那么它的查找操作显然就比较简单了，首先把根节点当做是当前节点，如果当前节点是空节点的话就直接返回null，当根节点就是要查找的目标节点时就直接返回根节点，但如果不是且当前节点要比所要查找节点大的话，那就往左子树的方向进行查找，否则就往右子树的方向进行查找，重复以上的的操作步骤，直到查到目标节点返回节点或者最终查到叶子节点时也无法找到目标节点就返回null。这里推荐一个红黑树在线生成的网站
红黑树的插入操作
为了便于接下来对插入过程的理解，我们来看一下插入节点的叫法，下图所示：
红黑树插入操作可以拆分成两部分，一是查找插入的位置，二是插入后如果影响到了红黑树需要满足的条件，那么就需要做一些变换操作，也就是我们一开始接触红黑树这种数据结构时经常听到的树的左旋和右旋操作以及对节点进行变色。
- 左旋：选中某个节点作为旋转节点，旋转节点的右子节点将会变成旋转节点的父节点，旋转节点的左子节点继续保持不变，但右子节点的左子节点则会变成旋转节点的右子节点。
- 右旋：选中某个节点作为旋转节点，旋转节点的左子节点将会变成旋转节点的父节点，旋转节点的右子节点继续保持不变，但左子节点的右子节点则会变成旋转节点的左子节点。
- 变色：节点由红节点变成黑节点或者由黑节点变成红节点。
我们来看看下面的图示例，先来看插入节点40时，此时为了满足红黑树的条件需要对节点35左旋，至于为什么需要左旋我们下面会谈到，可以看到，左旋会将旋转节点35的右子节点38反过来变成了旋转节点35的父节点，因为此时旋转节点35变成了节点38的子节点，而节点38又本身有左右子节点的话，那么肯定要把节点38的左子节点挂到旋转节点35的右子树上(这个左子节点满足比旋转节点35大，比节点38小)。再来看看插入节点3时，需要将节点9作为旋转节点进行右旋，这个跟左旋是同理的，就不过多介绍了。这里补充一下，对于怎么左旋怎么右旋，可以把旋转节点跟其父节点的连线先断开，然后把旋转节点看成时钟上的时针，左旋就是逆时针方向转动，右旋就是顺时针方向转动，这样可能会比较好理解。
先来看看查找插入的位置，这个跟我们上面提到红黑树的查找操作区别不大，首先也是从根节点开始查找，如果根节点为空，说明这是一条空树，那么就把插入节点插入，并把节点的颜色设为黑色即可；如果根节点不为空，那就开始按照查找操作进行匹配，如果在匹配过程的路径中找到了某个节点与插入节点相同，说明要插入的节点已经存在红黑树中了，那么就只需要把那个节点的value值更新成插入节点的value值即可，不需要做其它处理。
如果查找到null节点都没发现该节点的存在，那么就要在这个null节点插入这个红节点了，此时有很多种情况，有些不需要处理，直接插入即可，有些则是需要做出左旋、右旋和变色操作使红黑树重新满足平衡，插入的各种情况如下图所示，我们再对每种情况进行分析和变换，重新构建红黑树的平衡，这里有一个思想，那就是当每颗子树都满足平衡条件时，那么整棵树一定是平衡的。
插入情景1、插入情景2
这两个很容易理解，就不需要做过多的分析了
插入情景3
因为插入的是红节点，而父节点是黑节点的话，插入进去不会对红黑树的平衡条件有任何的影响，所以可以直接插入即可
插入情景4
情景4是插入节点的父节点(P)是红节点，叔节点(U)也是红节点，根据上面说到的红黑树平衡条件的第3点(红节点的子节点不能是红节点)，说明插入节点的祖父节点(PP)一定是黑节点了，此时只需要把插入节点的父节点(P)和叔节点(U)都变成黑色，把祖父节点(PP)变成红色，此时处理后的祖父节点的这条子树是平衡的，但因为祖父节点(PP)变红了，需要自下而上继续处理，需要把祖父节点(PP)当成新的插入节点，重复红黑树的插入情景处理，从而达到满足整颗红黑树的平衡。
这里有一种情况比较特殊，那就是当祖父节点(PP)是根节点时需要继续保持黑色，因为根据红黑树平衡条件第2点(红黑树的根节点是黑节点)，就不需要再把祖父节点(PP)当成新的插入节点继续做插入情景的处理了，此时，黑节点层数增加了，这也是插入操作的各种情景处理中唯一会增加黑节点层数的插入情况了。
我们来看看下面的图示例，当插入红节点100时，因为它的父节点99和叔节点85都是红节点，那么需要先把父节点99和叔节点85都变成黑色，把祖父节点90变成红色，此时把红色的祖父节点90变成新的插入节点，继续按照我们的插入情景处理，因为此时新的红色插入节点90的父节点78是黑节点，那么按照按照情景3，直接插入，不需要再做其它的操作处理了。
插入情景5
情景5的插入情形是当插入节点的父节点(P)是红节点、叔叔节点(U)不存在或为黑节点、插入节点是其父节点(P)的左子节点以及插入节点的父节点(P)是祖父节点(PP)的左子节点。
插入节点前，因为插入节点的父节点(P)是红节点，叔节点(U)非红则一定是叶子节点(null节点)，因为只有这种情况才满足上面说到的红黑树的平衡条件5；插入节点后，对于插入节点的祖父节点(PP)来说，有一边的子树的节点肯定多了，需要做出一些旋转变色的处理了，把节点多的子树通过旋转把一些节点匀给另一边的子树，因为这样才能继续保证插入后满足红黑树的平衡条件。接下来的情景6、情景7和情景8三种情况其实都跟这里的分析一样，就不再做出过多的说明了。
我们来看看下面的图示例，当插入红节点25时，因为它的父节点30是红节点，叔叔节点是个null节点，插入节点25是父节点30的左子节点，而父节点30又是祖父节点38的左子节点，此时对祖父节点38进行右旋，然后将父节点30变成黑色，把祖父节点38变成红色，这样就能在此情景下插入节点后继续保持红黑数的平衡了。
插入情景6
情景6的插入情形是当插入节点的父节点(P)是红节点、叔叔节点(U)不存在或为黑节点、插入节点是其父节点(P)的右子节点以及插入节点的父节点(P)是祖父节点(PP)的左子节点时。
此时需要先对父节点(P)进行左旋，然后会看到通过左旋操作后转换成了情景5的情况，接着我们再把父节点(P)当做新的插入节点，执行情景5的操作即可满足此情景下插入后的平衡。
我们来看看下面的图示例，当插入节点35时，因为它的父节点30是红节点，叔叔节点是个null节点，插入节点35是父节点30的右子节点，而父节点30又是祖父节点38的左子节点，此时对父节点30先进行左旋操作，经过左旋后的情况可以看到跟情景5是一样的，只需要把父节点30当做新的插入节点来看，再执行情景5的平衡步骤即可完成红黑树的平衡。
插入情景7
情景7的插入情形是插入节点的父节点(P)是红节点、叔叔节点(U)不存在或为黑节点、插入节点是其父节点(P)的右子节点以及插入节点的父节点(P)是祖父节点(PP)的右子节点。
这种插入情景跟情景5的情况正好相反了，所以我们也只需将旋转方向改变了即可，即对祖父节点(PP)进行左旋，然后再将父节点(P)设为黑色，将祖父节点(PP)设为红色。
我们来看看下面的图示例，当插入节点45时，因为它的父节点38是红节点，叔叔节点是个null节点，插入节点45是父节点38的右子节点，而父节点38又是祖父节点35的右子节点，此时对祖父节点35进行左旋操作，然后将父节点38变成黑色，把祖父节点35变成红色，这样就能在此插入情景下保持红黑数的平衡了。
插入情景8
情景8的插入情形是插入节点的父节点(P)是红节点、叔叔节点(U)不存在或为黑节点、插入节点是其父节点(P)的左子节点以及插入节点的父节点(P)是祖父节点(PP)的右子节点。
这种情况刚好跟插入情景6的情形相反，我们也只需改变旋转方向改变了即可，也就是先对父节点(P)进行右旋，然后会看到通过右旋操作后转换成了情景7的情况，然后我们再把父节点(P)当做新的插入节点，执行情景7的操作即可满足此情景下插入后的平衡。
我们来看看下面的图示例，当插入节点36时，因为它的父节点38是红节点，叔叔节点是个null节点，插入节点36是父节点38的左子节点，而父节点38又是祖父节点35的右子节点，此时对父节点38先进行右旋操作，经过右旋后的情况可以看到跟情景7是一样的，只需要把父节点38当做新的插入节点来看，再执行情7的平衡步骤即可完成红黑树的平衡。
好了，红黑书的插入情景到此就分析完了，可能刚开始看起来感觉插入情景好多，有点摸不着头脑，比较难分析插入时到底是哪种插入情景，需要使用哪些操作才能实现插入后保持红黑树的平衡，这里我提供了一个简单总结的插入情况图，可以供大家简单理解和记忆，其中，下边表格中的类型表示的是从祖父节点(PP)看起，节点位于父节点的什么位置，举个类型左左的例子，说的是父节点(P)在祖父节点(PP)的左边，插入节点在父节点(P)的左边。
红黑树的删除操作
为了便于接下来对删除过程的理解，我们来看一下删除节点的加法，下图所示：
删除操作相比于插入操作来说稍微复杂一些，一开始还是先进行红黑树的查找操作，如果最终没有查到，说明红黑树没有这个要删除的节点，那么就不需要进行处理了，如果找到了节点，那么就需要将这个节点从红黑树中删除。
但是删除操作最终都可以看做删除的是叶子节点。因为无论删除红黑树任何位置上的元素(如果本身就是叶子节点，那就直接删除，然后进行平衡处理)，最后都可以找到一个叶子节点来替代删除节点的位置，并让它的颜色改成和删除节点的颜色一致，这样一来就相当于删除的是叶子节点了。其实这个叶子节点是真正需要删除的那个节点的前继节点，或者后继节点。通过这样的处理，红黑树的删除操作的情形就会少很多了，也会比较好处理删除节点后的红黑树再平衡。
- 前继节点：简单来说就是删除节点的左子树中最大的节点，其实就是删除节点的左子树中最右边的那个节点
- 后继节点：简单来说就是删除节点的右子树中最小的节点，其实就是删除节点的左子树中最左边的那个节点
看看下面的图示例，这里先从小到大打印了红黑树的值，比如我们要删除根节点16，可以看到节点16的前后节点分别是节点9和节点35，这两个节点就是删除节点16的前继节点和后继节点，这边删除根节点16之后会用前继节点9来替代节点16的位置，并把节点9的颜色改成跟删除节点颜色一致，也就是由红节点变成了黑节点，此时可以看到删除节点16就是相当于删除的是叶子节点9，这里因为节点9是红节点，删除位置后不会影响红黑树的平衡，所以不需要进行红黑树的再平衡处理。
如果最终替代删除的那个前继节点或者后继节点(又或者删除节点本身就是叶子节点)是黑节点的话，那删除这个替代节点位置后肯定会影响到红黑树的平衡的，此时肯定就需要对红黑树进行再平衡操作了，删除的各种情况如下图所示，我们再对每种删除情况进行分析和变换，重新构建红黑树的平衡。
这里注意一下，因为删除某个节点最后都可以替换成删除的是叶子节点的位置，下面的图中删除节点表示的是最终删除的那个叶子节点位置，也就是替代节点，不是表示实际删除的节点，这个实际删除的节点最终会被删除掉，只是这个实际删除的节点位置会被替代的叶子节点顶上，颜色也会改成和删除节点一样，相当于根本就没动到实际删除的节点位置，只是把值给替换掉了。
这里还有个思想，就是删除了某个黑色叶子节点，如果它的兄弟节点有红节点存在的话，那就利用这个兄弟的红节点通过旋转变色补充到删除节点的那条子树上。但是如果不存在的话，那就从下往上交给父辈们去处理了。
删除情景1：
叶子节点是红节点的删除不会对红黑树的平衡产生影响，直接删除即可。但有个情况需要注意，就是这个红节点不是叶子节点，只是在经过其它删除情景操作之后需要从下往上继续进行删除情景处理的节点，此时就不能把红节点删除，而是把它的颜色改成黑色。
这个删除情景可以参考上面的那个图例，删除节点16相当于删除叶子节点9，叶子节点9是红节点，它的消失不会对红黑树平衡有影响。
删除情景2：
情景2的删除情形是删除节点是黑节点删除节点是其父节点的右子节点(其实就是前继节点)、删除节点的兄弟节点是黑节点以及删除节点的兄弟节点的左子节点是红节点，右子节点任意颜色。
我们来看看下面的图例，删除节点50时，找到节点50的前继节点40，并把节点40替换到节点50的位置，此时相当于删除的是叶子节点40，此时的兄弟节点10又有左红子节点8，那么就可以对父节点25进行右旋，然后把兄弟节点10的颜色设为父节点25的颜色，也就是红色，最后再将父节点25的颜色设为黑色，把兄弟节点10的左子节点8设为黑色，此时就可以保持红黑树的再平衡。
删除情景3：
情景3的删除情形是删除节点是黑节点、删除节点是其父节点的右子节点(其实就是前继节点)、删除节点的兄弟节点是黑节点以及删除节点的兄弟节点的左子节点是黑节点(非红即黑，null节点也是黑节点)，右子节点是红节点。
我们来看看下面的图例，删除节点25时，找到节点25的前继节点20，并把节点20替换到节点25的位置，此时相当于删除的是叶子节点20，此时的兄弟节点7有右红子节点8，那么就可以对兄弟节点7进行左旋，左旋后把兄弟节点的右子节点8的颜色设为黑色，把兄弟节点设为红色，此时就得到了删除情景2的情形，继续执行情景2的步骤就可以保持红黑树的再平衡。
删除情景4：
情景4的删除情形是删除节点是黑节点、删除节点是其父节点的右子节点(其实就是前继节点)、删除节点的兄弟节点是黑节点以及删除节点的兄弟节点的左右子节点是黑节点(非红即黑，null节点也是黑节点)。
我们来看看下面的图例，删除节点25时，找到节点25的前继节点20，并把节点20替换到节点25的位置，此时相当于删除的是叶子节点20，此时的兄弟节点7的左右子节点非红即为黑节点，所以先将兄弟节点7设为红色，然后把父节点15当做是新的删除节点来看待，此时在下面图例新的删除节点的情况刚好符合删除情景7的条件，那就继续执行情景7的处理来达到红黑树的再平衡。
删除情景5：
情景5的删除情形是删除节点是黑节点、删除节点是其父节点的右子节点(其实就是前继节点)以及删除节点的兄弟节点是红节点。
我们来看看下面的图例，当删除节点40时，它的兄弟节点15是红节点，那就先对父节点25进行右旋，然后将兄弟节点15改为黑色，将父节点25改成红色，此时会得到情景4的情况，执行情景4的操作，在这里也就是将节点20设为红色，把节点25看成新的删除节点来看待，此时节点25因为是红节点，根据删除情景1的处理，只需要把节点25设为黑色即可。
删除情景6：
情景6的删除情形是删除节点是黑节点、删除节点是其父节点的左子节点(其实就是后继节点)、删除节点的兄弟节点是黑节点以及删除节点的兄弟节点的右子节点是红节点，左子节点任意颜色。
我们来看看下面的图例，删除节点75时，此时的兄弟节点90是黑节点又有右红子节点95，那么就可以对父节点78进行左旋，然后把兄弟节点90的颜色设为父节点78的颜色，也就是黑色，最后再将父节点78的颜色设为黑色，把兄弟节点90的右子节点95设为黑色，此时就可以保持红黑树的再平衡。
删除情景7：
情景7的删除情形是删除节点是黑节点、删除节点是其父节点的左子节点(其实就是后继节点)、删除节点的兄弟节点是黑节点以及删除节点的兄弟节点的右子节点是黑节点(非红即黑，null节点也是黑节点)，左子节点是红节点。
我们来看看下面的图例，删除节点75时，此时的兄弟节点90有左红子节点85，右子节点非红即是黑节点，那么可以先对兄弟节点90进行右旋，右旋后把兄弟节点的左子节点85的颜色设为黑色，把兄弟节点90设为红色，此时就得到了删除情景6的情形，继续执行情景6的步骤就可以保持红黑树的再平衡。
删除情景8：
情景8的删除情形是删除节点是黑节点、删除节点是其父节点的左子节点(其实就是后继节点)、删除节点的兄弟节点是黑节点以及删除节点的兄弟节点的左右子节点是黑节点(非红即黑，null节点也是黑节点)。
我们来看看下面的图例，删除节点78时，此时的兄弟节点90的左右子节点非红即为黑节点，所以先将兄弟节点90设为红色，然后把父节点85当做是新的删除节点来看待，此时在下面图例新的删除节点的情况刚好符合删除情景4的条件，那就继续执行情景4的处理来达到红黑树的再平衡。
删除情景9：
情景9的删除情形是删除节点是黑节点、删除节点是其父节点的左子节点(其实就是后继节点)以及删除节点的兄弟节点是红节点。。
我们来看看下面的图例，当删除节点78时，它的兄弟节点100是红节点，那就先对父节点85进行左旋，然后将兄弟节点100改为黑色，将父节点85改成红色，此时会得到情景8的情况，执行情景8的操作，在这里也就是将节点90设为红色，把节点85看成新的删除节点来看待，此时节点85因为是红节点，根据删除情景1的处理，只需要把节点85设为黑色即可。
总结
总算写完了，如果深入理解了红黑树的实现原理和各种情况下的平衡处理，那么接下来就是按部就班的用代码去实现了。希望这篇文章对你有帮助，如果文章写的不对或者在叙述上有问题的地方，欢迎指出交流。
世界因交流而进步，因分享而美好。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/125069.html原文链接：https://javaforall.cn
