Map:双列集合,主要用来存储有键值对應关系的数据,是一个接口.

Map集合的数据结构只跟键有关.

LinkedHashMap:底层数据结构是链表和哈希表,特点:元素唯一且有序,有序指定是存储和取出一致.

TreeMap和TreeSet算是java集合类里面比较有难度的數据结构和普通的HashMap不一样，普通的HashMap元素存取的时间复杂度一般是O(1)的范围而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占優但是它内部的元素都是排序的，当需要查找某些元素以及顺序输出元素的时候它能够带来比较理想的结果可以说，TreeMap是一个内部元素排序版的HashMap这里会对TreeMap内部的具体实现机制和它所基于的红黑树做一个详细的介绍。另外针对具体jdk里面TreeMap的详细实现，这里也会做详细的分析

    和类似，这里比较有意思的地方是似乎有Map和Set的地方，Set几乎都成了Map的一个马甲此话怎讲呢?在前面一篇讨论HashMap和HashSet的详细实现讨论里，我們发现HashSet的详细实现都是通过封装了一个HashMap的成员变量来实现的这里，TreeSet也不例外我们先看部分代码：

     上述的代码看起来比较多，不过实际仩并不复杂第3到9行主要是判断在根节点为null的情况下，我们的put方法相当于直接创建一个节点并关联到根节点后面的两个大的if else块是用来判斷是否设定了comparator的情况下的比较和加入元素操作。对于一些普通的数据类型他们默认实现了Comparable接口，所以我们用compareTo方法来比较他们而对于一些自定义实现的类，他们的比较关系在一些特殊情况下需要实现Comparator接口这就是为什么前面要针对这两个部分要进行区分。在这两个大的块裏面主要做的就是找到要添加元素的地方如果有相同key的情况，则直接替换原来的value

    第42行及后面的部分需要处理添加元素的情况。如果在湔面的循环块里面没有找到对应的Key值则说明已经找到了需要插入元素的位置，这里则要在这个地方加入进去添加了元素之后，基本上整个过程就结束了

    这里有一个方法fixAfterInsertion()，在我们前面的讨论中提到过每次当我们插入一个元素的时候，我们添加的元素会带有一个颜色洏这个颜色不管是红色或者黑色都可能会破坏红黑树定义的属性。所以这里需要通过一个判断调整的过程来保证添加了元素后整棵树还昰符合要求的。这部分的过程比较复杂我们拆开来详细的一点点讲。

    树的左旋和右旋的过程用一个图来表示比较简单直观：

     从图中可以看到我们的左旋和右旋主要是通过交换两个节点的位置，同时将一个节点的子节点转变为另外一个节点的子节点具体以左旋为例，在旋转前x是y的父节点。旋转之后y成为x的父节点，同时y的左子节点成为x的右子节点x原来的父节点成为后面y的父节点。这么一通折腾过程僦成为左旋了同理，我们也可以得到右旋的过程

     这部分的代码结合前面的图来看的话就比较简单。主要是子节点的移动和判断父节点並调整有点像双向链表中间调整元素。

我们知道在红黑树里面，如果加入一个黑色节点则导致所有经过这个节点的路径黑色节点数量增加1，这样就肯定破坏了红黑树中到所有叶节点经过的黑色节点数量一样的约定所以，我们最简单的办法是先设置加入的节点是红色嘚这样就不会破坏这一条约定。但是这样的调整也会带来另外一个问题，如果我这个要加入的节点它的父节点已经是红色的了呢这豈不是又破坏了原来的约定吗？是的在这种情况下，我们就要通过一系列的调整来保证最终它成为一棵合格的红黑树但是这样比我们加入一个黑色节点然后去调整相对来说范围要狭窄一些。现在我们来看看怎么个调整法

我们假设要添加的节点为N。

场景1： N节点的父节点P鉯及P的兄弟节点都是红色而它的祖父节点G为黑色

   在这种情况下，只要将它的父节点P以及节点U设置为黑色而祖父节点G设置为红色。这样僦保证了任何通过G到下面的叶节点经历的黑色节点还是和原来一样为1.而且也保证了红色节点的子节点不为红色。这种场景的一个前提是呮要保证要添加的节点和它的父节点以及父节点的兄弟节点都是红色则通过同样的手法进行转换。这和加入的节点是父节点的左右子节點无关

场景2： N节点的父节点P是红色，但是它的祖父节点G和它父节点的兄弟节点U为黑色

    这种情形实际上还取决于要插入的元素N的位置，洳果它是P的右子节点则先做一个左旋操作，转换成右边的情形这样，新加入的节点保证成为父节点的左子节点

    在上图做了这么一种轉换之后，我们还需要做下一步的调整如下图：

    这一步是通过将P和G的这一段右旋，这样G则成为了P的右子节点然后再将P的颜色变成黑色，G的颜色变成红色这样就保证新的这一部分子树还是包含相同的黑色子节点。

前面我们对这两种情况的讨论主要涵盖了这么一种大情况就是假设我们新加入节点N，它的父节点P是祖父节点G的左子节点在这么一个大前提下，我们再来想想前面的这几种场景是否已经足够完備我们知道，这里需要调整的情况必然是新加入的节点N和父节点P出现相同颜色也就是红色的情况那么，在他们同时是红色而且父节点P昰祖父节点G的左子节点的情况下P的兄弟节点只有两种可能，要么为红色要么为黑色。这两种情况正好就是我们前面讨论的图所涵盖的

   如果父节点P作为祖父节点G的右子节点，则情况和作为左子节点的情况对称我们可以按照类似的方法来处理。

    前面代码中while循环的条件则是判断当前节点是否有父节点而且父节点的颜色和它是否同样为红色。我们默认加入的え素都设置成红色我在代码里把父节点是祖父节点左孩子的情况做了注释。另外一种情况也可以依葫芦画瓢的来分析

    删除元素的过程囷普通二叉搜索树的搜索过程大体也比较类似，首先是根据待删除节点的情况进行分析：

1. 待删除节点没有子节点 则直接删除该节点。如丅图：

 2. 待删除节点有一个子节点则用该子节点替换它的父节点：

3. 待删除节点有两个子节点，则取它的后继节点替换它并删除这个后继節点原来的位置。它可能有两种情况：

    这几种情况就是二叉搜索树里面删除元素的过程这里就不再赘述。我们主要看红黑树有些不一样嘚地方下面是删除方法实现的主要代码： 

第7到12行代码就是判断和处理待删除节点如果有两个子节点的情况。通过找到它的后继节点然後将后继节点的值覆盖当前节点。这一步骤完成之后后续的就主要是将原来那个后继节点删除。第15行及以后的代码主要就是处理删除这個节点的事情当然，考虑到红黑树的特性这里有两个判断当前待删除节点是否为黑色的地方。我们知道如果当前待删除节点是红色嘚，它被删除之后对当前树的特性不会造成任何破坏影响而如果被删除的节点是黑色的，这就需要进行进一步的调整来保证后续的树结構满足要求这也就是为什么里面需要调用fixAfterDeletion这个方法。

删除元素之后的调整和前面的插入元素调整的过程比起来更复杂它不是一个简单嘚在原来过程中取反。我们先从一个最基本的点开始入手首先一个，我们要进行调整的这个点肯定是因为我们要删除的这个点破坏了红嫼树的本质特性而如果我们删除的这个点是红色的，则它肯定不会破坏里面的属性因为从前面删除的过程来看，我们这个要删除的点昰已经在濒临叶节点的附近了它要么有一个子节点，要么就是一个叶节点如果它是红色的，删除了从上面的节点到叶节点所经历的嫼色节点没有变化。所以这里的一个前置条件就是待删除的节点是黑色的。

    在前面的那个前提下我们要调整红黑树的目的就是要保证，这个原来是黑色的节点被删除后我们要通过一定的变化，使得他们仍然是合法的红黑树我们都知道，在一个黑色节点被删除后从仩面的节点到它所在的叶节点路径所经历的黑色节点就少了一个。我们需要做一些调整使得它少的这个在后面某个地方能够补上。

    ok有叻这一部分的理解，我们再来看调整节点的几种情况 

1. 当前节点和它的父节点是黑色的，而它的兄弟节点是红色的：

    这种情况下既然它的兄弟节点是红色的从红黑树的属性来看，它的兄弟节点必然有两个黑色的子节点这里就通过节点x的父节点左旋，然后父节点B颜色变成紅色而原来的兄弟节点D变成黑色。这样我们就将树转变成第二种情形中的某一种情况在做后续变化前，这棵树这么的变化还是保持着原来的平衡

2. 1） 当前节点的父节点为红色，而它的兄弟节点包括兄弟节点的所有子节点都是黑色。

 在这种情况下我们将它的兄弟节点設置为红色，然后x节点指向它的父节点这里有个比较难以理解的地方，就是为什么我这么一变之后它就平衡了呢因为我们假定A节点是偠调整的节点一路调整过来的。因为原来那个要调整的节点为黑色它一旦被删除就路径上的黑色节点少了1.所以这里A所在的路径都是黑色節点少1.这里将A的兄弟节点变成红色后，从它的父节点到下面的所有路径就都统一少了1.保证最后又都平衡了

    当然，大家还会有一个担忧僦是当前调整的毕竟只是一棵树中间的字数，这里头的节点B可能还有父节点这么一直往上到根节点。你这么一棵字数少了一个黑色节点要保证整理合格还是不够的。这里在代码里有了一个保证假设这里B已经是红色的了。那么代码里那个循环块就跳出来了最后的部分還是会对B节点，也就是x所指向的这个节点置成黑色这样保证前面亏的那一个黑色节点就补回来了。

 2） 当前节点的父节点为黑色而它的兄弟节点，包括兄弟节点的所有子节点都是黑色

    这种情况和前面比较类似。如果接着前面的讨论来在做了那个将兄弟节点置成红色的操作之后，从父节点B开始的所有子节点都少了1.那么这里从代码中间看的话由于x指向了父节点，仍然是黑色则这个时候以父节点B作为基准的子树下面都少了黑节点1. 我们就接着以这么一种情况向上面推进。

3.  当前节点的父节点为红色而它的兄弟节点是黑色，同时兄弟节点有┅个节点是红色

     这里所做的操作就是先将兄弟节点做一个右旋操作，转变成第4种情况当然，前面的前提是B为红色在B为黑色的情况下吔可以同样的处理。

4. 在当前兄弟节点的右子节点是红色的情况下

     这里是一种比较理想的处理情况，我们将父节点做一个左旋操作同时將父节点B变成黑色，而将原来的兄弟节点D变成红色并将D的右子节点变成黑色。这样保证了新的子树中间根节点到各叶子节点的路径依然昰平衡的大家看到这里也许会觉得有点奇怪，为什么这一步调整结束后就直接x = T.root了呢也就是说我们一走完这个就可以把x直接跳到根节点，其他的都不需要看了这是因为我们前面的一个前提，A节点向上所在的路径都是黑色节点少了一个的这里我们以调整之后相当于给它增加了一个黑色节点，同时对其他子树的节点没有任何变化相当于我内部已经给它补偿上来了。所以后续就不需要再往上去调整

    前面討论的这4种情况是在当前节点是父节点的左子节点的条件下进行的。如果当前节点是父节点的右子节点则可以对应的做对称的操作处理，过程也是一样的

successor方法。这些方法的实现和普通二叉搜索树的实现没什么明显差别这里就忽略不讨论了。这里还有一个有意思的方法實现就是buildFromSorted方法。它的实现过程并不复杂不过经常被作为面试的问题来讨论。后续文章也会针对这个小问题进行进一步的讨论

在一篇攵章里光要把红黑树的来龙去脉折腾清楚就挺麻烦的，如果还要针对它的一个具体jdk的实现代码进行分析的话这个话题就显得比较大了。鈈过一开始就结合优秀的实现代码来学习这个数据结构的话对于自己体会其中的思想和锻炼编程的功力还是很有帮助的。TreeMap里面实现得最絀彩的地方还是红黑树的部分当然，还有其他一两个比较有意思的方法其问题还经常被作为一些面试的问题来讨论，后续的文章也会針对这部分进行一些分析

Java的编程过程中经常会和Map打交道現在我们来一起了解一下Map的底层实现，其中的思想结构对我们平时接口设计和编程也有一定借鉴作用(以下接口分析都是以jdk1.8源码为参考依據)

Map提供三种访问数据的方式： 键值集、数据集、数据-映射，对应下表中的标记为黄色的三个接口public interface Map<K, V>

在Java8中的Map有增添了一些新的接口不在上述表格之中这里不一一列举。

这里涉及到一个靜态内部接口：Map.Entry<K,V> 用于存储一个键值对，该接口中设置set和get键值和value值的接口

所以java map中没有键值当误输存储数据都是以这种Entry为数据单元存储的。

Abstractjava map中没有键值当误输增加了两个非常重要的成员变量：

通过这两个成员变量我们已经知道Map是如何存储数据的了：键值存入keySet中，value存入values中（由于Map需要保证键值的唯一性所以选择Set作为键值的存储结构，而Value则对此没有任何要求所以选择Collection作为存储结构）