基于红黑树的TreeMap使用
背景
最近在项目中做异步任务调度服务的时候，用到红黑树来实现异步任务的管理，挑选出最符合条件的任务执行，于是使用到了TreeMap来管理
TreeMap与TreeSet
TreeSet中使用了TreeMap来实现，只是TreeMap中的Value只是一个普通的Object
TreeMap使用
TreeMap提供了put，get，firstKey，lastKey，higherKey，floorKey，ceilingKey，lowerKey等方法来辅助红黑树获取/存放数据
只是通常TreeMap的Key不是一个简单类型，而是一个对象，存储相关的信息，如下所示
public class JobInfo implements Comparable<JobInfo>{
long time;
int type;
String name;
@Override
public int compareTo(JobInfo node){
if (node==this || node.type==this.type){
return 0;
}
if (node.time>=this.time){
return 1;
} else{
return -1;
}
}
}而红黑树的插入和查找都遵循二叉查找树的特性--左子树比当前节点小，右子树比当前节点大
所以在使用TreeMap的对象都需要实现Comparable接口，否则会直接Crash，或者在TreeMap中传入Comapretor对象，通过该比较器进行比较，而在该接口的compareTo返回结果为：
- 返回值 0：代表相同节点
- 返回值 -1：代表当前节点比传入节点小，会往左子树递归遍历
- 返回值 1：代表当前节点比传入节点大，会往右子树递归遍历
而在TreeMap内部代码如下，通过Key与Root开始比较，比较的值小于0，则往左节点开始寻找，大于0，则往右节点开始寻找，直到等于0认为找到对应的节点，否则认为没有该节点.
getEntryUsingComparator
Put函数与Get函数
Put函数和Get函数用的是最多的函数，在Put函数中可以看到：
- 先通过Compartor比较，如果值为0，则直接setValue更新值，更新完后，直接返回
- 如果没有的话，则根据值找到最符合的子节点，然后通过比较值看插入左节点还是右节点
- 最后通过fixAfterInsertion来调整红黑树的平衡性
Put函数截取
可是，在项目中使用的时候会有一些问题，比如： 使用JobInfo期望根据time属性，按照time属性的大小排序构建红黑树，在获取的时候，获取time最小的Key对应的Value进行操作，同时操作完后，更新Key的time属性，重新调整红黑树，以至于可以在下一次直接获取最左节点的Key进行操作。
在TreeMap中并没有直接调整Key，或者说红黑树重新自平衡的方法，只能通过先remove，再Put，才能保证红黑树的平衡性
JobInfo removeKey;
removeKey.time=3000L;
Obejct value=treeMap.remove(removeKey);
treeMap.put(removeKey,value);这种错误的方式会导致找不到Value，返回的Value为空，因为在remove前更新了time，所以time的值会比原来自平衡的时候大，导致compare的时候，本应该compareTo的值为-1往左子树查找，结果却是compareTo的值为1，往右子树查找了，所以找不到Value。而正确的方式应该是
JobInfo removeKey;
Obejct value=treeMap.remove(removeKey);
removeKey.time=3000L;
treeMap.put(removeKey,value);应该先remove，获取到Value后，再更新Key，重新put，这样的红黑树才会重新根据Key自平衡。
并且在创建节点，新增加的时候比较的值必须不一样！！否则在查找的时候，TreeMap会找不到对应Key的Value而返回空，因为所有二叉搜索树都是二分查找来提高效率，而不会全部都遍历，所以需要特别注意
FirstKey和LastKey
FirstKey会递归找到最左子节点，也就是值最小的节点 LastKey会递归找到最右子节点，也就是值最大的节点
firstKey&&lastKey
higherKey和lowerKey
higherKey的作用是：返回传入的Key值大一点最接近的Key lowerKey的作用是：返回传入的Key值小一点最接近的Key
getHigherEntry
floorKey和ceilingKey
floorKey的作用是：优先返回自身，如果compareTo没有0的话，则与higherKey的作用是一样的 ceilingKey的作用是：优先返回自身，如果compareTo没有0的话，则与lowerKey的作用是一样的
image.png