基于红黑树的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函数中可以看到：

1. 先通过Compartor比较，如果值为0，则直接setValue更新值，更新完后，直接返回
2. 如果没有的话，则根据值找到最符合的子节点，然后通过比较值看插入左节点还是右节点
3. 最后通过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