Java集合详解6：这次，从头到尾带你解读Java中的红黑树
《Java集合详解系列》是我在完成夯实Java基础篇的系列博客后准备开始写的新系列。
这些文章将整理到我在GitHub上的《Java面试指南》仓库，更多精彩内容请到我的仓库里查看
https://github.com/h4pl/Java-Tutorial
喜欢的话麻烦点下Star、fork哈
文章首发于我的个人博客：
什么是红黑树www.how2playlife.com
首先，什么是红黑树呢？ 红黑树是一种“平衡的”二叉查找树，它是一种经典高效的算法，能够保证在最坏的情况下动态集合操作的时间为O（lgn）。红黑树每个节点包含5个域，分别为color,key,left,right和p。 color是在每个节点上增加的一个存储位表示节点的颜色，可以是RED或者BLACK。key为结点中的value值，left,right为该结点的左右孩子指针，没有的话为NIL，p是一个指针，是指向该节的父节点。如下图（来自维基百科）表示就是一颗红黑树，NIL为指向外结点的指针。（外结点视为没有key的结点）
红黑树有什么性质呢？一般称为红黑性质，有以下五点： 1）每个结点或者是红的或者是黑的； 2）根结点是黑的； 3）每个叶结点（NIL）是黑的； 4）如果一个结点是红的，则它的两个孩子都是黑的； 5）对每个结点，从该结点到其他其子孙结点的所有路径上包含相同数目的黑结点。 为了后面的分析，我们还得知道以下知识点。（1）黑高度：从某个结点x出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度。（2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。 （内结点视为红黑树中带关键字的结点）（3）包含n个内部节点的红黑树的高度是 O(log(n))。红黑树是特殊的二叉查找树，又名R-B树(RED-BLACK-TREE)，由于红黑树是特殊的二叉查找树，即红黑树具有了二叉查找树的特性，而且红黑树还具有以下特性：
1.每个节点要么是黑色要么是红色
2.根节点是黑色
3.每个叶子节点是黑色，并且为空节点(还有另外一种说法就是，每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。)
4.如果一个节点是红色，则它的子节点必须是黑色
5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
有几点需要注意的是：
1.特性3中指定红黑树的每个叶子节点都是空节点，但是在Java实现中红黑树将使用null代表空节点，因此遍历红黑树时看不到黑色的叶子节点，反而见到的叶子节点是红色的
2.特性4保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍，例如黑色高度为3的红黑树，其最短路径(路径指的是根节点到叶子节点)是2(黑节点-黑节点-黑节点)，其最长路径为4(黑节点-红节点-黑节点-红节点-黑节点)。
实践红黑树操作插入操作首先红黑树在插入节点的时，我们设定插入节点的颜色为红色,如果插入的是黑色节点，必然会违背特性5，即改变了红黑树的黑高度，如下插入红色结点又存在着几种情况：
1.黑父
如图所示，这种情况不会破坏红黑树的特性，即不需要任何处理
2.红父
当其父亲为红色时又会存在以下的情况
红叔红叔的情况，其实相对来说比较简单的，如下图所示，只需要通过修改父、叔的颜色为黑色，祖的颜色为红色，而且回去递归的检查祖节点即可
黑叔黑叔的情况有如下几种，这几种情况下是不能够通过修改颜色达到平衡的效果，因此会通过旋转的操作，红黑树种有两种旋转操作，左旋和右旋(现在存在的疑问，什么时候使用到左旋，什么时候使用到右旋)
Case 1:[先右旋，在改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点Case 2:[先左旋变成Case1中的情况，再右旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点Case 3:[先左旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点Case 4:[先右旋变成Case 3的情况，再左旋，最后改变颜色(根节点必须为黑色，其两个子节点为红色，叔节点不用改变)],如下图所示，注意省略黑哨兵节点以上就是红黑树新增节点所有可能的操作，下面会介绍红黑树中的删除操作
删除操作删除操作相比于插入操作情况更加复杂，删除一个节点可以大致分为三种情况：
1.删除的节点没有孩子节点，即当前节点为叶子节点，这种可以直接删除
2.删除的节点有一个孩子节点，这种需要删除当前节点，并使用其孩子节点顶替上来
3.删除的节点有两个孩子节点，这种需要先找到其后继节点(树中大于节点的最小的元素);然后将其后继节点的内容复制到该节点上，其后继节点就相当于该节点的替身， 需要注意的是其后继节点一定不会有两个孩子节点(这点应该很好理解，如果后继节点有左孩子节点，那么当前的后继节点肯定不是最小的，说明后继节点只能存在没有孩子节点或者只有一个右孩子节点)，即这样就将问题转换成为1,2中的方式。
在讲述修复操作之前，首先需要明白几点，
1.对于红黑树而言，单支节点的情况只有如下图所示的一种情况，即为当前节点为黑色，其孩子节点为红色,(1.假设当前节点为红色，其两个孩子节点必须为黑色，2.若有孙子节点，则必为黑色，导致黑子数量不等，而红黑树不平衡)
2.由于红黑树是特殊的二叉查找树，它的删除和二叉查找树类型，真正的删除点即为删除点A的中序遍历的后继(前继也可以)，通过红黑树的特性可知这个后继必然最多只能有一个孩子，其这个孩子节点必然是右孩子节点，从而为单支情况(即这个后继节点只能有一个红色孩子或没有孩子)
下面将详细介绍，在执行删除节点操作之后，将通过修复操作使得红黑树达到平衡的情况。
Case 1:被删除的节点为红色，则这节点必定为叶子节点(首先这里的被删除的节点指的是真正删除的节点，通过上文得知的真正删除的节点要么是节点本身，要么是其后继节点，若是节点本身则必须为叶子节点，不为叶子节点的话其会有左右孩子，则真正删除的是其右孩子树上的最小值，若是后继节点，也必须为叶子节点，若不是则其也会有左右孩子，从而和2中相违背)，这种情况下删除红色叶节点就可以了，不用进行其他的操作了。Case 2:被删除的节点是黑色，其子节点是红色，将其子节点顶替上来并改变其颜色为黑色，如下图所示Case 3:被删除的节点是黑色，其子节点也是黑色，将其子节点顶替上来，变成了双黑的问题，此时有以下情况
Case 1:新节点的兄弟节点为红色，此时若新节点在左边则做左旋操作，否则做右旋操作，之后再将其父节点颜色改变为红色，兄弟节点从图中可以看出，操作之后红黑树并未达到平衡状态，而是变成的黑兄的情况
Case 2:新节点的兄弟节点为黑色,此时可能有如下情况
红父二黑侄：将父节点变成黑色，兄弟节点变成红色，新节点变成黑色即可,如下图所示黑父二黑侄：将父节点变成新节点的颜色，新节点变成黑色，兄弟节点染成红色，还需要继续以父节点为判定点继续判断,如下图所示红侄：情况一:新节点在右子树，红侄在兄弟节点左子树，此时的操作为右旋，并将兄弟节点变为父亲的颜色，父亲节点变为黑色，侄节点变为黑色，如下图所示
情况二:新节点在右子树，红侄在兄弟节点右子树，此时的操作为先左旋，后右旋并将侄节点变为父亲的颜色，父节点变为黑色，如下图所示
情况三：新节点在左子树，红侄在兄弟节点左子树,此时的操作为先右旋在左旋并将侄节点变为父亲的颜色，父亲节点变为黑色，如下图所示
情况四：新节点在右子树，红侄在兄弟节点右子树,此时的操作为左旋，并将兄弟节点变为父节点的颜色，父亲节点变为黑色，侄节点变为黑色，如下图所示
红黑树实现如下是使用JAVA代码实现红黑树的过程，主要包括了插入、删除、左旋、右旋、遍历等操作
插入/* 插入一个节点 * @param node */private void insert(RBTreeNode<T> node){ int cmp; RBTreeNode<T> root=this.rootNode; RBTreeNode<T> parent=null; //定位节点添加到哪个父节点下 while(null !=root){ parent=root; cmp=node.key.compareTo(root.key); if (cmp < 0){ root=root.left; } else { root=root.right; } } node.parent=parent; //表示当前没一个节点，那么就当新增的节点为根节点 if (null==parent){ this.rootNode=node; } else { //找出在当前父节点下新增节点的位置 cmp=node.key.compareTo(parent.key); if (cmp < 0){ parent.left=node; } else { parent.right=node; } } //设置插入节点的颜色为红色 node.color=COLOR_RED; //修正为红黑树 insertFixUp(node);}/** * 红黑树插入修正 * @param node */private void insertFixUp(RBTreeNode<T> node){ RBTreeNode<T> parent,gparent; //节点的父节点存在并且为红色 while( ((parent=getParent(node)) !=null) && isRed(parent)){ gparent=getParent(parent); //如果其祖父节点是空怎么处理 // 若父节点是祖父节点的左孩子 if(parent==gparent.left){ RBTreeNode<T> uncle=gparent.right; if ((null !=uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node=gparent; continue; } if (parent.right==node){ RBTreeNode<T> tmp; leftRotate(parent); tmp=parent; parent=node; node=tmp; } setColorBlack(parent); setColorRed(gparent); rightRotate(gparent); } else { RBTreeNode<T> uncle=gparent.left; if ((null !=uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node=gparent; continue; } if (parent.left==node){ RBTreeNode<T> tmp; rightRotate(parent); tmp=parent; parent=node; node=tmp; } setColorBlack(parent); setColorRed(gparent); leftRotate(gparent); } } setColorBlack(this.rootNode);}插入节点的操作主要分为以下几步：
1.定位：即遍历整理红黑树，确定添加的位置，如上代码中insert方法中就是在找到添加的位置
2.修复：这也就是前面介绍的，添加元素后可能会使得红黑树不在满足其特性，这时候需要通过变色、旋转来调整红黑树，也就是如上代码中insertFixUp方法
删除节点如下为删除节点的代码
private void remove(RBTreeNode<T> node){ RBTreeNode<T> child,parent; boolean color; //被删除节点左右孩子都不为空的情况 if ((null !=node.left) && (null !=node.right)){ //获取到被删除节点的后继节点 RBTreeNode<T> replace=node; replace=replace.right; while(null !=replace.left){ replace=replace.left; } //node节点不是根节点 if (null !=getParent(node)){ //node是左节点 if (getParent(node).left==node){ getParent(node).left=replace; } else { getParent(node).right=replace; } } else { this.rootNode=replace; } child=replace.right; parent=getParent(replace); color=getColor(replace); if (parent==node){ parent=replace; } else { if (null !=child){ setParent(child,parent); } parent.left=child; replace.right=node.right; setParent(node.right, replace); } replace.parent=node.parent; replace.color=node.color; replace.left=node.left; node.left.parent=replace; if (color==COLOR_BLACK){ removeFixUp(child,parent); } node=null; return; } if (null !=node.left){ child=node.left; } else { child=node.right; } parent=node.parent; color=node.color; if (null !=child){ child.parent=parent; } if (null !=parent){ if (parent.left==node){ parent.left=child; } else { parent.right=child; } } else { this.rootNode=child; } if (color==COLOR_BLACK){ removeFixUp(child, parent); } node=null;}/** * 删除修复 * @param node * @param parent */private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent){ RBTreeNode<T> other; //node不为空且为黑色，并且不为根节点 while ((null==node || isBlack(node)) && (node !=this.rootNode) ){ //node是父节点的左孩子 if (node==parent.left){ //获取到其右孩子 other=parent.right; //node节点的兄弟节点是红色 if (isRed(other)){ setColorBlack(other); setColorRed(parent); leftRotate(parent); other=parent.right; } //node节点的兄弟节点是黑色，且兄弟节点的两个孩子节点也是黑色 if ((other.left==null || isBlack(other.left)) && (other.right==null || isBlack(other.right))){ setColorRed(other); node=parent; parent=getParent(node); } else { //node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色 if (null==other.right || isBlack(other.right)){ setColorBlack(other.left); setColorRed(other); rightRotate(other); other=parent.right; } //node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色，左孩子是任意颜色 setColor(other, getColor(parent)); setColorBlack(parent); setColorBlack(other.right); leftRotate(parent); node=this.rootNode; break; } } else { other=parent.left; if (isRed(other)){ setColorBlack(other); setColorRed(parent); rightRotate(parent); other=parent.left; } if ((null==other.left || isBlack(other.left)) && (null==other.right || isBlack(other.right))){ setColorRed(other); node=parent; parent=getParent(node); } else { if (null==other.left || isBlack(other.left)){ setColorBlack(other.right); setColorRed(other); leftRotate(other); other=parent.left; } setColor(other,getColor(parent)); setColorBlack(parent); setColorBlack(other.left); rightRotate(parent); node=this.rootNode; break; } } } if (node!=null) setColorBlack(node);}删除节点主要分为几种情况去做对应的处理：
1.删除节点,按照如下三种情况去删除节点1.真正删除的节点没有子节点2.真正删除的节点有一个子节点3.正在删除的节点有两个子节点2.修复红黑树的特性，如代码中调用removeFixUp方法修复红黑树的特性。3.总结以上主要介绍了红黑树的一些特性，包括一些操作详细的解析了里面的过程，写的时间比较长，感觉确实比较难理清楚。后面会持续的理解更深入，若有存在问题的地方，请指正。
参考文章红黑树(五)之 Java的实现
通过分析 JDK 源代码研究 TreeMap 红黑树算法实现
红黑树
（图解）红黑树的插入和删除
红黑树深入剖析及Java实现
微信公众号Java技术江湖如果大家想要实时关注我更新的文章以及分享的干货的话，可以关注我的公众号【Java技术江湖】一位阿里 Java 工程师的技术小站，作者黄小斜，专注 Java 相关技术：SSM、SpringBoot、MySQL、分布式、中间件、集群、Linux、网络、多线程，偶尔讲点Docker、ELK，同时也分享技术干货和学习经验，致力于Java全栈开发！
Java工程师必备学习资源: 一些Java工程师常用学习资源，关注公众号后，后台回复关键字 “Java” 即可免费无套路获取。
我的公众号个人公众号：黄小斜黄小斜是跨考软件工程的 985 硕士，自学 Java 两年，拿到了 BAT 等近十家大厂 offer，从技术小白成长为阿里工程师。
作者专注于 JAVA 后端技术栈，热衷于分享程序员干货、学习经验、求职心得和程序人生，目前黄小斜的CSDN博客有百万+访问量，知乎粉丝2W+，全网已有10W+读者。
黄小斜是一个斜杠青年，坚持学习和写作，相信终身学习的力量，希望和更多的程序员交朋友，一起进步和成长！关注公众号【黄小斜】后回复【原创电子书】即可领取我原创的电子书《菜鸟程序员修炼手册：从技术小白到阿里巴巴Java工程师》
程序员3T技术学习资源： 一些程序员学习技术的资源大礼包，关注公众号后，后台回复关键字 “资料” 即可免费无套路获取。
?
本文由博客一文多发平台 OpenWrite 发布！
前言
本文源码采用jdk1.8
Java集合是Java提供的工具包，包含了常用的数据结构：集合、链表、队列、栈、数组、映射等。Java集合工具包位置是java.util.*，Java集合主要可以划分为4个部分：List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections)。
原本我是打算先写Collection下的Set集合的，结果看了源码发现：Set集合实际上底层就是HashMap来构建的！
所以，就先介绍Map集合和红黑树吧！
一、Map简介
前面我们学习的Collection叫做集合，它可以快速查找现有的元素。
Map 是一组成对的“键值对”对象，允许使用键 (key) 来查找值 (value)。它提供了一个映射表，可以通过某个对象来查找另一个对象。它也被称作关联数组，因为它将某些对象与另外一些对象关联在一起
Map基本特性：
以 key-value 键值对的形式存储数据，可通过 key 来查找 value键唯一，值不唯一。即一个键只能映射一个值，一个值可以对应多个键无法保证元素的存入顺序映射的模型图是这样的：
那为什么我们需要这种数据存储结构呢？举个例子
生活中，一个身份证号证明一个人的身份，一一对应
下面用红色框框圈住的就是Map值得关注的子类：
这只是集合包下的，是线程不安全的，在并发包下还有线程安全的ConcurrentHashMap，下面我会介绍的~
二、散列表介绍
散列表是一种不在意元素的顺序，能够快速地查找元素的数据结构
散列表为每个对象通过哈希函数计算出一个整数，称为散列码。根据这些计算出来的整数(散列码)保存在对应的位置上！
在Java中，散列表用的是链表数组实现的，每个列表称之为桶。每个桶都可能会出现被别的元素占用的情况，即此时hashCode散列码相同，会存储在同一个位置，这个现象叫散列冲突。
开放寻址：核心思想是如果出现了散列冲突，我们就重新探测一个空闲的位置，开放寻址法解决方案有线性探测法、二次探测、双重散列等方案。链表法：散列表中，每个“桶（bucket）”都会对应一个条链表，在查找时先听过hash(key)找到位置，然后遍历链表找到对应元素三、HashMap介绍
Hashmap定义：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {}Hashmap简介：
HashMap是基于Map接口的Key-Value的集合，允许使用null值和null键，但不保证映射的顺序，特别是它不保证该顺序恒久不变。HashMap在底层将Key-Value当成一个整体Entry来处理。底层使用数组实现，数组中每一项是单向链表，即数组和链表的结合体，链表长度大于一定阈值时，链表转换为红黑树。在链表和数组中可以说是有序的(存储的顺序和取出的顺序是一致的)，但同时也带来缺点：想要获取某个元素便要访问所有的元素直到找到为止（List中知道具体位置可以直接访问）。散列表HashMap会为每一个Key计算出哈希值，即散列码，根据这些散列码保存在对应的位置上。Hashmap核心函数：
我们先来看下属性和默认值~
注意：初始容量太高和负载因子太低的话，遍历效率不太好。
构造函数
这里我们需要注意第一个构造函数，传入初始容量和负载因子，如果初始容量小于0抛出异常，大于最大容量MAXIMUM_CAPACITY则置为MAXIMUM_CAPACITY；如果不是这两个会进入tableSizeFor()方法，一起来看看：
int n=cap - 1;为什么要有第一步的减一操作？目的是为了防止传入的cap已经是2的幂，如果没有执行这个减一操作，返回的将是这个cap(传入是2的幂)的2倍，不太懂？请继续读下去。
n |=n >>> 1; n |=n >>> 2; n |=n >>> 4; n |=n >>> 8; n |=n >>> 16;如果传入的cap为0，经过减一和后面几次的无符号移动之后会一直是0，最后返回capacity是1；主要考虑cap不为0的情况，由于cap不为0，则n的二进制中总会有一个bit位为1，我们只考虑最高bit位为1。
第一步n >>> 1是无符号右移1位，再做或运算，使得二进制中的最高位和紧邻的右边一位也是1（0000 11## #### ####这种格式）。
第二步n >>> 2是无符号右移两位，再做或操作，第一步已经将最高位和其临位变为1，这一步则会将从高位开始的4位都变成1（0000 1111 #### ####这种格式）。
第三步n >>> 4是无符号右移4位，再做或操作，同样的道理，经过这一步之后从最高位开始后面的8位都变为1（0000 1111 1111 ####这种格式）。
以此类推，容量最大是32位正数，经过n |=n >>> 16之后最多也就32个1（1+2+4+8+16=31，但是别忘了开始的那一位），此时已经是负数了。在执行tableSizeFor之前，对initialCapacity做了判断，如果大于MAXIMUM_CAPACITY(2 ^ 30)，则取MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY(2 ^ 30)，会执行移位操作。所以这里面的移位操作之后，最大30个1，不会大于等于MAXIMUM_CAPACITY。30个1，加1之后得2 ^ 30） 。
举个例子~
现传入一个数cap为11，n=cap-1为10，则n二进制为0000 1010。
n |=n >>> 1：n >>> 1变为0000 0101，n或n>>> 1变为0000 1101，n即此值；
n |=n >>> 2：n >>> 2变为0000 0011，n或n>>> 2变为0000 1111，n即此值；
n |=n >>> 4：n >>> 4变为0000 0000，n或n>>> 4变为0000 1111，n不变；
n |=n >>> 8：n >>> 8变为0000 0000，n或n>>> 8变为0000 1111，n不变；
n |=n >>> 16：n >>> 16变为0000 0000，n或n>>> 16变为0000 1111，n不变；
看完上面可能会感到奇怪的是：为啥是将2的整数幂的数赋给threshold？
threshold这个成员变量是阈值，决定了是否要将散列表再散列。它的值应该是：capacity * load factor才对的。其实这里仅仅是一个初始化，当创建哈希表的时候，它会重新赋值的。
内部类Node
put()方法：放入Key-Value键值对
内部包含hash()函数和putVal()函数，hash函数用来求哈希值，putVal()函数用来将key-value键值对放入集合map，我们先看hash()函数：
这里直接将key的哈希值返回不就好了， 为什么还要做异或运算？我们进入putVal()函数看：
这里是根据key的哈希值来保存在散列表中的，刚刚上面的key原哈希值和高16位异或运算得到的新哈希值便是用来计算保存在散列表中位置的。
我们表的默认初始容量是16，要放到散列表中即为0-15的位置，即tab[i=(n - 1) & hash]这里。我们可以发现在做&运算的时候，仅仅是后4位有效（容量32则是后5位有效，依次类推），那如果我们key的哈希值高位变化很大，低位变化很小，直接拿过去做&运算，这就会导致计算出来的Hash值相同的很多。
而设计者将key的哈希值的高位也做了运算(与高16位做异或运算，使得在做&运算时，此时的低位实际上是高位与低位的结合)，这就增加了随机性，减少了碰撞冲突的可能性！
详细理解下HashMap的put()过程吧：
put源码中还可以挖掘更多细节，比如putTreeVal()在树中插入节点、treeifyBin()转变树结构等，感兴趣的可以多多研究，关于红黑树结构及原理，文章下面会介绍。
resize()方法：扩容机制
当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作。
很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。
get()：根据Key获取Value
hash()计算key对应的哈希值，上面介绍过，我们看getNode()：
这里只讲解了最基本的函数的源码，很多常用函数我们完全没必要全部都阅读源码，学会使用，了解原理即可，但是阅读源码是一种优秀的习惯，大家还是要习惯性的养成。
三、红黑树介绍
HashMap底层的链表达到一定长度时并且数组满足长度时，会将链表转变成红黑树结构。各种常见的树的用途：
二叉查找树
在介绍红黑树之前我们要先理解二叉查找树的结构：
如上图就是一个二叉查找树。二叉查找树有如下几条特性
1、果子树上所有结点的值均小于或等于它的根结点的值
2、右子树上所有结点的值均大于或等于它的根结点的值
3、左、右子树也分别为二叉排序树
那既然他名字中是有“查找”的，那么他是怎么查找的呢？比如我们要查找10这个元素，查找过程为：首先找到根节点，然后根据二叉查找树特性，我们知道要查找的10>9所以是在根节点的右边去查找，找到13，10<13,所以接着在13的左边找，找到11,10<11,继续在11的左边查找，这样就找到了10，这其实就是二分查找的思想。最后我们要查出结果所需的最大次数就是二叉树的高度！
二分查找的思想，找到数组的中间位置的元素v，将数组分成>v和<v两部分，然后将v和要查找的数据进行一个比较，如果大于v那么就在>v的部分再次进行二分查找，否则就在<v的部分进行二分查找，直到找到对应的元素。
那既然要查出结果所需的最大次数就是二叉树的高度，那这个高度会不会有时候很长呢？比如我们依次插入根节点为9如下节点：7,6,5,4,3,2,1。依照二叉查找树的特性，结果会变成什么样呢？7,6,5,4,3,2,1一个比一个小，那么就会成一条直线，也就是成为了线性的查询，时间复杂度变成了O（N）级别。为了解决这种情况，该红黑树出场了。
红黑树：自平衡二叉树，带有颜色属性的二叉查找树，颜色是红色或者黑色
红黑树为了保持平衡，还有制定一些约束，遵守这些约束的才能叫做红黑树：
节点是红色或黑色。根节点是黑色。每个叶子节点都是黑色的空节点（NIL节点）。每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(每一条树链上的黑色节点数量（称之为“黑高”）必须相等)。红黑树那么多规则，那么再插入和删除元素会不会破坏红黑树的规则呢？答案是肯定的，红黑树通过“变色”和“旋转”来维护红黑树的规则，变色就是让黑的变成红的，红的变成黑的，旋转又分为“左旋转”和“右旋转”。
HashMap注意问题
HashMap底层到底在何时转换成红黑树？
很多博文中只提到了链表长度大于八的条件，实际上是需要两个条件的：
1、链表长度大于8，官方源码如下：
2、当满足条件1以后调用treeifyBin方法转化红黑树。该方法中，数组如果长度小于MIN_TREEIFY_CAPACITY（64）就选择扩容，而不是转化为红黑树。
哈希冲突是什么？如何解决？
哈希表是基于数组的一种存储方式，由哈希函数和数组构成。当存储数据时，先根据函数计算出数据的地址，然后放入数组的特定地址位置里，这个函数是哈希函数。
哈希冲突很容易理解，其实就是指的是这个计算出来的位置被别人占用了的时候如何处理。举个例子，上面的HashMap是通过哈希值来寻找数组位置的，我存储(key1-va1)(key2-va2)两个键值对，若key1计算的哈希值是0，在数组第一个位置存储，然后计算key2的哈希值也是0，这时这个位置有key1了，总不能把key2覆盖key1吧，两个键值对的key值不一样，不符合。如何处理这种情况？
1、开放地址法：开放地址之线性探测法，出现Hash冲突后，依次查询这个键值后面的地址，找到一个空的或者全部查完没找到。开放地址之二次探查法，出现冲突后，对这个键值后面的地址或者前面的地址进行平方后查询
2、链表法：把哈希冲突冲突的元素都放在一个链表中，但是链表的长度不能太长，越长效率越慢。（HashMap采用这个方法，但是链表有可能转化成红黑树）
3、建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表，比较粗暴
HashMap在多线程中存在的问题？如何解决？
网上很多博客讲述的是HashMap中的死循环问题，其实HashMap中存在很多并发问题，因为HashMap设计的目的和应用场所就没有考虑并发场景。HashMap 的设计目标是简洁高效，没有采取任何措施保证 put、remove 操作的多线程安全。在各种操作的过程中都有可能存在多线程并发问题，在这些复杂的逻辑中有任何一个线程改变了散列表的结构就有可能出现并发问题。
在jdk1.8之前HashMap经常会出现死循环导致CPU利用率较高等问题，在jdk1.8及之后改善了这个问题，但是不代表不存在并发问题，多线程put时可能导致元素的丢失，put非null元素后get出来的却是null等情况都有可能会出现。
在多线程环境下如何使用呢~
1、Collections.synchronizedMap(new HashMap<String , Object>())：可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力。底层是对每一个方法使用锁，让每一个方法的操作都具有原子性，更具有安全性
2、Hashtable：遗留类，承自Dictionary类，并且是线程安全的，了解即可
3、ConcurrentHashMap ：ConcurrentHashMap 与 HashMap 相比，在高效率的基础上添加了对多线程安全的保证。下面的文章会单独拎出来讲解~
HashMap的遍历？
1、遍历HashMap的键值对：根据entrySet()获取HashMap的“键值对”的Set集合，通过Iterator迭代器遍历“第一步”得到的集合
// map中的key是String类型，value是String类型 String value=null; Iterator iter=map.entrySet().iterator(); while(iter.hasNext()) { Map.Entry entry=(Map.Entry)iter.next(); // 获取key key=(String)entry.getKey(); // 获取value value=entry.getValue(); }2、遍历HashMap的键：根据keySet()获取HashMap的“键”的Set集合，通过迭代器遍历得到集合
// map中的key是String类型，value是String类型 String key=null; String value=null; Iterator iter=map.keySet().iterator(); while (iter.hasNext()) { // 获取key key=(String)iter.next(); // 根据key，获取value value=map.get(key); }3、遍历HashMap的值：根据values()获取HashMap的“值”的集合，通过Iterator迭代器遍历“第一步”得到的集合
// map中的key是String类型，value是String类型 String value=null; Collection c=map.values(); Iterator iter=c.iterator(); while (iter.hasNext()) { value=iter.next(); }絮叨叨
你知道的越多，你不知道的也越多。
建议：集合之HashMap，面试之宠儿，工作之利器，非学不可，我是兄说的！
下一篇：2012款途安的质量怎么样？
发表评论